数据结构章树和叉树ppt课件

1、第第6章章 树和二叉树树和二叉树Tree & Binary Tree数据构造课程的内容数据构造课程的内容第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 内排序内排序目目 录录目录6.1 树的定义和根本术语16.2 二叉树26.3 遍历二叉树和线索二叉树36.4 树和森林46.5 赫夫曼树及其运用5786.1 树的根本概念树的根本概念特点：非线性构造，一个直接前驱，但能够有多个直接后继。特点：非线性构造，一个直接前驱，但能够有多

2、个直接后继。注注1：过去许多书籍中都定义树为：过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树的说法，但如今树的定义已修正。树的说法，但如今树的定义已修正。注注2：树的定义具有递归性，即：树的定义具有递归性，即“树中还有树。树中还有树。由由n n个个(n0)(n0)结点组成的有限集合结点组成的有限集合T T，有且仅有一个结点称为，有且仅有一个结点称为根根rootroot，当，当n1n1时，其他的结点分为时，其他的结点分为m(m0)m(m0)个互不相交的有个互不相交的有限集合限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根。每个集合本身又是棵树，被称作这个

3、根的子树的子树 。ABCGEIDHFJFLK一对多一对多1:n1:n，有多个直接后继如家谱树、目录树，有多个直接后继如家谱树、目录树等等，但只需一个根结点，且子树之间互不相交。等等，但只需一个根结点，且子树之间互不相交。 特点：特点：树的树的5种表示法：种表示法：v 图形表示法图形表示法v 嵌套集合表示法嵌套集合表示法v 广义表表示法广义表表示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法图形表示法图形表示法教师教师学生学生其他人员其他人员20212021级级 20212021级级 20212021级级20212021级级辽宁工程技术大学辽宁工程技术大学电气系电气系电信学院

4、电信学院外语系外语系叶子叶子根根子树子树嵌套集合表示法嵌套集合表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 商定：商定：根作为由子树森林组成的表的名字写在表的左边根作为由子树森林组成的表的名字写在表的左边又称目录表示法又称目录表示法data左孩子左孩子 右兄弟左孩子右兄弟表示法左孩子右兄弟表示法多叉树转为多叉树转为了二叉树了二叉树即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点孩子之间互称兄弟同一双亲下的同层结点孩子之间互称兄弟即双亲位

5、于同一层的结点但并非同一双亲即双亲位于同一层的结点但并非同一双亲即从根到该结点所经分支的一切结点即从根到该结点所经分支的一切结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJFLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集合棵不相交的树的集合 (例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换左为第一结点各子树从左至右有序，不能互换左为第一结点各子树可互换位置。结点各子树可互换位置

6、。树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJFLK一切结点度中的最大值一切结点度中的最大值Max各结点的度各结点的度指一切结点中最大的层数指一切结点中最大的层数Max各结点的层次各结点的层次问：右上图中的结点数问：右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点从根到该结点的层数根结点算第一层从根到该结点的层数根结点算第一层即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点也称为内部结点的结点也称为内部结点有几个直

7、接后继就是几度，亦称有几个直接后继就是几度，亦称“次数次数13133 34 46.2 二叉树二叉树为何要重点研讨每结点最多只需两个为何要重点研讨每结点最多只需两个 “叉叉 的树？的树？二叉树的构造最简单，规律性最强；二叉树的构造最简单，规律性最强；可以证明，一切树都能转为独一对应的二叉树，不可以证明，一切树都能转为独一对应的二叉树，不失普通性。失普通性。6.2.1 二叉树的定义二叉树的定义6.2.2 二叉树的性质二叉树的性质6.2.3 二叉树的存储构造二叉树的存储构造定义：是定义：是nn0个结点的有限集合，由一个根结点以及两棵个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右

8、子树的二叉树组成互不相交的、分别称为左子树和右子树的二叉树组成 。逻辑构造：逻辑构造： 一对二一对二1:2 根本特征根本特征: 每个结点最多只需两棵子树不存在度大于每个结点最多只需两棵子树不存在度大于2的结点；的结点； 左子树和右子树次序不能颠倒。左子树和右子树次序不能颠倒。 根本形状：根本形状：普通普通的树的树有几有几种？种？讨论讨论1 1：第：第i i层的结点数最多是多少？层的结点数最多是多少？ 利用二进制性质可轻利用二进制性质可轻松求出松求出 性质性质1: 1: 在二叉树的第在二叉树的第i i层上至多有层上至多有2i-12i-1个结点个结点i0i0。性质性质2: 2: 深度为深度为k k

9、的二叉树至多有的二叉树至多有2k-12k-1个结点个结点k0k0。再提问：第再提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，最多有多少个结点？的二叉树，最多有多少个结点？ 利用二进制性质可利用二进制性质可轻松求出轻松求出性质性质3: 3: 对于任何一棵二叉树，假设度为对于任何一棵二叉树，假设度为2 2的结点数有的结点数有n2n2个，那么叶子数个，那么叶子数n0n0必定为必定为n2n21 1 即即n0=n2+1n0=n2+1三式联立可得：三式联立可得： n0+n1+n2= n1+2n2 +1, n0+n1+n2= n1+2n2 +1, 即

10、即n0=n2+1n0=n2+1讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？3. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度为的二叉树的结点总数，最多为深度为的二叉树的结点总数，最多为 个。个。 ) )k-1 k-1 ) log2k ) log2k ) ) k k ) )k k1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度DCC课堂练习：

