1、v 本章中主要介绍下列内容：l 树的逻辑定义和存储结构l 二叉树的逻辑定义、存储结构l 二叉树的基本操作算法l 树和二叉树的转换l 哈夫曼树及其应用第六章 树和二叉树本章学习要求掌握：树和二叉树的性质，有关术语及基本概念。掌握：二叉树的两种存储方法，重点是链式存储。掌握：各种次序的遍历算法，能灵活运用遍历算法实现二叉树的各种运算。掌握：几种建立二叉树的方法。了解：二叉树的线索化及其实质，了解在各种线索树中查找给定结点的前趋和后继的方法。了解：树、森林与二叉树之间的转换方法。了解：树的各种存储结构及其特点；树和森林的二种次序的遍历。掌握：哈夫曼树的基本概念，最优二叉树和哈夫曼编码方法。6.1 树
2、基本概念6.2 二叉树的基本操作与存储实现6.3 二叉树的遍历6.4 线索二叉树6.5 二叉树的应用6.6 树的定义与相关术语6.7 树的基本操作与存储6.8 树、森林与二叉树的转换6.9 树和森林的遍历6.1 6.1 树的基本概念树的基本概念 1.1.树的定义树的定义 树树是一种常非线性结构树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。递归定义的递归定义的树的几种形态2.2.树的特点树的特点（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前
3、驱结点（2）树中所有结点可以有零个或多个后继结点树结构和非树结构的示意 图3.3.树的表示方法：树的表示方法：(b)凹入表（a）树形表示ABCDEFIJGH(A(B(D)(E(I)(J)(C(G)(H)(d)嵌套括号表示法CDEIJFGHAB(c)文氏图4.4.基本术语基本术语v结点(node)表示树中的元素，包括数据项及若干指向其子树的分支v结点的度(degree)结点拥有的子树数v叶子(leaf)度为0的结点,也叫终端结点v分支结点度0的结点，也叫非终端结点v结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层v树的度一棵树中最大的结点度数v树的深度(depth)树中结点的最
4、大层次v有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。v森林 是m（m0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：v孩子(child)结点子树的根称为该结点的孩子v双亲(parents)孩子结点的上层结点v兄弟(sibling)同一双亲的孩子v祖先、子孙如果有一条路径从结点M到结点N，那么M就称为N的祖先，N成为M的子孙v堂兄弟 双亲在同一层的结点互为堂兄弟。ABCDEFGHIJKLM叶子：K，L，F，G，M，I，J结点B，C，D为兄弟结点K，L为兄弟结点A的度：结点B的度：结点M的度：结点A的孩子
5、：结点B的孩子：结点I的双亲：结点L的双亲：树的度：结点A的层次：结点M的层次：树的深度：结点F，G为堂兄弟结点A是结点F，G的祖先其它术语:有序树和无序树、森林320DE4143B，C，DE，F术语ABDEFHJKLM结点A的度：2结点B的度：2结点M的度：0叶子：K，L，F，M，J结点A的孩子：B，D结点B的孩子：E，F结点J的双亲：D结点L的双亲：E结点B，D为兄弟结点K，L为兄弟树的度：2结点A的层次：1结点M的层次：4树的深度：4结点F，H为堂兄弟结点A是结点F，H的祖先5.5.树的基本运算树的基本运算常用操作常用操作：（1）构造一个树 CreateTree(T)（2）清空以T为根的
6、树 ClearTree(T)（3）判断树是否为空 TreeEmpty(T)（4）获取给定结点的第i个孩子 Child(T,node,i)（6）获取给定结点的双亲 Parent(T,node)（6）遍历树Traverse(T)对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依后序遍历方法依次访问每棵子树，最后访问根结点。6.2 6.2 二叉树二叉树6.2.1 6.2.1 二叉树的定义二叉树的定义1.1.定义定义 二叉树二叉树是n（n0）个结点的有限集合。当n=0时
7、，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。二叉树二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。递归定义的递归定义的二叉树结构的图形表示示例G HD E FB CA 只有根结点的二叉树空二叉树 左子树右子树为空 右子树左子树为空 左子树右子树左、右子树均非空2.2.二叉树的二叉树的5 5种形态种形态：3.3.二叉树的基本运算二叉树的基本运算 （1）构造一棵二叉树 CreateBTree(BT)（2）清空以BT为根的二叉树 ClearBTre
8、e(BT)（3）判断二叉树是否为空 BTreeEmpty(BT)（4）获取给定结点的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node)（5）给定结点的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node)（5）获取给定结点的双亲 Parent(BT,node)（6）遍历二叉树Traverse(BT)6.2.2 二叉树性质v性质1：)1(21iii个结点层上至多有在二叉树的第 第i层上最大结点数是第i-1层的2倍，即 故命题得证12222ii证明：用归纳法证明之12201ii=1时，只有一个根结点是对的12j假设对所
9、有j(1ji)命题成立，即第j层上至多有 个结点22i那么，第i-1层至多有 个结点又二叉树每个结点的度至多为2v性质2：深度为k的二叉树至多有 个结点(k1)12 k证明：由性质1，可得深度为k 的二叉树最大结点数是122)(111kkikiii层的最大结点数第v性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n
10、1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1几种特殊形式的二叉树v满二叉树l定义：12个结点的二叉树称为且有一棵深度为kkl特点：每一层上的结点数都是最大结点数v完全二叉树l定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为l特点u叶子结点只可能在层次最大的两层上出现u对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1ABCKDEHILFGJ123456789101112ABCKDEHILMFGJNO1234567891011131415ABCDEJK12345
11、67ABCDEG123456证明：根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有2 k-1-1n2k-12 k-1 n 2kK-1 log2n 1，则其双亲是i/2 (2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i (3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+12i+2 2i 2i+1 2i+2 2i+3 i+1 2i 2i+1i i i+1 6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。1.顺序存储结构 其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序
12、存放结点内容。l完全二叉树的存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素l特点：结点间关系蕴含在其存储位置中ABCKDEHILFGJ1234567891011121.顺序存储结构:用一组连续的存储单元按照完全二叉树的 每个结点编号的顺序存放结点内容。A B C D E F G H I J K L1 2 3 4 5 6 7 8 9 10 11 12 6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。l一般二叉树的顺序存储：将一般二叉树添加虚结点转为完全二叉树，然后进行存储A B C D E J K 1 2 3 4 5 6 7 8 9 10
13、11l特点：u结点间关系蕴含在其存储位置中u浪费空间，适于存满二叉树和完全二叉树ABCDEJK1234567891011在C语言中，这种存储形式的类型定义如下所示：#define MaxTreeNodeNum 100typedef struct datatype dataMaxTreeNodeNum;/*根存储在下标为1的数组单元中*/int n;/*当前完全二叉树的结点个数*/QBTree;（1）构造一棵完全二叉树void CreateBTree(QBTree*BT,DataType data,int n)if(n=MaxTreeNodeNum)n=MaxTreeNodeNum-1;for(
14、i=1;idatai=datai;BT-n=n;（2）获取给定结点的左孩子 int LeftCHild(QBTree BT,int node)if(2*nodeBT.n)return 0;else return 2*node;RightChild(BT,node)与这个操作类似，读者可试着自行完成。（3）获取给定结点的双亲 int Parent(QBTree BT,int node)if(1node&nodeBDCD L R先序遍历序列：A B D C先序遍历:先访问根结点,然后分别先序遍历左子树、右子树ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍
15、历:先中序遍历左子树，然后访问根结点，最后中序遍历右子树ADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:先后序遍历左、右子树，然后访问根结点B-+/a*b-efcd先序遍历：中序遍历：后序遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/e f 下面我们再给出两种遍历二叉树的方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。D G B A E C H F
16、G HD E FB CA 任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。G HD E FB CAv遍历算法：由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。l递归算法void PreOrder(BiTree bt)if(bt=NULL)return；printf(%dt,bt-data);PreOrder(bt-lchild);PreOrder(bt-rch
17、ild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C6.3.2二叉树遍历的非递归算法（1）先序遍历的非递归实现 可利用堆栈将递归算法改写成非递归的形式BiTree stackMAXNODE;X遍历左子树遍历右子树访问结点bt 非递归先序遍历二叉树的主要操作：
18、非递归先序遍历二叉树的主要操作：p=bt;while(1)while(p不空不空)visit(p-data);/进栈之前访问进栈之前访问p结点结点；push(p,stack);p=p-lchild;if(栈空栈空)return;p=pop(stack);p=p-rchild;ABCDEFGptopP-A(1)访问：AABCDEFGp访问：ABtopP-A(2)P-B访问：ABCtopP-AP-C(3)P-BtopP-A (4)P-DpABCDEFGABCDEFGp访问：ABCDwhile(p不空不空)visit(p-data);push(p,stack);p=p-lchild;p=pop(st
19、ack);p=p-rchild;ABCDEFGp访问：ABCDEtopP-AP-E(5)P-DABCDEFGp访问：ABCDEGtopP-AP-G(6)P-DABCDEFGp访问：ABCDEGFtopP-A(7)P-FABCDEFGp栈空结束top (8)p=bt;while(1)while(p不空不空)push(p,stack);p=p-lchild;if(栈空栈空)return;p=pop(stack);visit(p-data);/出栈时访问出栈时访问p结点结点；p=p-rchild;（2）中序遍历的非递归实现ABCDEFGpP-A(1)ABCDEFGpP-AP-B(2)ABCDEFGp
20、P-AP-BP-C(3)p=NULLABCDEFGP-AP-B访问：C(4)pABCDEFGP-A访问：C B(5)ABCDEFGP-AP-D访问：C Bp(6)ABCDEFGP-AP-DP-E访问：C Bp(7)ABCDEFGP-AP-D访问：C B Ep(8)ABCDEFGP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGP-A访问：C B E G Dp(11)ABCDEFGP-AP-F访问：C B E G Dp(12)ABCDEFGP-AP-D访问：C B E Gp(10)ABCDEFGP-A访问：C B E G D Fp=NULL(13)ABCDEFG访问：C B E
21、G D F Ap(14)ABCDEFG访问：C B E G D F Ap=NULL(15)（3）后序遍历的非递归实现Typedef struct BiTree link;int flag=0;/进栈的次数进栈的次数 stacktype;stacktype stackMAXNODE;/顺序栈顺序栈stacktype XP；结点要入两次栈，出两次栈，在第二次出栈时访问。p=bt;while(1)while(p不空不空)XP.link=p；XP.flag=1；push(XP,stack);/第一次进栈第一次进栈 p=p-lchild;if(栈空栈空)return;XP=pop(stack);p=XP
22、.link;sign=XP.flag;if(sign=2)/第二次出栈第二次出栈 visit(p-data);p=NULL;else /第一次出栈第一次出栈 XP.link=p；XP.flag=2；push(XP,stack);/第二次进栈第二次进栈 p=p-rchild;pABCDEFGP-A 1(1)ABCDEFGpP-A 1P-B 1(2)ABCDEFGpP-A 1P-B 1P-C 1(3)while(p不空不空)XP.link=p；XP.flag=1；push(XP,stack);/第一次进栈第一次进栈 p=p-lchild;ABCDEFGP-A 1P-B 1P-C 1(4)ABCDE
23、FGP-A 1P-B 1P-C 2(5)ABCDEFGP-A 1P-B 1(6)XP=pop(stack);p=XP.link;sign=XP.flag;if(sign=2)/第二次出栈第二次出栈 visit(p-data);p=NULL;else /第一次出栈第一次出栈 XP.link=p；XP.flag=2；push(XP,stack);/第二次进栈第二次进栈 p=p-rchild;C第一次出栈C第二次进栈C第二次出栈访问CB第一次出栈第二次进栈ABCDEFGP-A 1P-B 2(7)pABCDEFGP-A 1P-B 2P-D 1P-E 1(8)pABCDEFGP-A 1P-B 2P-D
24、1P-E 2P-G 1(9)pABCDEFGP-A 1P-B 2P-D 1P-E 2(12)访问C GABCDEFGP-A 1P-B 2P-D 2P-F 1(13)访问C G EABCDEFGP-A 1P-B 2P-D 2P-F 1(14)访问C G E F D B ABCDEFGP-A 2 (15)访问C G E F D B A ABCDEFG (16)6.3.3 按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。G HD E FB CA按层次遍历按层次遍历该二叉树的序列为该二叉树的序列为：ABCD
25、EFGH 二叉树用顺序存储结构表示时，按层遍历的算法实二叉树用顺序存储结构表示时，按层遍历的算法实现现A 1B 3 4 C D 5 6 E F 7 8 G01234567ABCDEFG(a)完全二叉树A 1B 2 3 CD 4 E 6 7 F(b)非完全二叉树01234567A BC#D EF图 5-20void LevelOreder(QBTree BT)for(i=1;ilchild)Visite(p-lchild);EnQueue(&Q,p-lchild);/处理左孩子 if(!p-rchild)Visite(p-rchild);EnQueue(&Q,p-rchild);/处理右孩子 6
26、.3.4 6.3.4 二叉树遍历算法的应用二叉树遍历算法的应用 二叉树是递归定义，可以写出它的递归遍历算法，同时借助遍历算法可以实现一些基本的应用，如：节点计数、创建二叉树、计算二叉树的高度等等1.先序遍历查找数据元素ABCDEFGBiTree Search(BiTree bt,datatype x)if（空树）return NULL；if(bt-data=x)return bt;P为查找左子树的结果；if（找到）return p；else P为查找右子树的结果；return p；2.统计二叉树中叶子结点个数算法int countleaf(BiTree bt)if（空树）return 0；if
27、(bt-lchild=NULL&bt-rchild=NULL)return 1;return(countleaf(bt-lchild)+countleaf(bt-right)；这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。void Leaf(BTree BT,int *count)if(BT)Leaf(BT-child,&count);/计算计算左子树的叶子结点个数左子树的叶子结点个数 if(BT-lchild=NULL&BT-rchild=NULL)(*count)+;Leaf(BT
28、-rchild,&count);/计算计算右子树的叶子结点个数右子树的叶子结点个数 3.输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。ABCDEFG A B C D E F G l按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABC00DE0G00F000#typ
29、edef char datatype;void createBinTree(BiTree*t)输入一个字符ch;if(ch=#)*t=NULL;return;*t=(BiTNode*)malloc(sizeof(BiTNode);(*t)-data=ch;createBinTree(&(*t)-lchild);createBinTree(&(*t)-rchild);4.由中序和先序遍历序列建立二叉树的二叉链表ABCDEFG已知先序序列为：ABCDEGF 中序序列为：CBEGDFA设先序序列的序号范围为ij（初始情况为1n），中序序列的序号范围为kh（初始情况为1n）；算法过程：创建根结点；找到
30、先序序列的i对应的中序序列中的位置m；划定左、右子树的范围；创建左子树；创建右子树；5.交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。void change_left_right(BTree BT)if(BT)change_left_right(BT-lchild);change_left_right(BT-rchild);BT-lchildBT-rchild;6.求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的
31、思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。int hight(BTree BT)/h1和h2分别是以BT为根的左右子树的高度 if(BT=NULL)return 0;else h1=hight(BT-lchild);h2=hight(BT-right);return maxh1,h2+1;问题的提出：二叉树中有很多闲置的指针，能否利用它们为访问二叉树提供便利，如下图所示：如：求解某结点在某种遍历次序下的前驱或后继结点6.4线索二叉树6.4.1 线索的概念求前驱和后继的方法：求前驱和后继的方法：1.遍历通过指定次序的遍历发现结点的前驱或后继，费
32、时间，低效2.增设前驱和后继指针在每个结点中增设两个指针，分别指示该结点在指定次序下的前驱或后继。增加空间开销3.利用二叉链表中的空指针域（n个结点的二叉树有n+1个空指针域），将二叉链表中的空的指针域改为指向其前驱和后继：空的左孩子指针指向其前驱，空的右孩子指针指向其后继称这种新的指针为（前趋或后继）称这种新的指针为（前趋或后继）线索，所得到的二叉树被称为所得到的二叉树被称为线索二叉树，将二叉树转变成线，将二叉树转变成线索二叉树的过程被称为索二叉树的过程被称为线索化。线索二叉树根据所选择。线索二叉树根据所选择的次序可分为先序、中序和后序线索二叉树。的次序可分为先序、中序和后序线索二叉树。比较
33、好的比较好的方法方法线索化线索化为什么？为什么？（a）未加区分标志的先序线索二叉树的二叉链表示例）未加区分标志的先序线索二叉树的二叉链表示例 然而，仅仅按照这种方式简单地修改指针的值还不行，因为这将导致难以区分二叉链表中各结点的孩子指针和线索。例如，图6.15中结点C的lchild指针域所指向的结点是其左孩子还是其前趋？为此，在每个结点中需再引入两个区分标志ltag和rtag，并且约定如下：ltag=0：lchild指示该结点的左孩子。ltag=1：lchild指针该结点的前趋。rtag=0：rchild指示该结点的右孩子。rtag=1：rchild指针该结点的后继。lchild ltag d
34、ata rtag rchild线索二叉链表结构描述如下：线索二叉链表结构描述如下：typedef char datatype；/*不妨设数据类型为字符型*/typedef struct Threadnode int ltag,rtag;datatype data;struct Threadnode *lchild,*rchild;Threadnode,*Thread_Tree;图图6.15 b 线索二叉树的二叉链表形式示例线索二叉树的二叉链表形式示例ABCDE A B D C ET先序序列：ABCDE00001111 11v先序线索二叉树ABCDE A B D C ET中序序列：BCAED00
35、00111111v中序线索二叉树ABCDE A B D C ET后序序列：CBEDA0000111111v后序线索二叉树ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED 0 1头结点：ltag=0,lchild指向根结点rtag=1,rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉树0000111111v带头结点的中序线索二叉树6.4.2 线索的算法实现线索的算法实现 对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问
36、结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚已访问过的结点，即若指针t指向当前结点，则pre指向它的前驱，以便增设线索。1.建立一棵中序线索化二叉树ABCDE 0 1preBiThree pre;int Inorder(BiThree *head,BiThree T)申请头结点*head空间；(*head)-ltag=0;(*head)-rtag=1;(*head)-rchild=*head;if(T为空)*head-lchild=*head;return 1;(*head)-lchild=T;pre
37、=*head;InThreading(T);pre-rchild=*head;pre-rtag=1;(*head)-rchild=pre;return 1;A B D C ET0000000000*headABCDEvoid InTreading(BiThrTree p)/*递归中序线索化二叉树*/if(p=NULL)return;InTreading(p-lchild);/*中序线索化左子树*/if(p-lchild=NULL)/*建立前驱线索*/p-ltag=1;p-lchild=pre;/*左孩子域指向前驱*/if(pre-rchild=NULL)/*建立后继线索*/p-rtag=1;p
38、re-rchild=p;pre=p;/*中序线索化右子树*/InTreading(p-rchild);0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 12.中序线索二叉树的遍历算法 void InOrderTh(Threadnode*t)/*对中序线索二叉树进行中序遍历*/Threadnode *p;if(t)p=t;while(p-ltag=0)p=p-lchild;/*找最左下的结点，即中序遍历的第一个结点*/while(p)/*访问当前结点并找出当前结点的中序后继*/visite(p-data);/*访问当前结点*/p=In
39、PostNode(p);/*在中序线索二叉树上寻找结点p的中序后继结点*/如何实现如何实现Inpostnode？4.在中序线索二叉树中找结点后继的方法：（1）若rtag=1,则rchild域直接指向其后继（2）若rtag=0,则结点的后继应是其右子树的左链尾（ltag=1)的结点3.在中序线索二叉树中找结点前驱的方法：（1）若ltag=1,则lchild域直接指向其前驱（2）若ltag=0,则结点的前驱应是其左子树的右链尾（rtag=1)的结点ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 1 在中序线索二叉树上寻找结
40、点p的中序前驱结点的算法如下：Threadnode *InPreNode（Threadnode *p）/*在中序线索二叉树上寻找结点p的中序前驱结点*/Threadnode *pre;pre=p-lchild;if(p-ltag!=1)while(pre-rtag=0)pre=pre-rchild;return(pre);在中序线索二叉树上寻找结点p的中序后继结点的算法如下：Threadnode *InPostNode（Threadnode *p）/*在中序线索二叉树上寻找结点p的中序后继结点*/Threadnode *post;post=p-rchild;if (p-rtag=0)while
41、(post-ltag=0)post=post-lchild;return(post);5.在中序线索二叉树上查找值为x的结点（带头结点）BiThrTree Search(BiThrTree head,datatype x)BiThrTree p=head-lchild;if(p=head)return NULL;找到中序遍历的第一个结点；从该结点开始顺着后继进行查找、比较；if(找到)return p;else return NULL;6.在中序线索二叉树上查找任意结点在先序下的后继情况一：该结点p为分支结点 情况二：该结点p为叶子ABDEpCABpABDEpABDEp 后继为由右线索向上直到
42、某个结点有右孩子或头结点为止 p-rchild为后继;if（有左孩子）p-lchild为后继;else/有右孩子无左孩子7.在中序线索二叉树上查找任意结点在后序下的前驱情况一：该结点p为分支结点 情况二：该结点p为叶子ABDEpCABpABDEp 后继为由左线索向上直到某个结点有左孩子或头结点为止 p-lchild为前驱;if（有右孩子）p-rchild为前驱;else/有左孩子无右孩子ABDEp6.6树与森林v定义：树(tree)是n(n=0)个结点的有限集，在一棵非空树T有：l有且仅有一个特定的结点，称为树的根(root)l当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,T
43、m，其中每一个集合本身又是一棵树，称为根的子树(subtree)v特点：l树中至少有一个结点根l树中各子树是互不相交的集合6.6.1 树的存储结构1.双亲表示法l实现：定义结构数组存放树的结点，每个结点含两个域：u数据域：存放结点本身信息u双亲域：指示本结点的双亲结点在数组中位置abcdefhgi bdefghi c01124440a-16012345789dataparent-1表示无双亲如何找孩子结点#define MaxNodeNum 100typedef struct DataType data;int parent;Parentlist;typedef struct Parentli
44、st elemMaxNodeNum;int n;/*树中当前的结点数目*/ParentTree;2.孩子表示法l多重链表：每个结点有多个指针域，分别指向其子树的根u结点同构：结点的指针个数相等，为树的度Du结点不同构：结点指针个数不等，为该结点的度ddata child1 child2 .childDdata degree child1 child2 .childdabcdefhgi6012345789acdefghibdata firstchild1 2 3 4 8 6 7 5如何找双亲结点l孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子结点：type
45、def struct ChildNode int child;/该结点在表头数组中下标 struct ChildNode *nextchild;/指向下一孩子结点 ;表头结点：typedef struct datatype data;/数据域 struct ChildNode *firstchild;/指向第一个孩子结点 NodeType;NodeType tMAXNODE;501234678acdefghibdatafirstchild 1 2 348 6 7 5-101124440parentabcdefhgi3.带双亲的孩子链表4.孩子兄弟表示法（二叉树表示法）l实现：用二叉链表作树的存
46、储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点typedef struct TreeNode datatype data;struct TreeNode *lchild,*nextsibling;NodeType,*CSTree;abcdefhgi a b c d e f g h itypedef struct TreeNode datatype data;struct TreeNode *lchild,*nextsibling;NodeType,*CSTree;l特点u操作容易u破坏了树的层次6.6.2树、森林与二叉树转换ACBED树ABCDE二叉树 A B C
47、D E A B C D E A B C D E 对应存储存储解释解释v将树转换成二叉树l加线：在兄弟之间加一连线l抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系l旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空v将二叉树转换成树l加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来l抹线：抹掉原二叉树中双亲与右孩子之间的连线l调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDE
48、FGHIABCDEFGHIABCDEFGHIv森林转换成二叉树l将各棵树分别转换成二叉树l将每棵树的根结点用线相连l以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJv二叉树转换成森林l抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树l还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6.6.3树和森林的遍历1 树的遍历v遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，
49、即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列v常用方法l先根（序）遍历l后根（序）遍历l按层次遍历ABDEFGI先序遍历：ABE F I Gl先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树根根 子树子树B 子树子树D A根根 BID根根 子树子树E 子树子树F 子树子树GE根根 子树子树IF根根 根根 GD根根 l后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点ABDEFGI后序遍历：E I F GB D子树子树B 子树子树D 根根 根根ID子树子树E 子树子树F 子树子树G 根根E子树子树I 根根F 根根GAB 根根 根根AABDEFGI层次遍历：ABD
50、E F G Il按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点第1层第2层第3层第4层为什么没有中序遍历？ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNOABCDEFGHIJKLMNO例树：对应二叉树：先序遍历：ABE F I GCDHJ KL NOM中序遍历：E I F G B C J K N O L M H D A树的先序遍历与对应二叉树的先序遍历结果相同！树的后序遍历与对应二叉树的中序遍历结果相同！2森林的遍历v常
