第六章01(ldq)2

1、数 据 结 构 c语言描述data structure specification on c 数据结构数据结构 线性结构：线性表、栈、队列、串线性结构：线性表、栈、队列、串 非线性结构：至少存在一个数据元素有不非线性结构：至少存在一个数据元素有不止一个直接前驱或后继（树或图等）止一个直接前驱或后继（树或图等） 第六章第六章 树和二叉树树和二叉树 6.1 树的定义与基本术语树的定义与基本术语 1树的基本概念树的基本概念 树：树：n（n0）个个结点结点的有限的有限集合集合。当。当n n0 0时，称为空树；任意一时，称为空树；任意一棵非空树满足以下条件：棵非空树满足以下条件： 有且仅有一个特定的称为

2、有且仅有一个特定的称为根根(root)的结点；的结点； 当当n n1 1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m m（m0m0）个个互不相互不相交交的有限集合的有限集合t1,t2,t1,t2, ,tm ,tm，其中每个集合又是一棵树，并称为这个其中每个集合又是一棵树，并称为这个根结点的根结点的子树子树(subtree) 。 每棵子树的根结点有且仅有一个直接前驱，但可以有每棵子树的根结点有且仅有一个直接前驱，但可以有0 0个或多个直个或多个直接后继。接后继。树的定义是采用树的定义是采用递归递归方法方法efbagklmhijcdan=1的树的树n1的树的树t1t2t3(a

3、) 一棵树结构一棵树结构 (b)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 acbgfedhiacbgfdacbgfdebacgdefhia（b（d，e（h，i），），f），），c（g）（2） 文氏图表示法文氏图表示法（3）广义表表示法）广义表表示法abcdiefgh2树的图解表示法树的图解表示法（1） 树型表示法树型表示法hiefdbcga（4）凹入表示法）凹入表示法abcdiefgh结点：结点：包含一个数据元素及若干指向其他包含一个数据元素及若干指向其他结点的分支信息。结点的分支信息。结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。树的度：树的度：树中各结

4、点度的最大值。树中各结点度的最大值。cgbdefklhmija3树的相关术语树的相关术语叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。cgbdefklhmija孩子、双亲：孩子、双亲： 一个结点的直接后继称为该结点的孩子结点；一个结点的直接后继称为该结点的孩子结点； 一个结点的直接前驱称为该结点的双亲结点。一个结点的直接前驱称为该结点的双亲结点。兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。 cgbdefklhmija祖先、子孙：祖先、子孙

5、：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到到结点结点y，那么那么x就称为就称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。cgbdefklhmija路径：路径：如果树的结点序列如果树的结点序列n1, n2, , nk有如下关系：结点有如下关系：结点ni是是ni+1的双亲（的双亲（1=idata); /*访问根结点访问根结点*/ preorder(root -lchild); /*先序遍历左子树先序遍历左子树*/ preorder(root -rchild); /*先序遍历右子树先序遍历右子树*/ 2二叉树的递归遍历算法二叉树的递归遍历算法void inorder(bi

6、tree root) /*中序遍历二叉树中序遍历二叉树, root为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的指针*/ if (root! =null) inorder(root -lchild); /*中序遍历左子树中序遍历左子树*/ visit(root -data); /*访问根结点访问根结点*/ inorder(root -rchild); /*中序遍历右子树中序遍历右子树*/ （2） 中序中序遍历遍历 图：中序遍历二叉树的递归过程图：中序遍历二叉树的递归过程 abdce(a) 二叉树的遍历走向bd第一次经过第二次经过第三次经过(b) 遍历中三次经过结点的情形v

7、oid postorder(bitree root) /* 后序遍历二叉树，后序遍历二叉树， root为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的指针*/ if(root! =null) postorder(root -lchild); /*后序遍历左子树后序遍历左子树*/ postorder(root -rchild); /*后序遍历右子树后序遍历右子树* / visit(root -data); /*访问根结点访问根结点*/ （3） 后序后序遍历遍历 （1）输出二叉树中的结点）输出二叉树中的结点 （2）输出二叉树中的叶子结点）输出二叉树中的叶子结点 （3）统计叶子结