11、课堂练习：完全二叉树：深度为完全二叉树：深度为k k 的、有的、有n n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k k 的满二叉树中编号从的满二叉树中编号从1 1至至n n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树完全二叉树完全二叉树ABCGEIDHFJ为何要研讨为何要研讨这两种特殊这两种特殊方式？方式？满二叉树：一棵深度为满二叉树：一棵深度为k 且有且有2k -1个结点的二叉树。个结点的二叉树。 特点：每层都特点：每层都“充溢了结点充溢了结点解释：完全二叉树的特点是只需最后一层叶子不

12、满，解释：完全二叉树的特点是只需最后一层叶子不满，且全部集中在左边。但这其实是顺序二叉树的含义。且全部集中在左边。但这其实是顺序二叉树的含义。而图论中的而图论中的“完全二叉树是指完全二叉树是指n1=0的情况。的情况。满二叉树和完全二叉树有什么区别？满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-k-1 1层是满的，但最底层却允许在右边短少延续假设干个结点。层是满的，但最底层却允许在右边短少延续假设干个结点。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。证明：根据性质证明：根据性质2 2

13、，深度为，深度为k k的二叉树最多只需的二叉树最多只需2k-12k-1个结点，且个结点，且完全二叉树的定义是与同深度的满二叉树前面编号一样，即它完全二叉树的定义是与同深度的满二叉树前面编号一样，即它的总结点数的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，层满二叉树容量之间，即即 2k-1-1n2k-1 2k-1-1n2k-1 或或2k-1n2k2k-1n2k三边同时取对数，于是有：三边同时取对数，于是有：k-1log2nk k-1log2n0i0。性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有2k-12k-1个结点个结点k0k0。性质性质3: 3:

14、对于任何一棵二叉树，假设对于任何一棵二叉树，假设2 2度的结点数有度的结点数有n2n2个，那么叶子数个，那么叶子数n0n0必定为必定为n2n21 1 即即n0=n2+1n0=n2+1对于两种特殊方式的二叉树满二叉树和完全二叉树，对于两种特殊方式的二叉树满二叉树和完全二叉树，还特别具备以下还特别具备以下2 2个性质：个性质：2.2.一棵完全二叉树上有一棵完全二叉树上有10011001个结点，其中叶子结点的个数个结点，其中叶子结点的个数为为 个。个。 )250 )250 ) 254 ) 254 ) 501 ) 501 )505)5051. 1. 一棵有一棵有124124个叶子结点的完全二叉树，最多

15、有个叶子结点的完全二叉树，最多有 结点结点 ) 247 ) 247 ) 249 ) 249 ) 251 ) 251 ) ) 248248DC课堂练习：课堂练习：3. 3. 一棵完全二叉树中，结点个数为一棵完全二叉树中，结点个数为n n，那么编号最大的，那么编号最大的分支结点的编号是分支结点的编号是 6.2.3 6.2.3 二叉树的存储构造二叉树的存储构造一、顺序存储构造一、顺序存储构造按二叉树的结点按二叉树的结点“自上而自上而下、从左至右编号，用下、从左至右编号，用一组延续的存储单元存储。一组延续的存储单元存储。123456789问：顺序存储后能否复原成独一对应的二叉树外形？问：顺序存储后能否

16、复原成独一对应的二叉树外形？答：假设是完全答：假设是完全/满二叉树那么可以做到独一复原。满二叉树那么可以做到独一复原。 而且有规律：下标值为而且有规律：下标值为i的双亲，其左孩子的下标值必为的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为其右孩子的下标值必为2i1即性质即性质5 例如，对应例如，对应2的两个孩子必为的两个孩子必为4和和5,即即B的左孩子必是的左孩子必是D,右孩子必为右孩子必为E。T0T0普普通不用通不用讨论：不是完全二叉树怎样办？讨论：不是完全二叉树怎样办？答：一概转为完全二叉树！答：一概转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚

