1、6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 1数据结构数据结构第六章第六章 树和二叉树树和二叉树2022-11-116.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 2ABCDEFGHIJKLM树树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 36
2、.1 6.1 树的类型定义树的类型定义数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R：若若D为空集，则称为空树；为空集，则称为空树；否则否则:（1）在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,（2）当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不相交的个互不相交的有限集有限集 T1,T2,Tm,其中每一棵子集本身又是一棵符其中每一棵子集本身又是一棵符合本定义的树，称为根合本定义的树，称为根root的子树。的子树。基本操作：基本操作：查找：查找：Root(T);Value(T,cur_e);Pare
3、nt(T,cur_e);LeftChild(T,cur_e);TreeEmpty(T);T r e e D e p t h(T);TraverseTree(T,Visit();6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 46.1 6.1 树的类型定义树的类型定义插入：插入：InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删除：删除：ClearTree(&T)
4、;DestroyTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 56.1 6.1 树的类型定义树的类型定义和线性结构的比较和线性结构的比较 线性结构线性结构 树结构树结构第一个数据元素第一个数据元素(无前驱无前驱)；根结点根结点(无前驱无前驱)；最后一个数据元素最后一个数据元素(无后继无后继)；多个叶子结点多个叶子结点(无后继无后继)；其它数据元素其它数据元素 树中其它结点树中其它结点(一
5、个前驱、一个后继一个前驱、一个后继)。(一个前驱、多个后继一个前驱、多个后继)。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 6ABCDEFGHIJKLM树形表示树形表示A(B(E(K,L),F),C(G),D(H(M),I,J)嵌套括号表示法嵌套括号表示法树的表示方法：树的表示方法：I JFKLGMCCDBEA文氏图文氏图凹入表凹入表ABFEKLCDHIGMJ6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6
6、.6 树和森林 6.7 哈夫曼树与哈夫曼编码 7基本术语基本术语结点结点:数据元素数据元素+若干指向子树的分支。若干指向子树的分支。结点的度结点的度:分支的个数。分支的个数。树的度树的度:树中所有结点的度的最大值。树中所有结点的度的最大值。叶子结点叶子结点:度为零的结点。度为零的结点。分支结点分支结点:度大于零的结点；度大于零的结点；路径路径和和路径长度路径长度。孩子孩子结点、结点、双亲双亲结点、结点、兄弟兄弟结点、堂兄弟、结点、堂兄弟、祖先祖先结点、结点、子孙子孙结点。结点。边边：双亲节点：双亲节点x到子结点到子结点y的有序对的有序对(x，y)。结点的层次结点的层次:假设根结点的层次为假设根
7、结点的层次为1，第，第i 层的结点的层的结点的子树根结点的层次为子树根结点的层次为i+1。规定根的层数为规定根的层数为0。树的深度：树的深度：树中叶子结点所在的最大层次。树中叶子结点所在的最大层次。森林：森林：是是m（m0）棵互不相交的树的集合任何一棵）棵互不相交的树的集合任何一棵非空树是一个二元组非空树是一个二元组Tree=（root，F）其中：其中：root被称为根结点，被称为根结点，F被称为子树森林。被称为子树森林。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 86.2
8、6.2 二叉树的类型定义二叉树的类型定义二叉树的定义二叉树的定义定义：定义：二叉树是由二叉树是由n(n=0)个结点的有限集合构个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。不相交的左右子树组成，并且左右子树都是二叉树。与树的关系：与树的关系：这也是一个递归定义。这也是一个递归定义。区别区别：二叉树结点的子树要区分左子树和右二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。子树，还是右子树。6.1
9、 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 9(a)空二叉树空二叉树A (b)根和空的根和空的左右子树左右子树AB (c)根和左子树根和左子树二叉树的二叉树的5 5种基本形态种基本形态A(d)根和右子树根和右子树BA(e)根和左右子树根和左右子树BC6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 10二叉树的主要基本操作：二叉树的主要基本操作：查找：查找：Root(T
10、);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();插入：插入：InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);I
11、nsertChild(T,p,LR,c);删除：删除：ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 11性质性质1：在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i=1)。证明：证明：采用归纳法证明此性质。采用归纳法证明此性质。当当i=1时，只有一个根结点，时，只有一个根结点，2i-1=20=1,命题成立。命题成立。现在假定第现在假定第i1层上命题成
12、立，则第层上命题成立，则第i1层上至层上至多有多有2i-2个结点。由于二叉树每个结点的度最大为个结点。由于二叉树每个结点的度最大为2，故在第故在第i层上最大结点数为第层上最大结点数为第i1层上最大结点数的二层上最大结点数的二倍，倍，即即22i-22i-1。命题得到证明。命题得到证明。二叉树的重要特性：二叉树的重要特性：6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 12性质性质2：深度为：深度为k的二叉树至多有的二叉树至多有2k1个结点（个结点（k=1).证明：证明：深度为深度为
13、k的二叉树的最大的结点时为二叉的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质树中每层上的最大结点数之和，由性质1得到每层上的得到每层上的最大结点数最大结点数2i-1（第第i层上的最大结点数）层上的最大结点数）二叉树的重要特性：二叉树的重要特性：12k1i1i2k6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 13二叉树的重要特性：二叉树的重要特性：性质性质3：对任何一棵二叉树，如果其终端结点数为对任何一棵二叉树，如果其终端结点数为n0，度为度为2的结点数为的结点数
14、为n2，则则n0n21。证明：证明：设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点，二叉树中总结点数为数为N，因为二叉树中所有结点均小于或等于，因为二叉树中所有结点均小于或等于2，所以有：，所以有：Nn0n1n2 （1）再看二叉树中的分支数，除根结点外，其余结点都再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设有一个进入分支，设B为二叉树中的分支总数，为二叉树中的分支总数，则有：则有：NB1。由于这些分支都是由度为。由于这些分支都是由度为1和和2的结点射出的，的结点射出的，所以有：所以有：Bn1+2*n2 NB1n12n21 （2)由式（由式（1）和（）和
15、（2）得到：）得到：n0+n1+n2=n1+2*n2+1 n0n216.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 14满二叉树满二叉树2453671123456(a)完全二叉树完全二叉树123457(b)非完全二叉树非完全二叉树12367(c)非完全二叉树非完全二叉树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 15两种特殊形态的二叉树：两种特殊形态的二叉树：一
16、棵深度为一棵深度为k且由且由2k-1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。如果深度为如果深度为k、由由n个结点的二叉树中各结点能够与个结点的二叉树中各结点能够与深度为深度为k的顺序编号的满二叉树从的顺序编号的满二叉树从1到到n标号的结点相对标号的结点相对应，则称这样的二叉树为应，则称这样的二叉树为完全二叉树完全二叉树。完全二叉树的特点完全二叉树的特点是：是：（1）所有的叶结点都出现在第）所有的叶结点都出现在第k层或层或k1层。层。（2）对任一结点，如果其右子树的最大层次为）对任一结点，如果其右子树的最大层次为h，则其左子树的最大层次为则其左子树的最大层次为h或或h1。满二叉树和
17、完全二叉树满二叉树和完全二叉树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 16 性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n1。符号符号x表示不大于表示不大于x的最大整数。的最大整数。证明：证明：假设此二叉树的深度为假设此二叉树的深度为k，则根据性质，则根据性质2及完全及完全二叉树的定义得到：二叉树的定义得到：2k-11n=2k-1 或或 2k-1=n2k取对数得到：取对数得到：k1log2nk 因为因为k是整数。所以有：是整数。所以
18、有：klog2n1。二叉树的重要特性二叉树的重要特性6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 17性质性质5：如果对一棵有如果对一棵有n个结点的完全二叉树的结点按个结点的完全二叉树的结点按层序编号（从第层序编号（从第1层到第层到第log2n+1层，每层从左到右层，每层从左到右),则则对任一结点对任一结点i（1=i1，则其双亲是结点，则其双亲是结点i/2。（2）如果）如果2in，则结点，则结点i为叶子结点，无左孩子；否为叶子结点，无左孩子；否则，其左孩子是结点则，其左孩子是结
19、点2i。（3）如果）如果2i1n，则结点，则结点i无右孩子；否则，其右孩无右孩子；否则，其右孩子是结点子是结点2i1。证明：略！证明：略！完全二叉树的特点完全二叉树的特点:6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 186.3 6.3 二叉树的存储结构二叉树的存储结构1.顺序存储结构顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素。它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序因此，必须把二叉树的所有结点安排成为一个恰当
20、的序列，结点在这个序列中的相互位置能反映出结点之间的列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：逻辑关系，用编号的方法：#define max-tree-size 100Typedef telemtype sqbitreemax-tree-size;Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有从树根起，自上层至下层，每层自左至右的给所有结点编号。结点编号。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 19LKJIHGFEDCB
21、A 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树完全二叉树ABCDEFGHIJKL6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 20ABCDEFG 表示该处没有元素表示该处没有元素存在仅仅为了好理解存在仅仅为了好理解ABCDEFG一般二叉树一般二叉树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 211.1.顺序存储结构顺序存储结构缺点：缺点：有
22、可能对存储空间造成极大的浪费，在最有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为坏的情况下，一个深度为H且只有且只有H个结点的个结点的右单支树右单支树确需要确需要2h-1个结点存储空间。而且，若经常需要插入与个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！删除树中结点时，顺序存储方式不是很好！6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 221.1.顺序存储结构顺序存储结构ABCDindexindex 0 01 1 2 23 34 4 5
23、 5 6 6 7 78 8 9 9 1010 1111 1212 1313 1414 1515A A B B C C D D-6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 23lchildDatarchildABCDEFGH（2 2）二叉链表法）二叉链表法ABCDEFGH6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 24Typedef struct BiTNod
24、e TelemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;2 2）二叉链表法）二叉链表法二叉树的二叉链表存储表示二叉树的二叉链表存储表示6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 25Status CreateBiTree(BiTree*T)/*创建一棵二叉树创建一棵二叉树*/scanf(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNod
25、e)exit(OVERFLOW);Tdata=ch;CreateBiTree(Tlchild);CreateBiTree(Trchildd);return OK;6.3 6.3 二叉树的存储结构二叉树的存储结构链式存储结构的算法：链式存储结构的算法：6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 26三叉链表法三叉链表法ABCDEFGHDBCEFGHArchildparentdatalchild6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉
26、树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 27Typedef struct TBiTNode TelemType data;struct TBiTNode*lchild,*rchild,*parent;BiTNode,*BiTree;三叉链表法三叉链表法二叉树的三叉链表存储表示二叉树的三叉链表存储表示6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 286.4 6.4 二叉树的遍历二叉树的遍历一、问题的提出一、问题的提出顺着某一条搜索路径巡访二叉
27、树中的结点，使得每顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。个结点均被访问一次，而且仅被访问一次。“访问访问”的含义可以很广，如：输出结点的信息的含义可以很广，如：输出结点的信息等。等。对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：1先上后下的按层次遍历；先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。先右（子树）后左（子树）的遍历。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6
28、树和森林 6.7 哈夫曼树与哈夫曼编码 296.4 6.4 二叉树的遍历二叉树的遍历二、先左后右的遍历算法二、先左后右的遍历算法 先（根）序的遍历算法：先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（若二叉树为空树，则空操作；否则，（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树。）先序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：若二叉树为空树若二叉树为空树,则空操作；否则则空操作；否则,（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。后（根）序的遍历算法：后（根）序
29、的遍历算法：若二叉树为空树若二叉树为空树,则空操作则空操作;否则否则,（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 306.4 6.4 二叉树的遍历二叉树的遍历示例示例/-abcd图图1 (a-b)/(c+d)/bca-+d图图2 a-(b/c+d)/bca-+d图图3 a-b/c+d先序：先序：/-ab+cd中序：中序：a-b/c+d后序：后序：ab-cd+/先序：
30、先序：-a+/bcd中序：中序：a-b/c+d后序：后序：abc/d+-先序：先序：+-a/bcd中序：中序：a-b/c+d后序：后序：abc/-d+分别称为表达式的前缀表示法、中缀表示法和后缀表示分别称为表达式的前缀表示法、中缀表示法和后缀表示法（逆波兰表示法）。法（逆波兰表示法）。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 316.4 6.4 二叉树的遍历二叉树的遍历三、算法的递归描述三、算法的递归描述 void Preorder(BiTree T,void(*visit
31、)(TElemType&e)/先序遍历二叉树先序遍历二叉树 if(T)visit(T-data）;/访问结点访问结点Preorder(T-lchild,visit);/遍历左子树遍历左子树Preorder(T-rchild,visit);/遍历右子树遍历右子树6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 32void InOrderTraverse(BiTree T,void(*visit)(TElemType&e)/中序遍历中序遍历if(T)InOrderTraverse(T
32、-lchild,visit);visit(T-data）;/访问结点访问结点InOrderTraverse(T-rchild,visit);void PostOrderTraverse(BiTree T,void(*visit)(TElemType&e)/后序遍历后序遍历if(T)PostOrderTraverse(T-lchild,visit);PostOrderTraverse(T-rchild,visit);visit(T-data）;/访问结点访问结点6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6
33、.7 哈夫曼树与哈夫曼编码 33四、先序遍历算法的非递归描述四、先序遍历算法的非递归描述先序遍历的非递归算法。先序遍历的非递归算法。t指向根，指向根，p为指针，指为指针，指向当前结点。使用一个堆栈向当前结点。使用一个堆栈s（），（），top为栈指针为栈指针 1 if t=NULL 2 then 输出输出 这是一棵空树这是一棵空树 3 else p=t，top=0 4 DO 5 while p！=NULL 6 输出输出 data（p）;7 top+;8 if topn9 then 调用调用 栈满栈满 10 else stop=p，p=lchild（p）11 if top！=012 p=stop;
34、top-;p=rchild（p）13while(top=0&p=null)算法结束算法结束6.4 6.4 二叉树的遍历二叉树的遍历四、先序遍历算法的非递归描述四、先序遍历算法的非递归描述1 if t=NULL2 then 输出输出 这是一棵空树这是一棵空树 3 else p=t，top=0 4 DO 5 while p！=NULL 6 输出输出 data（p）;7 top+;8 if topn9 then 调用调用 栈满栈满10 else stop=p，p=lchild（p）11 if top！=012 p=stop;top-;p=rchild（p）13while(top=0&p=null)算
35、法结束算法结束注注:结点旁结点旁的数字是的数字是该结点的该结点的存储地址存储地址二叉树执行先序遍历二叉树执行先序遍历算法的过程算法的过程栈栈6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 35中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法，使用堆栈中序遍历的非递归算法，使用堆栈s（），（），top为指针，为指针，t指向根，指向根，p为指针，指向当前结点为指针，指向当前结点1 top=0,p=t2 DO 3 while(p!=NIL)4 top+5 if(topn)6
36、 then 调用调用 栈满栈满7 else stop=p;p=Lchild(p)8 if top!=09 then p=stop,top-10 输出输出 data(p)11 pn)6 then 调用调用 栈满栈满7 else stop=p;p=Lchild(p)8 if top!=09 then p=stop,top-10 输出输出 data(p)11 plchild)&(!T-rchild)count+;CountLeaf(T-lchild,count);/统计左子树中叶子结点个数统计左子树中叶子结点个数CountLeaf(T-rchild,count);/统计右子树中叶子结点个数统计右子树
37、中叶子结点个数6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 38五、遍历算法的应用举例五、遍历算法的应用举例2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)int Depth(BiTree T)if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return dept
38、hval;6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 39五、遍历算法的应用举例五、遍历算法的应用举例3、复制二叉树、复制二叉树(后序遍历后序遍历)/生成一个二叉树的结点生成一个二叉树的结点BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rptr)if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=item;T-lchild=lptr；T-rchild=rp
39、tr;return T;6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 40五、遍历算法的应用举例五、遍历算法的应用举例3、复制二叉树、复制二叉树(后序遍历后序遍历)BiTNode*CopyTree(BiTNode*T)if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);else newlptr=NULL;if(T-rchild)newrptr=CopyTree(T-rchild);else newrptr=NULL;
40、newnode=GetTreeNode(T-data,newlptr,newrptr);return newnode;6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 416.5 6.5 线索二叉树线索二叉树一、何谓线索二叉树？一、何谓线索二叉树？遍历二叉树是按一定的规则将二叉树中结点排列成遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列；这实际上是把一个非线性结构进行线性一个线性序列；这实际上是把一个非线性结构进行线性化的操作。化的操作。以二叉链表作为存储结构时，对于某个
41、结点只能找以二叉链表作为存储结构时，对于某个结点只能找到其左右孩子，而不能直接得到结点在任一序列中的前到其左右孩子，而不能直接得到结点在任一序列中的前驱或后继。要想得到只能通过遍历的动态过程才行。驱或后继。要想得到只能通过遍历的动态过程才行。怎样保存遍历过程中得到的信息呢？怎样保存遍历过程中得到的信息呢？（1增加两个指针增加两个指针（2利用结构中的空链域，并设立标志。即采用如利用结构中的空链域，并设立标志。即采用如下的形式：下的形式：lchild ltagdatartagrchild6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉
42、树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 426.5 6.5 线索二叉树线索二叉树何谓线索二叉树？何谓线索二叉树？指向该线性序列中的指向该线性序列中的“前驱前驱”和和“后继后继”的的指针指针，称，称作作“线索线索”。包含。包含“线索线索”的存储结构，称作的存储结构，称作“线索链线索链表表”；与其相应的二叉树，称作；与其相应的二叉树，称作“线索二叉树线索二叉树”。对线索链表中结点的约定：对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则若该结点的左子树不空，则lchild域的指针指向其域的指针
43、指向其左子左子树树，且左标志域，且左标志域 ltag的值为的值为0；否则，否则，lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志，且左标志ltag的值的值为为1。若该结点的右子树不空，则若该结点的右子树不空，则rchild域的指针指向其右域的指针指向其右子树，且右标志域子树，且右标志域rtag的值为的值为0；否则，否则，rchild域的指针指向其域的指针指向其“后继后继”，且右标志，且右标志rtag的值为的值为1。6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 43
44、6.5 6.5 线索二叉树线索二叉树0 A 01B 00D 1 1C 11E 1TADBEC中序序列：中序序列：BCAED6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林 6.7 哈夫曼树与哈夫曼编码 446.5 6.5 线索二叉树线索二叉树线索链表的结构描述：线索链表的结构描述：typedef enum Link,Thread PointerThr;/Link=0:指针，指针，Thread=1:线索线索typedef struct BiThrNodeTElemType data;struct BiThrNod
45、e*lchild,*rchild;/左右指针左右指针PointerThr LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree;6.5 6.5 线索二叉树线索二叉树找结点的后继找结点的后继线索化线索化：对二叉树以某种次序遍历使其变为线索二叉树的：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做过程叫做线索化线索化。下面以下面以中序中序为例看看如何在线索二叉树中为例看看如何在线索二叉树中找结点的后继找结点的后继。（1树中所有叶子结点和只有左子树的右指针均为线索，树中所有叶子结点和只有左子树的右指针均为线索，直接指示了结点的后继；直接指示了结点的后继；（2其他非终端结
46、点的右链均为指针，无法得到后继的信其他非终端结点的右链均为指针，无法得到后继的信息。然而根据中序遍历的规律可知，结点的后继应是遍历其右息。然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。子树时访问的第一个结点，即右子树中最左下的结点。（3反之，在中序线索树中找结点前驱的规律是：若左标反之，在中序线索树中找结点前驱的规律是：若左标志是志是1，则左链为线索，指示其前驱；否则，遍历该结点的左子，则左链为线索，指示其前驱；否则，遍历该结点的左子树时最后访问的结点（左子树中最右下的结点为其前驱树时最后访问的结点（左子树中最右下的结点为其前驱)。ABCEI
47、DHF GGKnullnull6.5 6.5 线索二叉树线索二叉树找结点的后继找结点的后继在在后序线索树后序线索树中找结点中找结点x的后继较复杂，可分三种情况：的后继较复杂，可分三种情况：（1若结点若结点x是二叉树的根是二叉树的根,则其后继为空则其后继为空;（2若结点若结点x是其双亲的右孩子或是左孩子且其双亲没有是其双亲的右孩子或是左孩子且其双亲没有右子树右子树,则其后继即为双亲结点。则其后继即为双亲结点。（3若结点若结点x是其双亲的左孩子，且其双亲有右子树，则是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点。其后继为双亲的右子树上按后序遍历出的第一个结点。
48、由此可见，在后序线索化树上找后继时需知道结点的双亲，由此可见，在后序线索化树上找后继时需知道结点的双亲，因此需要使用三叉链表。因此需要使用三叉链表。可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度也是也是O(n)，但常数因子小，且不需要设栈，因此若在某程序中但常数因子小，且不需要设栈，因此若在某程序中需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。则应采用线索链表作存储结构。6.5 6.5 线索二叉树线索二叉树二、线索链表的遍历算法二、线索链表的遍历算
49、法:for(p=firstNode(T);p;p=Succ(p)Visit(p);中序线索化链表的遍历算法中序线索化链表的遍历算法:中序遍历的第一个结点中序遍历的第一个结点？在中序线索化链表中结点的后继在中序线索化链表中结点的后继？ABCEIDHF GGKnullnull6.5 6.5 线索二叉树线索二叉树二、线索链表的遍历算法二、线索链表的遍历算法:Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)/T指向头结点，头指向头结点，头结点的左链结点的左链lchild指向根结点，头结点的右链指向根结点，头结点的右链r
50、child，指向指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树，对每个数据元素调用函数二叉树，对每个数据元素调用函数Visit。p=T-lchild;/p指向根结点指向根结点while(p!=T)/空树或遍历结束时，空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;/访问其访问其左子树为空的结点左子树为空的结点 while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结访