8、点数目）统计叶子结点数目 （4）建立二叉链表方式存储的二叉树）建立二叉链表方式存储的二叉树 （5）求二叉树的高度）求二叉树的高度 （6）按树状打印二叉树）按树状打印二叉树以上操作可以通过对以上操作可以通过对二叉树遍历二叉树遍历来完成，一方面要重点理解来完成，一方面要重点理解访访问根节点问根节点操作的含义，另一方面要注意对具体的实现时是否要操作的含义，另一方面要注意对具体的实现时是否要考虑考虑遍历的次序遍历的次序选择的要求。选择的要求。3遍历算法应用遍历算法应用 （1）输出二叉树中的结点输出二叉树中的结点 遍历算法将走遍二叉树中的每一个结点，故输出二叉树中的遍历算法将走遍二叉树中的每一个结点，故

9、输出二叉树中的结点并无次序要求，因此可用结点并无次序要求，因此可用三种遍历中的任何一种算法完成。三种遍历中的任何一种算法完成。 void preorder(bitree root) /* 先序遍历输出二叉树结点先序遍历输出二叉树结点, root为指向二叉树根结点的指针为指向二叉树根结点的指针 */ if (root! =null) printf (root -data); /* 输出根结点输出根结点 */ preorder(root -lchild); /* 先序遍历左子树先序遍历左子树 */ preorder(root -rchild); /* 先序遍历右子树先序遍历右子树 */ （2）输出

10、二叉树中的叶子结点输出二叉树中的叶子结点 输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试测试，看是否有满足叶子结点的条件，如果满足则进行输出。看是否有满足叶子结点的条件，如果满足则进行输出。void preorder(bitree root) /* 先序遍历输出二叉树中的叶子结点先序遍历输出二叉树中的叶子结点, root为指向二叉树根结点的指针为指向二叉树根结点的指针 */ if (root! =null) if (r

11、oot -lchild=null & root -rchild=null) printf (root -data); /* 输出叶子结点输出叶子结点 */ preorder(root -lchild); /* 先序遍历左子树先序遍历左子树 */ preorder(root -rchild); /* 先序遍历右子树先序遍历右子树 */ （3）统计叶子结点数目）统计叶子结点数目 方法一：方法一： 统计二叉树中的叶子节点数目并无次序要求，因此可用三种统计二叉树中的叶子节点数目并无次序要求，因此可用三种遍历算法的任何一种完成，只需将访问操作具体变为判断是否为遍历算法的任何一种完成，只需将访问操作具体变

12、为判断是否为叶子节点，如果是叶子节点，则进行统计即可。叶子节点，如果是叶子节点，则进行统计即可。/* leafcount是保存叶子结点数目的全局变量是保存叶子结点数目的全局变量, 调用之前初始化值为调用之前初始化值为0 */void leaf(bitree root) if(root! =null) leaf(root-lchild); leaf(root-rchild); if (root -lchild=null & root -rchild=null) leafcount+; 方法二：方法二： 采用递归算法，如果是空树，返回采用递归算法，如果是空树，返回0；如果只有一个结点，；如果只有一

13、个结点，返回返回1；否则为左、右子树的叶子结点数之和。；否则为左、右子树的叶子结点数之和。 int leaf(bitree root) int leafcount; if(root=null) leafcount =0; else if(root-lchild=null)&(root-rchild=null) leafcount =1; else leafcount =leaf(root-lchild)+leaf(root-rchild); /* 叶子数为左右子树的叶子数目之和叶子数为左右子树的叶子数目之和 */ return leafcount; （4）建立二叉链表方式存储的二叉树）建立二叉

14、链表方式存储的二叉树 给定一棵二叉树，可以得到它的遍历序列；反过来，给定一棵二叉给定一棵二叉树，可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，也可以创建相应的二叉链表。树的遍历序列，也可以创建相应的二叉链表。 这里所说的遍历序列是一这里所说的遍历序列是一种种“扩展的遍历序列扩展的遍历序列”。在通常的遍历序列中，均忽略空子树，而在扩。在通常的遍历序列中，均忽略空子树，而在扩展的遍历序列中，必须用特定的元素表示空子树。展的遍历序列中，必须用特定的元素表示空子树。例如，下面左图中二例如，下面左图中二叉树的叉树的“扩展先序遍历序列扩展先序遍历序列”如右图所示（如右图所示（其中用小圆点表示空子