17、结点，其虚结点，其内容为空。内容为空。123456789.16ABECD缺陷：浪费空间；插入、删除不便缺陷：浪费空间；插入、删除不便 二、链式存储构造二、链式存储构造用二叉链表即可方便表示。用二叉链表即可方便表示。二叉树结点数据类型定义：二叉树结点数据类型定义：typedef struct node *tree_pointer;typedef struct node int data; tree_pointer left_child, right_child; node;普通从根结点开场存储。普通从根结点开场存储。相应地，访问树中结点时相应地，访问树中结点时也只能从根开场也只能从根开场注：假设

18、需求倒查某结点的注：假设需求倒查某结点的双亲，可以再添加一个双亲双亲，可以再添加一个双亲域直接前趋指针，将二域直接前趋指针，将二叉链表变成三叉链表。叉链表变成三叉链表。三叉链表三叉链表二叉树链式存储举例：二叉树链式存储举例： ABECD优点：不浪费空间；插入、删除方便优点：不浪费空间；插入、删除方便 所以，所以， 空指针数目空指针数目2n(n-1) =n+1个。个。证明：用二叉链表存储包含证明：用二叉链表存储包含n个结点的二叉树，结点个结点的二叉树，结点必有必有2n个链域见二叉链表数据类型阐明。个链域见二叉链表数据类型阐明。除根结点外，二叉树中每一个结点有且仅有一个双亲，除根结点外，二叉树中每

19、一个结点有且仅有一个双亲，意即每个结点地址占用了双亲的一个直接后继，意即每个结点地址占用了双亲的一个直接后继，n n个结点地址个结点地址共占用了共占用了n-1n-1个双亲的指针域。也就是说，只会有个双亲的指针域。也就是说，只会有n n1 1个结点个结点的链域存放指针。的链域存放指针。讨论：用二叉链表法讨论：用二叉链表法l_child, r_childl_child, r_child存储包存储包含含n n个结点的二叉树，结点的指针区域中会有多少个结点的二叉树，结点的指针区域中会有多少个空指针？个空指针？6.3.1 二叉树遍历的概念遍历定义遍历定义遍历用途遍历用途遍历方法遍历方法指按某条搜索道路遍

20、访每个结点且不反复指按某条搜索道路遍访每个结点且不反复又称周游。又称周游。它是树构造插入、删除、修正、查找和排它是树构造插入、删除、修正、查找和排序运算的前提，是二叉树一切运算的根底序运算的前提，是二叉树一切运算的根底和中心。和中心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后右先左后右 。Traversing Binary Tree6.3遍历二叉树和线索二叉树对对“二叉树而言，可以有三条收索途径：二叉树而言，可以有三条收索途径：1。先上后下的按层次遍历。先上后下的按层次遍历2。先左子树后右子树的遍历。先左子树后右子树的遍历3。先右子树后左子树的遍历。先右子树后左子树的遍历遍历规那

21、么遍历规那么v 二叉树由根、左子树、右子树构成，定义为二叉树由根、左子树、右子树构成，定义为D、 L、R以根结点为参照系以根结点为参照系注：注：“先、中、后的意思是指访问的结点先、中、后的意思是指访问的结点D D是先于子树出是先于子树出现还是后于子树出现。现还是后于子树出现。v假设限定先左后右，那么有三种实现方案：假设限定先左后右，那么有三种实现方案： DLR LDR LRD先序遍历先序遍历 中序遍历中序遍历 后序遍历后序遍历 ABGFKEDCH先序遍历序列：先序遍历序列：ABCDEFGHK中序遍历序列：中序遍历序列：BDCAEHGKF后序遍历序列：后序遍历序列：DCBHKGFEA例例1：先序

22、遍历的结果是：先序遍历的结果是：中序遍历的结果是：中序遍历的结果是：后序遍历的结果是：后序遍历的结果是： A B CD E口诀：口诀：DLR先序遍历，即先根再左再右先序遍历，即先根再左再右LDR中序遍历，即先左再根再右中序遍历，即先左再根再右LRD后序遍历，即先左再右再根后序遍历，即先左再右再根先序遍历二叉树算法：先序遍历二叉树算法：假设二叉树为空，那么空操作；否那么假设二叉树为空，那么空操作；否那么1访问根结点；访问根结点；2先序遍历左子树；先序遍历左子树；3先序遍历右子树；先序遍历右子树；中序遍历二叉树算法：中序遍历二叉树算法：假设二叉树为空，那么空操作；否那么假设二叉树为空，那么空操作；

23、否那么 1 中序遍历左子树；中序遍历左子树；2 访问根结点；访问根结点；3中序遍历右子树；中序遍历右子树；后序遍历二叉树算法：后序遍历二叉树算法：假设二叉树为空，那么空操作；否那么假设二叉树为空，那么空操作；否那么1后序遍历右子树；后序遍历右子树；2后序遍历左子树；后序遍历左子树；3访问根结点；访问根结点；+*A*/EDCB先序遍历结果先序遍历结果+ * * / A B C D E前缀表示法前缀表示法中序遍历结果中序遍历结果A / B * C * D + E中缀表示法中缀表示法后序遍历结果后序遍历结果A B / C * D * E +后缀表示法后缀表示法层次遍历结果层次遍历结果+ * E *

24、D / C A B例例2：用二叉树表示算术表达式：用二叉树表示算术表达式对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：假设将从前面的三种遍历算法可以知道：假设将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全一样的，或者说这三种从递归的角度看，这三种算法是完全一样的，或者说这三种遍历算法的访问途径是一样的，只是访问结点的时机不同。遍历算法的访问途径是一样的，只是访问结点的时机不同。从虚线的出发点到终点的途径从虚线的出发点到终点的途径上，每个结点经过上，每个结点经过3次。次。AFEDCBG第第1次经过时访问，是先序遍历次经过时访问，是先序遍历第第2次经过时访问，是

25、中序遍历次经过时访问，是中序遍历第第3次经过时访问，是后序遍历次经过时访问，是后序遍历2. 2. 二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率:O(n) /:O(n) /每个结点只访问一次每个结点只访问一次空间效率空间效率:O(n) /:O(n) /栈占用的最大辅助空栈占用的最大辅助空间间准确值：树深为准确值：树深为k k的递归遍历需求的递归遍历需求k+1k+1个辅助单元个辅助单元中序遍历二叉树的非递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e) /采用二叉链表存储构造，采用二叉链表存

26、储构造，Visit是对数据元素操作的运用函数。是对数据元素操作的运用函数。/中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitInitStackS；p=T；While (p|!StackEmpty(S) if(p) Push(S,p);p=p-lchild;/根指针进栈，遍历左子树根指针进栈，遍历左子树 else / /根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树Pop(S,p); if(!Visit(p-data) return ERROR;p=p-rchild; /else /while return O

27、K;/InOrderTraverse例：知一棵二叉树的中序序列和后序序列分别是例：知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和和 DECBHGFA，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部即由后序遍历特征，根结点必在后序序列尾部即A；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙即树的子孙即BDCE，其右部必全部是右子树的子孙即，其右部必全部是右子树的子孙即FHG；继而，根据后序中的继而，根据后序中的DECB子树可确定子树可确定B为为A的左孩子，根据的左孩子，

28、根据HGF子串可确定子串可确定F为为A的右孩子；以此类推。的右孩子；以此类推。中序遍历二叉树的非递归算法 void InOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;p=b;while (top-1 | p!=NULL) while (p!=NULL) /扫描扫描*p的一切左结点并进栈的一切左结点并进栈 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出栈出栈*p结点结点 printf(%c ,p-data); /访问之访问之 p=p-rchild; /扫描扫描*p的右孩子结点的右

29、孩子结点 知中序遍历：知中序遍历：B D C E A F H G知后序遍历：知后序遍历：D E C B H G F AB D C E F H GA D C EBFGHCD EABBACCD C E练习 1.一棵二叉树的先序序列为ABDCEF，中序序列为DBAECF，那么该二叉树的后序序列为 。 A)DBEFCA B)DEBFCA C)DFEBCA D)DBFECAA 2.一棵二叉树的后序序列为DABEC，中序序列为DEBAC，那么该二叉树的序序列为 。 A)ACBED B)DECAB C)DEABC D) CEDBAD 3.设n、m为一棵二叉树上的两个节点，在中序遍历时，n在m前的条件是 。

30、A)n在m右方 B)n是m的祖先 C)n在m左方 D) n是m子孙D假设某非空二叉树的先序序列和后序序列正好相反，那么该二叉树的形状？二叉树的形状是其高度等于节点个数假设某非空二叉树的先序序列和后序序列正好一样，那么该二叉树的形状？二叉树的形状是只需一个根节点同样的问题假设非空二叉树先序和中序序列一样或者相反，二叉树的形状？假设非空二叉树后序和中序序列一样或者相反，二叉树的形状？本人总结规律用空格字符表示用空格字符表示无孩子无孩子或指针或指针为空为空如何把二叉树存入电脑内？如何把二叉树存入电脑内？怎样建树？见教材怎样建树？见教材P131P131例例例：将下面的二叉树以二叉链表方式存入计算机内。