15、树）其中用小圆点表示空子树）： ab.df.g.c.e.h. cehgfbdaa e bc d12g f abgcdefabc de g f 空格代表不存在的左、右子树空格代表不存在的左、右子树建立二叉树的二叉链表过程建立二叉树的二叉链表过程：(按先序序列按先序序列)按下列次序读入字符按下列次序读入字符:用用“扩展先序遍历序列扩展先序遍历序列”创建二叉链表创建二叉链表:void createbitree(bitree *bt)char ch; scanf(&ch); if(ch=.) *bt=null; else *bt=(bitree)malloc(sizeof(bitnode); (*bt

16、)-data=ch; createbitree(&(*bt)-lchild); createbitree(&(*bt)-rchild); 二叉树建立的演示二叉树建立的演示 设函数表示二叉树设函数表示二叉树bt的高度，则递归定义如下的高度，则递归定义如下: 若若bt为空，则高度为为空，则高度为0； 若若bt非空，其高度应为其左右子树高度的最大值加非空，其高度应为其左右子树高度的最大值加1， 如下图所示。如下图所示。二叉树的高度二叉树的高度(深度深度)为二叉树中结点层次的最大值，即结点的层次自根结为二叉树中结点层次的最大值，即结点的层次自根结点起递推。设根结点为第点起递推。设根结点为第1层的结点，

17、所有层的结点，所有h层的结点的左右孩子结点在层的结点的左右孩子结点在h+1层，则可以通过先序遍历计算二叉层，则可以通过先序遍历计算二叉树中的每个结点的层次，其中最大树中的每个结点的层次，其中最大值即为二叉树的高度。值即为二叉树的高度。 （5）求二叉树的高度）求二叉树的高度bt左子树右子树hlhrhighmax(hlhr)lint posttreedepth(bitree bt) /* 后序遍历求二叉树的高度递归算法后序遍历求二叉树的高度递归算法 */ int hl, hr, max; if(bt! =null) hl=posttreedepth(bt-lchild); /* 求左子树的深度求左

18、子树的深度 */ hr=posttreedepth(bt-rchild); /* 求右子树的深度求右子树的深度 */ max=hlhr?hl: hr; /* 得到左、得到左、 右子树深度较大者右子树深度较大者*/ return(max+1); /* 返回树的深度返回树的深度 */ else return(0); /* 如果是空树，如果是空树， 则返回则返回0 */ （6） 按树状打印的二叉树按树状打印的二叉树 例：假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单例：假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母字母, 要求实现如下图所示打印结果。要求实现如下图所示打印结果

19、。 这实际是一个二叉树的横向显示问题：因为二叉树的横向显示应是二这实际是一个二叉树的横向显示问题：因为二叉树的横向显示应是二叉树竖向显示的叉树竖向显示的90旋转，又由于二叉树的横向显示算法一定是中序遍历旋转，又由于二叉树的横向显示算法一定是中序遍历算法，所以把横向显示的二叉树算法改算法，所以把横向显示的二叉树算法改为先右子树再根结点再左子树的为先右子树再根结点再左子树的rdl结构，结构， 实现算法如下：实现算法如下： abcdef输出caefdb void printtree(treenode boot, int nlayer) /* 按竖向树状打印的二叉树按竖向树状打印的二叉树 */ if(

20、boot= =null) return; printtree(boot-pright, nlayer+1); for(int i=0; ich); printtree(boot-pleft, nlayer+1); 若已知一棵二叉树的前序序列和中序序列，若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？能否唯一确定这棵二叉树呢？怎样确定？ 例如例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为：已知一棵二叉树的前序遍历序列和中序遍历序列分别为abcdefghi 和和bcaedghfi，如何构造该二叉树呢如何构造该二叉树呢? ? （见下图）（见下图）4由遍历序列确定二叉

21、树由遍历序列确定二叉树根据前序序列的第一个元素建立根结点；根据前序序列的第一个元素建立根结点；在中序序列中找到该元素，确定根结点的左右子树的中序序列；在中序序列中找到该元素，确定根结点的左右子树的中序序列； 在前序序列中确定左右子树的前序序列；在前序序列中确定左右子树的前序序列；由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。 已知一棵二叉树的前序序列和中序序列，已知一棵二叉树的前序序列和中序序列，构造构造该二叉树的该二叉树的过程过程如下：如下： 前序：前序：a b c d e f

22、g h i中序：中序：b c a e d g h f i前序：前序：b c中序：中序：b c b c d ef gh ia前序：前序： d e f g h i中序：中序： e d g h f iabcdefghi前序：前序：f g h i中序：中序：g h f i前序：前序： d e f g h i中序：中序： e d g h f iabcdefghiabcdefighagbcdfe（1 1）前序遍历）前序遍历算法的算法的执行轨迹执行轨迹5基于栈的递归消除基于栈的递归消除访问结点序列访问结点序列:a栈栈s内容内容:b d a b前序遍历的前序遍历的非递归非递归实现实现 adbc访问结点序列访问

23、结点序列:a栈栈s内容内容:b d aadbc d访问结点序列访问结点序列:a栈栈s内容内容:b d cadbcc（2 2） 中序遍历中序遍历二叉树的非递归算法二叉树的非递归算法 【算法思想算法思想】p p取二叉树根取二叉树根 while(pwhile(p | | 栈不空栈不空) p p向左前进直至不再有左子女，途经结点进栈；向左前进直至不再有左子女，途经结点进栈； 若栈不空，出栈一个元素至若栈不空，出栈一个元素至p p； 访问访问p p； p p前进至右子女；前进至右子女； 【递归过程递归过程】abdce(a) 二叉树的遍历走向bd第一次经过第二次经过第三次经过(b) 遍历中三次经过结点的情

24、形【算法实现算法实现1】中序遍历二叉树的非递归算法（中序遍历二叉树的非递归算法（直接实现栈操作直接实现栈操作）/* sm 表示栈，表示栈， top表示栈顶指针表示栈顶指针 */void inorder(bitree root) /* 中序遍历二叉树，中序遍历二叉树， bt为二叉树的根结点为二叉树的根结点 */ top=0; p=bt; do do while(p! =null) if (topm) return(overflow); top=top+1; stop=p; p=p-lchild ; /* 遍历左子树遍历左子树 */ if(top! =0) p=stop; top=top-1; v

25、isit(p-data); /* 访问根结点访问根结点 */ p=p-rchild; /* 遍历右子树遍历右子树 */ while(p! =null | top! =0) 【算法实现算法实现2】中序遍历二叉树的非递归算法（中序遍历二叉树的非递归算法（调用栈操作的函数调用栈操作的函数）void inorder（bitree root）/* 中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法 */ initstack (&s); p=root; while(p! =null | !isempty(s) if (p! =null) /* 根指针进栈，根指针进栈， 遍历左子树遍历左子树 */ pus

26、h(&s, p); p=p-lchild; else /*根指针退栈，根指针退栈， 访问根结点，访问根结点， 遍历右子树遍历右子树*/ pop(&s, &p); visit(p-data); p=p-rchild; （3） 后序遍历后序遍历二叉树的非递归算法二叉树的非递归算法【算法设计算法设计】判断刚访问过的结点判断刚访问过的结点q是不是当前栈顶结点是不是当前栈顶结点p的右孩子的右孩子 p无右孩子，此时应该访问根结点；无右孩子，此时应该访问根结点； 如如p的右孩子是刚被访问过的结点的右孩子是刚被访问过的结点q（表明（表明p的右子树已遍历的右子树已遍历过），此时也应该访问根结点。过），此时也应该

27、访问根结点。 除这两种情况外，均不应访问根，而是要继续进入右子树中。除这两种情况外，均不应访问根，而是要继续进入右子树中。【算法思想算法思想】 从根结点开始，只要当前结点存在，或者栈不空，则重复下面的从根结点开始，只要当前结点存在，或者栈不空，则重复下面的步骤：步骤： 从当前结点开始，进栈并走左子树，直到左子树为空；从当前结点开始，进栈并走左子树，直到左子树为空； 如果栈顶结点的右子树为空，或者栈顶结点的右孩子为刚访问如果栈顶结点的右子树为空，或者栈顶结点的右孩子为刚访问过的结点，则退栈并访问，然后将当前结点指针置空；过的结点，则退栈并访问，然后将当前结点指针置空； 否则，走右子树。否则，走右

28、子树。【算法描述算法描述】void postorder（bitree root） bitnode * p, *q； bitnode *s； int top=0; q=null; p=root; s=（bitnode*）malloc（sizeof（bitnode*）*num）; /* num为预定义的常数为预定义的常数 */ while(p! =null | top!kg-*2=0) while(p! =null) top=+; stop=p; p=p-lchild; /* 遍历左子树遍历左子树 */ if(top0) p=stop; if(p-rchild=null) |(p-rchild=q

29、) /* 无右孩子，无右孩子， 或右孩子已遍历过或右孩子已遍历过 */ visit(p-data); /* 访问根结点访问根结点* / q=p; /* 保存到保存到q， 为下一次已处理结点前驱为下一次已处理结点前驱 */ top-; p=null; else p=p-rchild; free(s); （1 1）问题）问题：如何保存二叉树的：如何保存二叉树的遍历运算遍历运算的结果？的结果？ 或如何得到二叉树中结点在遍历序列中的或如何得到二叉树中结点在遍历序列中的前驱和后继信息前驱和后继信息？（2 2）方法）方法：a a、将二叉树、将二叉树遍历一遍遍历一遍，在遍历过程中便可得到结点的前，在遍历过程

30、中便可得到结点的前驱和后继，但这种动态访问浪费时间；驱和后继，但这种动态访问浪费时间； b b、充分、充分利用利用二叉链表中的二叉链表中的空链域空链域，将遍历过程中结点的，将遍历过程中结点的前驱、前驱、 后继信息保存下来。后继信息保存下来。 具体办法具体办法：若结点有左子树，则其：若结点有左子树，则其lchildlchild域指向其域指向其左孩子左孩子，否则否则lchildlchild域指向其域指向其前驱结点前驱结点；若结点有右子树，则其；若结点有右子树，则其rchildrchild域指向域指向其其右孩子右孩子，否则，否则rchildrchild域指向其域指向其后继结点后继结点。为了区分孩子结

31、点和前驱、。为了区分孩子结点和前驱、后继结点，为结点结构增设后继结点，为结点结构增设两个标志域两个标志域，如下所示：，如下所示： 6.4 线索二叉树线索二叉树1基本概念基本概念其中：其中： 0 lchild域指示结点的左孩子域指示结点的左孩子1lchild域指示结点的遍历前驱域指示结点的遍历前驱0 rchild域指示结点的右孩子域指示结点的右孩子1 rchild域指示结点的遍历后继域指示结点的遍历后继 线索线索：指向前驱和后继结点的：指向前驱和后继结点的指针指针叫做线索；叫做线索；线索链表线索链表：以这种结构组成的：以这种结构组成的二叉链表二叉链表作为二叉树的作为二叉树的存储结构存储结构，叫做

32、线索，叫做线索链表；链表；线索化线索化：对二叉树以某种次序进行遍历并且加上线索的：对二叉树以某种次序进行遍历并且加上线索的过程过程叫做线索化；叫做线索化；线索二叉树线索二叉树：线索化了的二叉树线索化了的二叉树称为线索二叉树称为线索二叉树。 lchildltagdatartagrchild（3）概念：）概念： （1 1）线索化二叉树的）线索化二叉树的实质实质： 将二叉链表中的将二叉链表中的空指针域空指针域填上相应结点的填上相应结点的遍历前驱或后继结遍历前驱或后继结点的地址点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此，线索化的过程

33、即为在遍历过程中到。因此，线索化的过程即为在遍历过程中修改空指针域修改空指针域的过程。的过程。 （2 2）线索化二叉树的）线索化二叉树的方式方式： 对于同一棵二叉树按照对于同一棵二叉树按照不同的次序不同的次序进行线索化，可以得到进行线索化，可以得到不不同的线索二叉树同的线索二叉树，包括先序、中序和后序线索二叉树。，包括先序、中序和后序线索二叉树。2二叉树的线索化二叉树的线索化abcdefgh(a) 二叉树abcdefgh(b )先序线索 二叉树acdefgh(c) 中序线索二叉树abcdefgh(d) 后序线索 二叉树bnullnullnullnull（3 3）中序线索化二叉树的）中序线索化二

34、叉树的算法算法： 中序线索化采用中序递归遍历算法框架中序线索化采用中序递归遍历算法框架 加线索操作就是访问结点操作加线索操作就是访问结点操作 加线索操作需要利用刚访问过结点与当前结点的关系，因此设置一加线索操作需要利用刚访问过结点与当前结点的关系，因此设置一个指针个指针prepre，始终记录刚访问过的结点，其操作如下：，始终记录刚访问过的结点，其操作如下： 如果当前遍历结点如果当前遍历结点rootroot的左子域为空，则让左子域指向的左子域为空，则让左子域指向prepre 如果前驱如果前驱prepre的右子域为空，则让右子域指向当前遍历结点的右子域为空，则让右子域指向当前遍历结点rootroo

35、t 为下次做准备，当前访问结点为下次做准备，当前访问结点rootroot作为下一个访问结点的前驱作为下一个访问结点的前驱preprevoid inthread(bitree root) if (root! =null) inthread(root-lchild); /* 线索化左子树线索化左子树 */ if (root-lchild=null) root-ltag=1; root-lchild=pre; / *置前驱线索置前驱线索 */ if (pre! =null& pre-rchild=null) /* 置后继线索置后继线索 */ pre- rchild=root; pre=root； i

36、nthread(root-rchild); /*线索化右子树线索化右子树*/ （4）中序线索化二叉树）中序线索化二叉树动态演示动态演示 （1） 找结点的找结点的中序前驱结点中序前驱结点 分析：分析：根据线索二叉树的基本概念和存储结构可知，对于结点根据线索二叉树的基本概念和存储结构可知，对于结点p， 当当p-ltag=1时，时，p-lchild指向指向p的前驱；的前驱； 当当p-ltag=0时，时，p-lchild指向指向p的左孩子。由中序遍历的的左孩子。由中序遍历的规律可知，作为根规律可知，作为根p的前驱结点，它是中序遍历的前驱结点，它是中序遍历p的左子树时访问的最后的左子树时访问的最后一个结

37、点，即一个结点，即左子树的左子树的“最右下端最右下端”结点结点。3找前驱、找前驱、 后继结点后继结点 在中序线索二叉树中在中序线索二叉树中 查找算法：查找算法：void inpre(bitnode *p, bitnode *pre)/* 在中序线索二叉树中查找在中序线索二叉树中查找p的中序前驱的中序前驱, 并用并用pre指针返回结果指针返回结果 */ if(p-ltag=1) pre= p-lchild; /*直接利用线索直接利用线索*/ else /* 在在p的左子树中查找的左子树中查找“最右下端最右下端”结点结点 */ for(q= p-lchild; q-rtag=0; q=q-rchi

38、ld); pre=q; 找结点的中序前驱结点找结点的中序前驱结点动态演示动态演示： （2 2）找结点的）找结点的中序后继结点中序后继结点 分析：分析：对于结点对于结点p p，若要找其后继结点，若要找其后继结点， 当当p-rtag=1p-rtag=1时，时，p-p-rchildrchild即为即为p p的后继结点；的后继结点； 当当p-rtag=0p-rtag=0时，时， 说明说明p p有右子树，此时有右子树，此时p p的中序后继结点的中序后继结点即为其右子树的即为其右子树的“最左下端最左下端”的结点。的结点。 查找算法：查找算法：void insucc(bitnode *p, bitnode

39、*succ) /*在中序线索二叉树中查找在中序线索二叉树中查找p的中序后继结点，的中序后继结点， 并用并用succ指针返回结果指针返回结果*/ if (p-rtag=1) succ= p- rchild; /*直接利用线索直接利用线索*/ else /*在在p的右子树中查找的右子树中查找“最左下端最左下端”结点结点*/ for(q= p-rchild; q-ltag=0 ; q=q-lchild ); succ=q; 找结点的中序后继结点找结点的中序后继结点动态演示动态演示： 遍历线索树的问题可以分为遍历线索树的问题可以分为两步两步：第一步第一步是求出某种遍历次是求出某种遍历次序下第一个被访问

40、结点，序下第一个被访问结点，然后然后连续求出刚访问结点的后继结点，直连续求出刚访问结点的后继结点，直至所有的结点均被访问。至所有的结点均被访问。（1）在中序线索树上求中序遍历的）在中序线索树上求中序遍历的第一个结点第一个结点 bitnode *infirst (bitree bt) bitnode *p = bt; if ( ! p ) return (null) while (p-ltag = 0) p=p-lchild ; return p 4遍历中序线索树遍历中序线索树（2）遍历遍历中序二叉线索树中序二叉线索树 void tinorder (bitree bt) bitnode *p;

41、p=infirst ( bt ); while ( p ) visit ( p ) ; p = innext (p); 通过调用通过调用infirst和和 innext，可以实现对中序线索树的，可以实现对中序线索树的中序遍历，且不需要使用递归栈。中序遍历，且不需要使用递归栈。 （1 1） 插入结点运算插入结点运算 在中序线索二叉树上插入新结点可分两种情况：要么作某结点的在中序线索二叉树上插入新结点可分两种情况：要么作某结点的左左孩子、要么作某结点的孩子、要么作某结点的右右孩子。孩子。 在后种情况中，用在后种情况中，用insnode(bitnodeinsnode(bitnode * *p, p,

42、 bitnodebitnode * *r)r)表示在线表示在线索二叉树中插入索二叉树中插入r r所指向的结点，做所指向的结点，做p p所指结点的右孩子。此时有两种所指结点的右孩子。此时有两种情况：情况： 若结点若结点p p的右孩子为空的右孩子为空，则插入结点，则插入结点r r的过程很简单。原来的过程很简单。原来p p的后的后继变为继变为r r的后继，结点的后继，结点p p变为变为r r的前驱，结点的前驱，结点r r成为成为p p的右孩子，结点的右孩子，结点r r的的插入对插入对p p原来的后继结点没有任何的影响。插入过程如下图所示。原来的后继结点没有任何的影响。插入过程如下图所示。 5插入、删

43、除运算插入、删除运算 以中序线索二叉树为例以中序线索二叉树为例图：结点的右孩子为图：结点的右孩子为空空时的插入操作时的插入操作 (a) 插入前(b) 插入后prpr 若若p的右孩子不为空的右孩子不为空，则插入后，则插入后，p的右孩子变为的右孩子变为r的右孩子结点，的右孩子结点， p变为变为r的前驱结点，的前驱结点，r变为变为p的右孩子结点，这时还需要修改原来的右孩子结点，这时还需要修改原来p的右的右子树中子树中“最左下端最左下端”结点的左指针域，使它由原来的指向结点结点的左指针域，使它由原来的指向结点p变为指变为指向结点向结点r。插入过程如下图所示。插入过程如下图所示。 图：结点的右孩子图：结

44、点的右孩子非空非空时的插入操作时的插入操作prpr(a) 插入前(b) 插入后算法描述：算法描述：void insnode(bitnode *p, bitnode *r)if(p-rtag=1) /* p无右孩子无右孩子 */ r-rchild=p-rchild; /* p的后继变为的后继变为r的后继的后继 */ r-rtag=1; p-rchild=r; /* r成为成为p的右孩子的右孩子 */ r-lchild=p; /* p变为变为r的前驱的前驱 */ r-ltag=1; else /* p有右孩子有右孩子 */ s=p-rchild; while(s-ltag=0) s=s-lchil

45、d; /* 查找查找p结点的右子树的结点的右子树的“最左下端最左下端”结点结点 */ r-rchild=p-rchild; /* p的右孩子变为的右孩子变为r的右孩子的右孩子 */ r-rtag=0; r-lchild=p; /* p变为变为r的前驱的前驱 */ r-ltag=1; p-rchild=r; /* r变为变为p的右孩子的右孩子 */ s-lchild=r; /* r变为变为p原来右子树的原来右子树的“最左下端最左下端”结点的前驱结点的前驱 */ （2 2） 删除结点运算删除结点运算 图：删除线索二叉树中结点的过程图：删除线索二叉树中结点的过程 prpr(a)删除前(b)删除后6.

46、5 树、森林和二叉树的关系树、森林和二叉树的关系 （1 1）双亲表示法双亲表示法 用一组连续的空间来存储树中的结点，在保存每个结点的同时附用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下：设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下： dataparent数据数据 双亲双亲 1树的存储结构树的存储结构data：存储树中结点的数据信息：存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标：存储该结点的双亲在数组中的下标双亲表示法的形式说明如下：双亲表示法的形式说明如下： define max 100ty

47、pedef struct tnode datatype data; int parent; tnode; 一棵树可以定义为一棵树可以定义为: typedef struct tnode treemax; int nodenum; /*结点数结点数*/parenttree; 下标下标 data parent012345678 a - -1 b 0 c 0 d 1 e 1 f 1 g 2 h 2 i 4 如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？acbhfedgiacbhfedgi如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？下标下标 data parentfirstchil

48、d 1 3 6 -1 8 -1-1-1-1012345678 a - -1 b 0 c 0 d 1 e 1 f 1 g 2 h 2 i 4 下标下标 data parent rightsib- -1 2- -1 4 5 - -17- -1- -1012345678 a - -1 b 0 c 0 d 1 e 1 f 1 g 2 h 2 i 4 acbhfedgi如何查找如何查找兄弟兄弟结点？时间性能？结点？时间性能？ （2 2） 孩子表示法孩子表示法 方法：把每个结点的孩子结点排列起来，构成一个单链表，方法：把每个结点的孩子结点排列起来，构成一个单链表， 称称为孩子链表。为孩子链表。n n个结点

49、共有个结点共有n n个孩子链表（叶子结点的孩子链表为空个孩子链表（叶子结点的孩子链表为空表），而表），而n n个结点的数据和个结点的数据和n n个孩子链表的头指针又组成一个顺序表。个孩子链表的头指针又组成一个顺序表。 存储结构定义如下：存储结构定义如下： typedef struct childnode /* 孩子链表结点的定义孩子链表结点的定义 */ int child; /* 该孩子结点在线性表中的位置该孩子结点在线性表中的位置 */ struct childnode *next; /* 指向下一个孩子结点的指针指向下一个孩子结点的指针 */childnode;typedef struct

50、 /* 顺序表结点的结构定义顺序表结点的结构定义 */ datatype data; /* 结点的信息结点的信息 */ childnode *firstchild ; /* 指向孩子链表的头指针指向孩子链表的头指针 */datanode;typedef struct /* 树的定义树的定义 */ datanode nodesmax; /* 顺序表顺序表 */ int root, num; /* 该树的根结点在线性表中的位置和该树的结点个数该树的根结点在线性表中的位置和该树的结点个数 */ childtree; 012345678下标下标 data firstchild a b c d e f

51、g h i 如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？12 345 7 68 acbhfedgi a b c d e f g h i 012345678下标下标 data firstchild12 345 7 68 如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？acbhfedgi012345678 a - -1 b 0 c 0 d 1 e 1 f 1 g 2 h 2 i 4 data parent firstchild12 345 7 68 acbhfedgi结点结构：结点结构：firstchild data rightsibdata：数据域，存储该结点的数据信息；数据

52、域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；指针域，指向该结点第一个孩子；rightsib：指针域，指向该结点的右兄弟结点。指针域，指向该结点的右兄弟结点。 存储结构定义：存储结构定义： typedef struct csnode datatype data; /*结点信息结点信息*/ struct csnode *firstchild, *nextsibling; /*第一个孩子第一个孩子, 下一个兄弟下一个兄弟*/csnode, *cstree; （3）孩子兄弟表示法孩子兄弟表示法某结点的第一个孩子是惟一的某结点的第一个孩子是惟一的某结点的右兄弟是惟一的某

53、结点的右兄弟是惟一的设置两个分别指向该结点的设置两个分别指向该结点的第一个孩子和右兄弟的指针第一个孩子和右兄弟的指针acbhfedgi a b c d e f g h i如何查找如何查找兄弟兄弟结点？时间性能？结点？时间性能？ a b c d e f g h i如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？acbhfedgi是哪些树结构的是哪些树结构的存储结构存储结构? ?树和二叉树之间具有对应关系树和二叉树之间具有对应关系aebcfdga bced f gabcdefg（1）树转换为二叉树）树转换为二叉树 2树、森林与二叉树的相互转换树、森林与二叉树的相互转换 树和二叉树之间的对应

54、关系：树和二叉树之间的对应关系： 树：兄弟关系树：兄弟关系二叉树：双亲和右孩子二叉树：双亲和右孩子 树：双亲和长子树：双亲和长子二叉树：双亲和左孩子二叉树：双亲和左孩子aebcfdgabcdefg 转换方法：转换方法：加线加线树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。 去线去线对树中的每个结点，只保留它与第一个孩子结点之间的连对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。线，删去它与其它孩子结点之间的连线。 层次调整层次调整以根结点为轴心，将树顺时针转动一定的角度，使之以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。层次分明

55、。 1.兄弟加线兄弟加线.abcdefg 转换分解图如下：转换分解图如下：2.保留双亲与第一孩子连线保留双亲与第一孩子连线,删去与其他孩子的连线删去与其他孩子的连线.abcdefg 1.兄弟加线兄弟加线.3.顺时针转动顺时针转动,使之层次分明使之层次分明.2.保留双亲与第一孩子连线保留双亲与第一孩子连线,删去与其他孩子的连线删去与其他孩子的连线. 1.兄弟加线兄弟加线.abcdefg3.顺时针转动顺时针转动,使之层次分明使之层次分明.2.保留双亲与第一孩子连线保留双亲与第一孩子连线,删去与其他孩子的连线删去与其他孩子的连线. 1.兄弟加线兄弟加线.gdabecf 树与二叉树的对应树与二叉树的对应 dabce对应abcdeabcdeeabcdabcde存储存储解释解释 （2）森林转换为二叉树）森林转换为二叉树 转换方法转换方法 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树； 从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是