31、例：将下面的二叉树以二叉链表方式存入计算机内。思索思索1 1：输入结点时怎样表示：输入结点时怎样表示“无孩子？无孩子？思索思索2 2：以何种遍历方式来输入和建树？：以何种遍历方式来输入和建树？将二叉树按先序遍历次序输入：将二叉树按先序遍历次序输入：A B C D E G F (/n)以先序遍历最为适宜，以先序遍历最为适宜，让每个结点都能及时让每个结点都能及时被衔接到位。被衔接到位。字符串输完后该当再字符串输完后该当再加一特殊的终了符号加一特殊的终了符号(如如$)，由于，由于 无无法独一表示终了。法独一表示终了。建树算法：建树算法：Status CreateBiTree( BiTree &

32、;T ) /构造二叉树构造二叉树Tscanf(“%c,&ch);if( ch= )T=NULL; else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根结点生成根结点 CreateBiTree(T-lchild); /构造左子树构造左子树 CreateBiTree(T-rchild); /构造右子树构造右子树 return OK; /CreateBiTree输入序列：输入序列： A B C D E G F (1) 创建二叉树创建二叉树CreateBTNode(*b,*str) void C

33、reateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL;/*建立的二叉树初始时为空建立的二叉树初始时为空*/ ch=strj; while (ch!=0) /*str未扫描完时循环未扫描完时循环*/ switch(ch) case (:top+;Sttop=p;k=1; break; /*为左孩子结点为左孩子结点*/入栈入栈 case ):top-;break;出栈出栈 case ,:k=2; break; /*为孩子结点右结点为孩子结点右结点*/ d

34、efault:p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /*p为二叉树的根结点为二叉树的根结点*/ b=p; else /*已建立二叉树根结点已建立二叉树根结点*/ switch(k) case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+;ch=strj; 层次遍历层次遍历其过程是：其过程是：假设二叉树非空假设其高度为假设二叉树非空假设其高度为h，那么：，那么：1访问根结点第访问根结点第1层；层；2从左到右访

35、问第从左到右访问第2层的一切结点；层的一切结点；3从左到右访问第从左到右访问第3层的一切结点、层的一切结点、第、第h层的一切结点。层的一切结点。 A B C E F D G A B C D E F G (a) (b) 层次遍历序列：层次遍历序列：A、B、C、D、E、F、Gvoid LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;/*定义环形队列定义环形队列,存放结点存放结点指针指针*/ int front,rear;/*定义队头和队尾指针定义队头和队尾指针*/ front=rear=-1;/*置队列为空队列置队列为空队列*/ rear+;

36、qurear=b;/*根结点指针进入队列根结点指针进入队列*/ while (front!=rear)/*队列不为空队列不为空*/ front=(front+1)%MaxSize; p=qufront;/*队头出队列队头出队列*/ printf(%c ,p-data);/*访问结点访问结点*/if (p-lchild!=NULL)/*有左孩子时将其进队有左孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NULL)/*有右孩子时将其进队有右孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear

37、=p-rchild; 例例7.2 假设二叉树采用二叉链存储构造存储假设二叉树采用二叉链存储构造存储,试设计一个试设计一个算法算法,输出一棵给定二叉树的一切叶子结点。输出一棵给定二叉树的一切叶子结点。 解：输出一棵二叉树的一切叶子结点的递归模型解：输出一棵二叉树的一切叶子结点的递归模型 f()如下：如下： f(b)：不做任何事件：不做任何事件 假设假设b=NULL f(b)：输出：输出*b结点的结点的data域域 假设假设*b为叶子结为叶子结点点 f(b)：f(b-lchild);f(b-rchild) 其他情况其他情况void DispLeaf(BTNode *b) if (b!=NULL)

38、if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); (5) 输出二叉树输出二叉树DispBTNode(*b) 其过程是：对于非空二叉树其过程是：对于非空二叉树b,先输出其元素值先输出其元素值,当当存在左孩子结点或右孩子结点时存在左孩子结点或右孩子结点时,输出一个输出一个“(符号符号,然后递归处置左子树然后递归处置左子树,输出一个输出一个“,符号符号,递归处置右递归处置右子树子树,最后输出一个最后输出一个“)符号。对应的递归算法如下：符号。对

39、应的递归算法如下： void DispBTNode(BTNode *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild); /*递归处置左子树递归处置左子树*/ if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild); /*递归处置右子树递归处置右子树*/ printf(); 6.3.2线索二叉树Threaded Binary Tree思索：二叉链表空间效率这么低，能否利用这些空思索：二叉链表空间

40、效率这么低，能否利用这些空闲区存放有用的信息或线索？闲区存放有用的信息或线索？我们可以用它来存放当前结点的直接前驱和后我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。继等线索，以加快查找速度。结论：用二叉链表法存储包含结论：用二叉链表法存储包含n n个结点的二叉树，结个结点的二叉树，结点的指针区域中会有点的指针区域中会有n+1n+1个空指针。个空指针。这就是线索二叉树这就是线索二叉树Threaded Binary TreeThreaded Binary Tree二叉树中容易找到结点的左右孩子信息，但该结点的二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在

41、某种遍历过程中动态获得。直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规那么把每个结点对应的前驱和后继线索预先依遍历规那么把每个结点对应的前驱和后继线索预存起来，这叫做存起来，这叫做“线索化。线索化。意义：从任一结点出发都能快速找到其前驱和后继，意义：从任一结点出发都能快速找到其前驱和后继，且不用借助堆栈。且不用借助堆栈。 对二叉树进展某种遍历之后，将得到一个线性有序的序列。对二叉树进展某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将，意味着已将该树转为线性陈列，显然其中结点具有独一前驱和独

42、一后继。在该树转为线性陈列，显然其中结点具有独一前驱和独一后继。在此前提下，那此前提下，那n+1个空链域才干装入也装得下个空链域才干装入也装得下“线索。线索。讨论讨论2.2.如何获得这种如何获得这种“直接前驱或直接前驱或“直接后继？直接后继？有何意义？有何意义？讨论讨论1 1：二叉树是：二叉树是1:21:2的非线性构造，如何定义其直接后继？的非线性构造，如何定义其直接后继？ 每个结点添加两个域：每个结点添加两个域：fwd和和bwd；存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存这类信息？有两种处理方法：如何预存这类信息？有两种处理方法： 与原有的左右孩子指针域与原有的左右孩子指针域“

43、复用，充分利用那复用，充分利用那n+1个空链域。个空链域。规规 定：定：1假设结点有左子树，那么假设结点有左子树，那么lchild指向其左指向其左孩子；孩子； 否那么，否那么， lchild指向其直接前驱指向其直接前驱(即线索即线索)；2假设结点有右子树，那么假设结点有右子树，那么rchild指向其右孩指向其右孩子；子； 否那么，否那么，rchild指向其直接后继指向其直接后继(即线索即线索) 。datalchildrchildfwdbwddatalchildrchild缺陷：空间效率太低！缺陷：空间效率太低！问题：计算机如何问题：计算机如何判别是孩子指针还判别是孩子指针还是线索指针？是线索指

44、针？如何区别？如何区别？lchildLTagdataRTagrchild商定商定:当当Tag域为域为0时时,表示正常情况表示正常情况;当当Tag域为域为1时时,表示线索情况表示线索情况.前驱前驱(后继后继)左左(右右)孩子孩子为区别两种不同情况，特添加两个标志域：为区别两种不同情况，特添加两个标志域：问：添加了前驱和后继等线索有什么益处？问：添加了前驱和后继等线索有什么益处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈递归也能遍历整个树。堆栈递归也能遍历整个树。各各1bit1bit1. 有关线索二叉树的几个术语：有关线索二叉树的几个术语： 线索链表：线索链表：

45、线线 索：索：线索二叉树：线索二叉树： 线线 索索 化：化：用含用含Tag的结点款式所构成的二叉链表的结点款式所构成的二叉链表指向结点前驱和后继的指针指向结点前驱和后继的指针加上线索的二叉树加上线索的二叉树对二叉树以某种次序遍历使其变为线索对二叉树以某种次序遍历使其变为线索二叉树的过程二叉树的过程线索化过程就是在遍历过程中修正空指针的过程：线索化过程就是在遍历过程中修正空指针的过程：将空的将空的lchildlchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的rchildrchild改为结点的直接后继。改为结点的直接后继。非空指针呢？依然指向孩子结点称为非空指针呢？依然指向孩子结点称

46、为“正常情况正常情况dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例：带了两个标志的某先序遍历结果如下表所示，请画例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。出对应的二叉树。ATag=1表示线索表示线索:Ltag=1表示前驱表示前驱Rtag=1表示后继表示后继ABCGEIDHFroot悬空？悬空？ NIL悬空？悬空？ NIL解：对该二叉树中序遍历的结果为解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, : H, D, I, B, E, A, F, C, GC, G所以添加线索该当按如下途径进

47、展：所以添加线索该当按如下途径进展：为防止悬空为防止悬空态，应增设态，应增设一个头结点一个头结点例例1 1：画出以下二叉树对应的中序线索二叉树。：画出以下二叉树对应的中序线索二叉树。2. 2. 线索二叉树的生成线索二叉树的生成线索化线索化线索化过程就是在遍历过线索化过程就是在遍历过程中修正空指针的过程程中修正空指针的过程00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: H, D, I, B, E, A, F, C, : H, D, I, B, E, A, F, C, G G0root0对应的中序线索二叉树存储构造如下图：对应的中序线索二叉树存

48、储构造如下图：例例2 2：【：【 考研题】给定如下图二叉树考研题】给定如下图二叉树T T，请画出与其对应，请画出与其对应的中序线索二叉树。的中序线索二叉树。 2825405560330854解解: :由于中序遍历序列是：由于中序遍历序列是：55 40 25 60 28 08 33 5455 40 25 60 28 08 33 54对应线索树该当按此规律连线，即在原二叉树中添加虚线。对应线索树该当按此规律连线，即在原二叉树中添加虚线。NILNILNILNIL线索二叉树的生成算法线索二叉树的生成算法目的：在遍历二叉树的过程中修正空指针，添加前驱或后继目的：在遍历二叉树的过程中修正空指针，添加前驱或

49、后继的线索，使之成为线索二叉树。的线索，使之成为线索二叉树。为了记下遍历过程中访问结点的先后次序，需求设置两个指针：为了记下遍历过程中访问结点的先后次序，需求设置两个指针：p指针指针当前结点之指针；当前结点之指针；pre指针指针当前结点的前趋结点指针。当前结点的前趋结点指针。设计技巧：依某种顺序遍历二叉树，对每个结点设计技巧：依某种顺序遍历二叉树，对每个结点p，判别其左指，判别其左指针能否为空，以及其前驱结点的右指针能否为空。针能否为空，以及其前驱结点的右指针能否为空。每次只修正前驱结点的右指针后继和本结点的左指针前每次只修正前驱结点的右指针后继和本结点的左指针前驱，参见算法驱，参见算法6.6

50、。假设假设p-lchildp-lchildNULL,NULL,那么那么p-Ltag=1;p-lchildp-Ltag=1;p-lchildpre;pre; /p /p的前驱线索应存的前驱线索应存p p结点的左边结点的左边假设假设pre-rchildpre-rchildNULL, NULL, 那么那么pre-Rtagpre-Rtag1; pre-1; pre-rchild=p;rchild=p; /pre /pre的后继线索应存的后继线索应存prepre结点的右边结点的右边3. 3. 线索二叉树的遍历无需堆栈线索二叉树的遍历无需堆栈对于线索二叉树的遍历，只需找到序列中的第一个结对于线索二叉树的遍

51、历，只需找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。点，然后依次访问结点的后继直到后继为空为止。由于建立线索时已遍历一次，相当于线性化了！由于建立线索时已遍历一次，相当于线性化了！难点：在线索化二叉树中，并不是每个结点都能难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为直接找到其后继的，当标志为0 0时，那么需求经过时，那么需求经过一定运算才干找到它的后继。一定运算才干找到它的后继。以中序线索二叉树为例：以中序线索二叉树为例：当当RTag=1时，直接后继指针就在其时，直接后继指针就在其rchild域内；域内；当当RTag=0时，直接后继是当前结点右子树最

52、左下方的结点；时，直接后继是当前结点右子树最左下方的结点；请留意中序遍历规那么是请留意中序遍历规那么是LDR，先左再根再右，先左再根再右5当当RTag=0时表示有右孩子时表示有右孩子 ，此时该当从该结点，此时该当从该结点的右孩子开场的右孩子开场(p=p-rchild查找左下角的子孙结点；查找左下角的子孙结点；即反复即反复2附：中序线索二叉树遍历步骤附：中序线索二叉树遍历步骤1设置一个搜索指针设置一个搜索指针p；2先寻觅中序遍历之首结点即最左下角结点，方先寻觅中序遍历之首结点即最左下角结点，方法是：当法是：当LTag=0时表示有左孩子，时表示有左孩子，p=p-lchild; 直到直到LTag=1

53、无左孩子，已到最左下角；首先访无左孩子，已到最左下角；首先访问问p-data；3接着进入该结点的右子树，检查接着进入该结点的右子树，检查RTag 和和p-rchild ；4 假设该结点的假设该结点的RTag=1(表示有后继线索表示有后继线索)，那么，那么p=p-rchild ；访问；访问p-data ;并反复并反复4 ，直到后继结点的，直到后继结点的RTag=0；有后继找后继，有后继找后继，无后继找右子树无后继找右子树的最左子孙的最左子孙有后继找后继有后继找后继算法流程：算法流程：return OK;return OK;p=T-lchild;p=T-lchild;p!=Tp!=Tp-LTag=

54、0p-LTag=0p=p-lchild;p=p-lchild;visit(p-data);visit(p-data);p-RTag=1&p-rchild!=Tp-RTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;visit(p-data);p=p-rchild;p=p-rchild;Y YN NY YN NY YN N先找最左子孙先找最左子孙找到最左子孙找到最左子孙无后继找右子树无后继找右子树的最左子孙的最左子孙要明确：要明确：1. 普通树即多叉树假设不转化为二叉树，那么运算很普通树即多叉树假设不转化为二叉树，那么运算很

55、难实现。难实现。2. 二叉树的运算依然是插入、删除、修正、查找、排序等，二叉树的运算依然是插入、删除、修正、查找、排序等，但这些操作必需建立在对树结点可以但这些操作必需建立在对树结点可以“遍历的根底上！遍历的根底上！树的遍历运算的算法主要有先根遍历和后根遍历两种。树的遍历运算的算法主要有先根遍历和后根遍历两种。1. 先根遍历先根遍历 (1) 访问根结点；访问根结点； (2) 按照从左到右的次序先根遍历根结点的每一棵子树。按照从左到右的次序先根遍历根结点的每一棵子树。2. 后根遍历后根遍历 后根遍历过程为：后根遍历过程为： (1) 按照从左到右的次序后根遍历根结点的每一棵子树；按照从左到右的次序

56、后根遍历根结点的每一棵子树； (2) 访问根结点。访问根结点。留意留意, 先根遍历先根遍历和后根遍历算法和后根遍历算法都是递归的。都是递归的。讨论讨论1：树是非线性构造，该怎样存储？：树是非线性构造，该怎样存储？依然有顺序存储、链式存储等方式。依然有顺序存储、链式存储等方式。 双亲存储构造双亲存储构造( 这种存储构造是一种顺序存储构造这种存储构造是一种顺序存储构造) A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 讨论讨论1：树是非线性构造，该怎样存储？：树是非线性构造，该怎样存储？依然有顺序存储、链式存储等方式

57、。依然有顺序存储、链式存储等方式。 A B C F D E (a) G A B C D E F G (b) 2 孩子链存储构造孩子链存储构造可按树的度可按树的度(即树中一切结点度的最大值即树中一切结点度的最大值)设计结点的孩子结点指针域个数。设计结点的孩子结点指针域个数。讨论讨论1：树是非线性构造，该怎样存储？：树是非线性构造，该怎样存储？依然有顺序存储、链式存储等方式。依然有顺序存储、链式存储等方式。 3 孩子兄弟链存储构造孩子兄弟链存储构造为每个结点设计三个域：一个数据元素域为每个结点设计三个域：一个数据元素域,一个该结点的第一个一个该结点的第一个孩子结点指针域孩子结点指针域,一个该结点的

58、下一个兄弟结点指针域。一个该结点的下一个兄弟结点指针域。 A B C F D E (a) G A B D C E G F (b) 讨论讨论3：树的链式存储方案应该怎样制定？：树的链式存储方案应该怎样制定？复原困难复原困难可用多重链表：一个前趋指针，可用多重链表：一个前趋指针，n n个后继指针。个后继指针。 细节问题：细节问题： 树中结点的构造类型款式该如何设计？树中结点的构造类型款式该如何设计？ 即应该设计成即应该设计成“等长还是等长还是“不等长？不等长？ 缺陷：缺陷： 等长构造太浪费每个结点的度不一定一样；等长构造太浪费每个结点的度不一定一样； 不等长构造太复杂要定义好多种构造类型。不等长构

59、造太复杂要定义好多种构造类型。先研讨最简单、最有规律的树，然先研讨最简单、最有规律的树，然后设法把普通的树转化为简单树。后设法把普通的树转化为简单树。可规定为：可规定为： 从上至下、从左至右将树的结点依次存入内存。从上至下、从左至右将树的结点依次存入内存。艰苦缺陷：艰苦缺陷：处理思绪：处理思绪：不能独一复原就没有适用价值！不能独一复原就没有适用价值！讨论讨论2：树的顺序存储方案应该怎样制定？：树的顺序存储方案应该怎样制定？6.2.3 树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1: step1: 将树中同一结点的兄弟相连将树中同一结点的兄弟相连; ;加线加线抹线抹线

60、旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？孩子孩子兄弟兄弟表示法表示法step2: step2: 保管结点的最左孩子连线，保管结点的最左孩子连线，删除其它孩子连线；删除其它孩子连线；step3: step3: 将同一孩子的连线绕左孩子将同一孩子的连线绕左孩子旋转旋转4545度角。度角。方法：加线方法：加线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左讨论讨论2 2：二叉树怎样复原为树？：二叉树怎样复原为树？abeidfhgc要点：逆操作，把一切右孩子变为兄弟！要点：逆操作，把一切右孩子变为兄弟！ abdefhgic法一：法一： 各森林先各