合工大数据结构07-树和二叉树

1、1数数 据据 结结 构构（第七章第七章 树和二叉树树和二叉树） Data Structures张晶张晶计算机与信息学院计算机与信息学院 2022-5-32022-5-32第七章第七章 树和二叉树树和二叉树 第七章第七章 树和二叉树树和二叉树 7.1 树的相关概念和术语 7.2 二叉树的定义、性质和存储结构 7.3 二叉树的遍历及其应用 7.4 线索二叉树 7.5 树和森林 7.6 哈夫曼树（Huffman）37.1 树的相关概念和术语 家族关系示意图家族关系示意图/单位机构组成示意图单位机构组成示意图o 定义：定义：树树T是由是由n个结点组成的个结点组成的有限集合有限集合（n 0）: 其中有一

2、个其中有一个根结点根结点， 其余结点可划分成其余结点可划分成m个（个（m=0）互不相交的互不相交的子集子集 T1, T2, . ,Tm， 且这些子集也分别构成且这些子集也分别构成树。树。 （注意：有无空树的概念）（注意：有无空树的概念）47.1 树的相关概念和术语o术语术语关系术语关系术语 孩子结点孩子结点 子树的根子树的根 父结点父结点 兄弟结点兄弟结点 同一个结点的孩子结点互为兄弟同一个结点的孩子结点互为兄弟 祖先结点祖先结点 后代结点后代结点层次类术语层次类术语 根的根的层次层次为为1 其余结点的层次为其父结点层次加其余结点的层次为其父结点层次加1 高度高度/深度深度 整个树中结点的最大

3、层次整个树中结点的最大层次 度度 结点的孩子数目称为结点的度结点的孩子数目称为结点的度 叶子叶子（终结点）（终结点） 度为度为0 分支结点分支结点-度不为度不为0的结点（非叶子结点）的结点（非叶子结点） 树的度树的度 最大的结点度最大的结点度 森林森林 多棵树多棵树 有序树有序树/无序树无序树 按照兄弟结点之间的排列按照兄弟结点之间的排列是否有序是否有序57.1 树的相关概念和术语o 运算运算（1）初始化）初始化（2）查找）查找 结点的父、兄弟、祖先、后代、根结点的父、兄弟、祖先、后代、根（3）插入）插入 叶子，叶子， 子树子树（4）删除）删除 叶子，子树叶子，子树树的存储？树的存储？6相关习

4、题 1. 画出由4个结点所构成的所有形态的树（假设是无序树）。2. 已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。77.2 二叉树的定义、性质和存储结构7.2.1定义定义 二叉树二叉树T：是：是n个结点组成的有限集合（个结点组成的有限集合（n = 0）: n=0时为时为空二叉树空二叉树， 否则：其中有一个否则：其中有一个根结点根结点， 其余结点可以划分成其余结点可以划分成两个两个互不相交的子集互不相交的子集TL, TR， 且且TL, TR也分别构成二叉树也分别构成二叉树 左、右子树左、右子树

5、。87.2 二叉树的定义、性质和存储结构二叉树与树的区别：二叉树与树的区别：是两种不同性质的结构；是两种不同性质的结构；二叉树存在空树，树不存在空树；二叉树存在空树，树不存在空树；二叉树恰有两个子树，树可有多个；二叉树恰有两个子树，树可有多个；二叉树子树有序，树无序。二叉树子树有序，树无序。比较三个结点的树与二叉树的各有几种不同的形态。比较三个结点的树与二叉树的各有几种不同的形态。 三个结点的三个结点的树树三个结点的三个结点的二叉树二叉树 AABBCCAAAAABBBBBCCCCC97.2 二叉树的定义、性质和存储结构由定义可知，依据结点数的多少可将二叉树划分为五由定义可知，依据结点数的多少可

6、将二叉树划分为五种不同的形态：种不同的形态：（1）空树，即结点数为）空树，即结点数为0（2）单结点二叉树，即仅有一个结点）单结点二叉树，即仅有一个结点（3）左子树为空右子树不空）左子树为空右子树不空（4）右子树为空左子树不空）右子树为空左子树不空（5）左右子树均不空）左右子树均不空107.2 二叉树的定义、性质和存储结构7.2.2二叉树的性质二叉树的性质 性质性质1：第第i层的结点数层的结点数2i-1； 性质性质2：高度为：高度为k（k1）的二叉树的结点总数）的二叉树的结点总数2k-1； 性质性质3：设二叉树的叶子结点数为：设二叉树的叶子结点数为n0，度为，度为2的结点数为的结点数为n2，则则

7、 n0=n2+1。 证明证明：设总结点数为：设总结点数为n，度为，度为1的结点数为的结点数为n1，则，则 n=n0+n1+n2 结点数结点数 （1） n-1=n1+2n2 分支数分支数 （2） 式（式（1）（）（2）得）得 n0=n2+1课堂练习课堂练习：已知一棵二叉树中，有：已知一棵二叉树中，有20个叶子结点，个叶子结点，10个结个结点只有左孩子，点只有左孩子，15个结点只有右孩子，求该二叉树的个结点只有右孩子，求该二叉树的总结点数。总结点数。117.2 二叉树的定义、性质和存储结构定义定义1：称高度为称高度为k且有且有2k-1个结点的二叉树为个结点的二叉树为满二叉树满二叉树。例如，高度为例

8、如，高度为14的满二叉树如下。的满二叉树如下。 ABCGFEDANOABCGFEHIDKJMLCBA(a) 高度为1的满二叉树(b) 高度为2的满二叉树(c) 高度为3的满二叉树(d) 高度为4的满二叉树127.2 二叉树的定义、性质和存储结构定义定义2：在满二叉树最下一层：在满二叉树最下一层从右到左从右到左依次连续去掉若干个依次连续去掉若干个结点的二叉树称为结点的二叉树称为完全二叉树完全二叉树。 下面分别给出完全二叉树和非完全二叉树的示例。下面分别给出完全二叉树和非完全二叉树的示例。ABCGFEHIDKJML(a) 完全二叉树示例MNABCGFEHIDKJL(b) 非完全二叉树示例ON137

9、.2 二叉树的定义、性质和存储结构对完全二叉树编号对完全二叉树编号o 编号的方式：从上到下，每一层中从左到右，根节点编号为1。o 例：下面完全二叉树的编号 ABCGFEHIDKJML12345678910111213147.2 二叉树的定义、性质和存储结构性质性质4：有：有n个（个（n1）结点的完全二叉树的高度）结点的完全二叉树的高度为为 。 性质性质5：对完全二叉树进行编号，则对编号为：对完全二叉树进行编号，则对编号为i的结点，的结点， 若存在左孩子结点，则其左孩子结点的编号为若存在左孩子结点，则其左孩子结点的编号为2i， 若存在右孩子结点，则其右孩子结点的编号为若存在右孩子结点，则其右孩子

10、结点的编号为2i+1， 若存在父结点，则其父结点的编号为若存在父结点，则其父结点的编号为 。2/i.1log2nABCGFEHIDKJML12345678910111213157.2 二叉树的定义、性质和存储结构课堂练习课堂练习： （1）求）求100个结点的完全二叉树的叶子结点数。个结点的完全二叉树的叶子结点数。 解：根据性质解：根据性质4，从编号，从编号51到到100都是叶子。共有都是叶子。共有50个叶子。个叶子。 （2）已知完全二叉树的第）已知完全二叉树的第7层有层有10个结点，问共有多少个结点？多少个结点，问共有多少个结点？多少个叶子结点？多少个度为个叶子结点？多少个度为1的结点？的结点

11、？ 解：共有解：共有26-1+10=73个结点。个结点。 叶子求法：叶子求法： 方法方法1、37到到73都是叶子，共都是叶子，共37个叶子结点；个叶子结点； 方法方法2、第、第7层层10个结点都是叶子，第个结点都是叶子，第6层有层有32个结点，其中个结点，其中5 个结点是第个结点是第7层层10个结点的父亲，个结点的父亲， 所以共有所以共有10+32-5=37个叶子结点。个叶子结点。 度为度为1的结点数为的结点数为0。 （3）判断题：完全二叉树最多有）判断题：完全二叉树最多有1个度为个度为1的结点。（的结点。（ ） （4）编号为）编号为i、j的两个结点是否在同一层的条件是的两个结点是否在同一层的

12、条件是 。 10050167.2 二叉树的定义、性质和存储结构7.2.3 二叉树的存储二叉树的存储 存储一个结构时，不仅要存值，还要存储元素间的关系。 1. 顺序存储方式顺序存储方式存储方式：用数组存储二叉树各结点的值， 各结点在数组中的位置（元素下标） -就是其在完全二叉树中对应结点的编号。例如：右图二叉树的存储如下所示。 0 123 45678 910111213ABCGFEHIDKJML12345678910111213 ABC DEF GH IJKLM177.2 二叉树的定义、性质和存储结构分析分析：这种方法有其优点，但也有不足：这种方法有其优点，但也有不足： 优点优点：方便、简洁：方

13、便、简洁 缺点缺点：只适合完全二叉树：只适合完全二叉树 或或 近似的完全二叉树。近似的完全二叉树。例如例如，对如下形状的二叉树，仅有，对如下形状的二叉树，仅有n个结点，个结点， 但需要的数组元素个数为但需要的数组元素个数为2n-1。问题问题： 若数组元素占一个单元，若数组元素占一个单元， 则在则在n=20、30时，时， 分别需要多大的存储空间？分别需要多大的存储空间？练习练习：设计算法求出编号：设计算法求出编号i、j的最小公共祖先。的最小公共祖先。x2x3x1xn1372n-1187.2 二叉树的定义、性质和存储结构 2. 动态二叉链表动态二叉链表存储方式存储方式： 二叉树中每个二叉树中每个结

14、点结点用一个有两个用一个有两个分叉的结点分叉的结点（二叉结点）二叉结点）来存储，来存储， 每个分叉指向左右孩子结点中的一个每个分叉指向左右孩子结点中的一个 -左右孩子左右孩子结点结点指针指针）。）。由此可得到二叉树的由此可得到二叉树的二叉链表结构二叉链表结构。 设二叉结点类型为设二叉结点类型为bnode, 其中：其中： 左右孩子指针分别为左右孩子指针分别为 lchild和和rchild， 存储结点值的字段为存储结点值的字段为data， 则结点的类型描述如下：则结点的类型描述如下：Struct bnode elementtype data; bnode *lchild, *rchild; ;lc

15、hild data rchild指向左孩子的指针指向左孩子的指针指向右孩子的指针指向右孩子的指针bnode197.2 二叉树的定义、性质和存储结构o 例例：下面二叉树对应的二叉链表结构如图所示。：下面二叉树对应的二叉链表结构如图所示。o 相关问题相关问题：（1）如图所示，根结点的指针为）如图所示，根结点的指针为T， 则如何表示其左右孩子指针的标识符？则如何表示其左右孩子指针的标识符？（2）从图中可知，二叉链表中有值为空的指针，）从图中可知，二叉链表中有值为空的指针， 有有n个结点的二叉链表中有多少个这样的空指针？个结点的二叉链表中有多少个这样的空指针？AGFEDCB G AB E C D F

16、T20相关习题 3. 如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。 4. 如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点数目最多的那棵完全二叉树的叶子结点数目。 5. 在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？ 217.3 二叉树的遍历及其应用 7.3.1 遍历的基本方法遍历的基本方法二叉树的遍历二叉树的遍历 按照某种次序依次访问二叉树按照某种次序依次访问二叉树T中每个结点中每个结点一次且仅一次一次且仅一次。分析分析：（1）若若T为空，遍历结束；为空，遍历结束；（2）

17、否则，设二叉树的形态如右图所示。）否则，设二叉树的形态如右图所示。a . 假设左右子树能分别遍历假设左右子树能分别遍历 （用（用L，R分别表示其遍历），则整个二分别表示其遍历），则整个二 叉树可有如下形式的遍历：叉树可有如下形式的遍历： 先左后右：先左后右：DLR LDR LRD 先右后左：先右后左：DRL RDL RLD 先根序先根序 中根序中根序 后根序后根序b.对于左右子树的遍历，对于左右子树的遍历， 可按照与整个二叉树相同的方式遍历（递归调用）可按照与整个二叉树相同的方式遍历（递归调用）DLR227.3 二叉树的遍历及其应用o 有关遍历方法的例题：有关遍历方法的例题： 例：分别写出下图

18、二叉树的先序、中序和后序序列例：分别写出下图二叉树的先序、中序和后序序列ABCDEFGHICDBEFAHGIDCFEBHIGADEIAGFCBH先序先序中序：中序：后序：后序：求解过程讨论求解过程讨论求解过程讨论求解过程讨论求解过程讨论求解过程讨论237.3 二叉树的遍历及其应用 例例：已知一棵二叉树的先序序列和中序序列，要求还原该二叉树。：已知一棵二叉树的先序序列和中序序列，要求还原该二叉树。 先序：先序：ABCDEFG 中序：中序：CDBEAGFGFDCBCDECDBEFGGFCDCDBAAABEFGGFE247.3 二叉树的遍历及其应用结论结论：已知中序序列和后序序列，或中序序列和先序序

19、列，可已知中序序列和后序序列，或中序序列和先序序列，可 以唯一确定一棵二叉树；以唯一确定一棵二叉树； 而已知先序序列和后序序列不能唯一确定二叉树而已知先序序列和后序序列不能唯一确定二叉树。课堂练习：已知二叉树中序序列和后序序列，还原此二叉树课堂练习：已知二叉树中序序列和后序序列，还原此二叉树。AGFEDCB中序：中序：CBDAGEF后序：后序：CDBGFEA257.3 二叉树的遍历及其应用7.3.2遍历算法遍历算法o 遍历方法遍历方法先序遍历先序遍历二叉树二叉树T若若T不空，则：不空，则： 访问根；访问根； 先序访问其左子树；先序访问其左子树； 先序访问其右子树先序访问其右子树 中序遍历中序遍

20、历二叉树二叉树T若若T不空，则：不空，则： 中序访问其左子树；中序访问其左子树； 访问根；访问根； 中序访问其右子树。中序访问其右子树。遍历算法遍历算法void preorder(bnode *t) if(t!=NULL) visit(t); preorder(t-lchild); preorder(t-rchlid); void inorder(bnode *t) if(t!=NULL) inorder(t-lchild); visit(t); inorder(t-rchlid); 267.3 二叉树的遍历及其应用 后序遍历后序遍历二叉树二叉树T 若若T不空，则：不空，则： 后序访问其左子树

21、；后序访问其左子树； 后序访问其右子树。后序访问其右子树。 访问根；访问根； void postorder (bnode *t) if(t!=NULL) postorder (t-lchild); postorder (t-rchlid); visit(t); 277.3 二叉树的遍历及其应用 练习练习： （1）对前述二叉树，按照阅读递归算法的方法，模拟执）对前述二叉树，按照阅读递归算法的方法，模拟执行。行。 （2）证明）证明preorder(bnode * T)对二叉树遍历的正确性对二叉树遍历的正确性（所有结点访问一次仅且一次）（所有结点访问一次仅且一次） （3） 设计算法求二叉树的结点数设

22、计算法求二叉树的结点数287.3 二叉树的遍历及其应用7.3.3遍历算法的应用遍历算法的应用例题例题：设计算法输出二叉树的所有叶子结点的值：设计算法输出二叉树的所有叶子结点的值 设计算法输出从根结点到每个叶子结点的路径设计算法输出从根结点到每个叶子结点的路径7.3.4 遍历方法的应用遍历方法的应用 1、求给定二叉树的高度：、求给定二叉树的高度：（1）若）若T为空，则高度为为空，则高度为0，遍历结束；，遍历结束；（2）否则，设二叉树的形态如右图所示。）否则，设二叉树的形态如右图所示。a、假设左右子树能分别求出高度为、假设左右子树能分别求出高度为hl、hr， 则整个二叉树的高度为：则整个二叉树的高

23、度为： max(hl, hr) + 1;b、对于左右子树高度的求解，可按照、对于左右子树高度的求解，可按照 与整个二叉树相同的方式进行（递归调用）与整个二叉树相同的方式进行（递归调用）T L R(直观上的高度求解过程及难度直观上的高度求解过程及难度)297.3 二叉树的遍历及其应用 设函数设函数int high(bnode *t)为求为求T的高度算法，则的高度算法，则 int high( bnode *T ) if ( T = NULL ) return(0); else return max( high( T - lchild ), high( T - rchild ) ) + 1 ; 或者

24、或者 int high( bnode * T ) if ( T = NULL ) return(0); else hl = high( T - lchild ); hr = high( T - rchild ); h = max( hl, hr ) + 1; return(h); 注意注意：hl,hr是局部变量还是全局变量？有何差异？如何体现？是局部变量还是全局变量？有何差异？如何体现？307.3 二叉树的遍历及其应用2、设计算法求二叉树的结点数：、设计算法求二叉树的结点数：分析分析: （1）设置一个）设置一个全局变量全局变量，在遍历二叉树的过程中，对访问的结点累，在遍历二叉树的过程中，对访问

25、的结点累计计数。计计数。 （2） 设函数设函数void num( bnode *T )表示对以表示对以T为根的二叉树遍历和为根的二叉树遍历和计数，分析如下：计数，分析如下： 如果如果T = NULL 结点数为结点数为0，不必累计；，不必累计； 否则否则 结点数结点数 = 左子树结点数左子树结点数 右子树结点数右子树结点数+1。 void num( bnode *T ) /设设k是全局变量，初始化是全局变量，初始化k=0 if ( T != NULL ) k+; num( T - lchild ); num( T - rchild ); 317.3 二叉树的遍历及其应用也可以设一个也可以设一个参

26、数参数返回累计的结点数。返回累计的结点数。void num( bnode *T, int &k ) /设调用时设调用时k对应的实参初对应的实参初始化为始化为0 if ( T != NULL ) k+; num( T - lchild, k); num( T - rchild, k ); 可以设计为可以设计为int型函数形式：型函数形式： int num( bnode * T ) if ( T = NULL ) return(0); else return num( T - lchild ) + num( T - rchild ) + 1; 327.3 二叉树的遍历及其应用3、设计算法求

27、二叉树的叶子结点数：、设计算法求二叉树的叶子结点数：分析分析：可以设计出多种形式的函数： int型函数，void型函数； 可以通过全局变量返回值，参数形式返回等。 void leaf( bnode *T, int &k ) /设调用时k对应的实参初始化为0 if ( T != NULL ) if ( T - lchild = NULL & T - rchild = NULL ) k+; leaf( T - lchild,k ); leaf( T - rchild,k ); 337.3 二叉树的遍历及其应用4、打印出二叉树的结点及其先序遍历的顺序数、打印出二叉树的结点及其先序遍历

28、的顺序数,如如(A,1),(B,2),(C,3) ：分析分析：函数返回类型: void型函数； 可能涉及变量及参数: 结点值, 先序次序。 void printnode( bnode *T, int &k ) /设调用时k对应的实参初始化为0 if ( T != NULL ) k+; coutdata,k lchild, k ); printnode( T - rchild, k ); 5、思考、思考:打印出二叉树的结点及其层次数打印出二叉树的结点及其层次数,如如(A,1),(B,2),(C,2) 347.4 二叉树o 6. 构造二叉树构造二叉树 输入数据 = 构造算法 如何确定输入序

29、列 (1) 先序、中序、后序配合构造 麻烦 (2) 扩展二叉树的先序序列 扩展二叉树的先序序列 扩展先序序列为：ABCDEFGHIJKL DEFHABGIJKCL D E F H A B G I J K C L357.4 二叉树 例：扩展二叉树先序序列为： ABCDEFGHIJKLMNO 对应的二叉树为：FEHJADBIKLNCMDGO F E H J A B I KL N C M D G O367.4 二叉树 例：扩展二叉树先序序列为：ABCDEFG. 对应的二叉树为： 例：扩展二叉树先序序列为：ABCDEFG 对应的二叉树为：DFABECGCDABEFG377.4 二叉树 二叉树的构造：输

30、入：扩展先序序列字符串输出：二叉树算法思路： 按顺序读入1个字符； 若为结束符，则 否则 开空间，存储结点； 对该结点的左右孩子递归进行操作DFABECGABCDEFG.注意：用户输入序列不能任意387.4 二叉树void create ( bitre *T ) cin x; if ( x = . ) T = NULL; else T = new bnode; T - data = x; create ( T - lchild ); create ( T - rchild ); 思考：能否按照类似的方法利用扩展中序、后序进行二叉树构造397.4 二叉树 文件形式存储二叉树：文件形式存储二叉树：

31、 例若外存文件存储，则文件内容为 如何检验二叉树构造是否正确成功？ 输出扩展二叉树序列 输出三种序 图形化显示树CDADBEFGbitreA 0 0B 1 0C 1 0D 1 1E 1 0F 1 0G 1 1CDABEFG407.3 二叉树的遍历及其应用练习：（1）设计一个非递归算法以输出二叉树t中先序序列中最后一个结点 的值。分析：首先需要知道这一结点的条件，然后才能正确地求解。请注意下面的算法中的相关条件，以及求解的思路。void print(bnod *t) p=t; while (p - lchild != NULL | p - rchild != NULL ) if ( p - rc

32、hild = NULL ) p = p - lchild; else p = p - rchild; cout data;417.3 二叉树的遍历及其应用相关习题相关习题1。设计算法将二叉链表存储的二叉树转换为顺序存储形式。设计算法将二叉链表存储的二叉树转换为顺序存储形式。 存储在存储在 A中，并将对应空结点的元素的值设置为中，并将对应空结点的元素的值设置为“”。例如，下面是一棵二叉树及其对应的存储结构例如，下面是一棵二叉树及其对应的存储结构A的示例。的示例。 ABC DEF GH I JM0 123 45678 910111213ABCGFEHDIKJ123456789101213427.3

33、 二叉树的遍历及其应用 void trans( bnode *t, int i ) if ( t != NULL ) Ai = t - data; trans( t - lchild,2 * i ); trans( t - rchild,2 * i + 1 ); 调用该算法前，将数组所有元素先设置为“”。2. 设计算法输出二叉树先序遍历的前设计算法输出二叉树先序遍历的前k个结点个结点判断题判断题： 先序和中序相同的二叉树，所有结点左孩子为空。（先序和中序相同的二叉树，所有结点左孩子为空。（ ） 先序和中序相反的二叉树，所有结点右孩子为空。（先序和中序相反的二叉树，所有结点右孩子为空。（ ） 先

34、序序列中最后一个结点是叶子结点。先序序列中最后一个结点是叶子结点。 （ ） 后序序列中第一个结点是叶子结点。后序序列中第一个结点是叶子结点。 （ ） 中序序列中第一个结点是叶子结点。中序序列中第一个结点是叶子结点。 （ ）437.3 二叉树的遍历及其应用3.分别描述满足下面条件的二叉树的特征： （1）先序序列和中序序列相同。 （2）先序序列和后序序列相反。4.证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树： 先序：ABCDEFGHI 先序：ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF 5.证明：由二叉树的后序序列和

35、中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树： 后序：DCFEBIHGA 后序：DECBGIHFA 中序：DCBFEAGHI 中序：DCEBAFHGI447.3 二叉树的遍历及其应用6. 已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。 先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _7. 证明：任意一棵非空的二叉树的先序序列的最后一个结点一定是叶子结点。8. 用反例证明：由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。9. 设计算法以输出二叉树中先序序列的前k（k0）个结点的值。457.

36、4 线索二叉树1。基本概念。基本概念问题问题: 对给定二叉树（二叉链表），对给定二叉树（二叉链表）， 求某结点在给定次序（先、中、后序）中的前驱或后继。求某结点在给定次序（先、中、后序）中的前驱或后继。 例：例：求图中结点求图中结点E，在先序、中序、后序中的前驱、后继结点。，在先序、中序、后序中的前驱、后继结点。 求解方法？求解方法？ （1）从头开始遍历）从头开始遍历 费时；费时； （2）给每个结点增设前驱）给每个结点增设前驱/后继指针后继指针 费空间；费空间； （3）利用二叉链表中）利用二叉链表中n+1个为空的指针域个为空的指针域 可行的一种考虑可行的一种考虑 DEIAGFCBH467.4

37、线索二叉树 将二叉链表中空的指针修改为指向前驱或后继，即将二叉链表中空的指针修改为指向前驱或后继，即 将其中的值为空的将其中的值为空的左孩子左孩子指针改为指向指针改为指向前驱，前驱， 将其中的值为空的将其中的值为空的右孩子右孩子指针改为指向指针改为指向后继。后继。 线索。线索。 线索二叉树。线索二叉树。 例如，例如，右图就是一个右图就是一个 先序先序线索二叉树。线索二叉树。 其中线索用其中线索用虚线虚线表示。表示。 线索化线索化 将二叉树修改为线索二叉树的过程。 ABCDEFHGIJ477.4 线索二叉树为了区分孩子指针和线索（虽然由图中可以“直观地”区分出来，但在算法中却不行）。在每个结点中

38、需再引入两个区分标志ltag和rtag，并且约定如下：ltag=0： lchild指示该结点的左孩子。ltag=1： lchild指示该结点的前驱。rtag=0： rchild指示该结点的右孩子。rtag=1： rchild指示该结点的后继。0A00B01C10D01E11F10G11H00I11J1487.4 线索二叉树为简便起见，通常将线索二叉树画成如下的形式。ABCDGFEHI先序线索二叉树中序线索二叉树EIHDCGBAF497.4 线索二叉树 2。线索二叉树的结构描述线索二叉树的结构描述 如前所述，为区分结点中的孩子指针和线索，结点中增设了两个如前所述，为区分结点中的孩子指针和线索，结

39、点中增设了两个标志标志ltag和和rtag，并约定：，并约定： 0 结点中的结点中的 lchild字段指向字段指向左孩子；左孩子； ltag= 1 结点中的结点中的 lchild字段指向字段指向前驱前驱； 0 结点中的结点中的 rchild字段指向字段指向右孩子右孩子； rtag= 1 结点中的结点中的 rchild字段指向字段指向后继后继； 由此可知，结点的类型描述由此可知，结点的类型描述 typedef struct tbnode elementtype data; tbnode *lchild, *rchild; int ltag, rtag; tbnode; 507.4 线索二叉树3.

40、 线索二叉树中前驱和后继的求解线索二叉树中前驱和后继的求解o 先序线索二叉树n 前驱n 后继o 中序线索二叉树n 前驱n 后继o 后序线索二叉树n 前驱n 后继 共有三组六个问题需求解517.4 线索二叉树3. 线索二叉树中前驱和后继的求解线索二叉树中前驱和后继的求解 (1) 先序线索二叉树中先序线索二叉树中先序后继先序后继的求解的求解先序后继先序后继 对先序线索二叉树中任意结点对先序线索二叉树中任意结点P，求其先序后继。，求其先序后继。 讨论：讨论： (a) 若若*p有左孩子有左孩子 按照遍历的过程描述（按照遍历的过程描述（PPLPR）可知，）可知， 其后继应为：左子树其后继应为：左子树PL

41、中的第一个结点，中的第一个结点， 即即*p的左孩子结点，的左孩子结点， 因此，因此， p-lchild为其后继；为其后继； (b) 否则，否则，*p有右孩子有右孩子 类似地，可知类似地，可知 p-rchild为其后继；为其后继； (c) 否则，否则， p-rchild为其后继线索；为其后继线索；由此得由此得算法算法如下：如下： tbnode *presuc(tbnode *p) if ( p - ltag = 0 ) return ( p - lchild ); else return ( p - rchild ); P PLPR(a)PPR(b)(c)P527.4 线索二叉树 (2) 先序线

42、索二叉树中先序线索二叉树中先序前驱先序前驱的求解的求解先序前驱先序前驱 对二叉树先序中任意的结点对二叉树先序中任意的结点P，求其前驱。，求其前驱。 讨论：讨论： (a) 若若*P是根结点是根结点 无前驱无前驱 (b) 若若*P是其父结点的左孩子是其父结点的左孩子 前驱是其父结点；前驱是其父结点； (c) 否则，若否则，若*P是其父结点的右孩子是其父结点的右孩子 无左兄弟结点无左兄弟结点 前驱是父结点；前驱是父结点； 有左兄弟结点有左兄弟结点 前驱是左兄弟子树中前驱是左兄弟子树中 最右下的叶子结点。最右下的叶子结点。 练习练习：n设计一个非递归算法，设计一个非递归算法， 以先序遍历先序线索二叉树

43、（且不用栈）以先序遍历先序线索二叉树（且不用栈） (a)PPP子子树树XR(b)XPP子子树树XL(c)X537.4 线索二叉树(3) 中序线索二叉树中中序后继的求解中序线索二叉树中中序后继的求解中序后继中序后继分析：按照中序遍历的过程描述（分析：按照中序遍历的过程描述（PLPPR）可知，）可知， (a) 若若*P有右孩子有右孩子 其后继应在其右子树中，其后继应在其右子树中， 即右子树的中序序列的即右子树的中序序列的 第一个结点为第一个结点为*p的后继。的后继。 如何求解此结点？如何求解此结点？ 从右孩子结点往左下从右孩子结点往左下“滑行滑行”到到 。？。？ (b) 若若*P无右孩子无右孩子

44、则则p - rchild 就是其后继线索。就是其后继线索。PPR(a)(b)PPP1P2Pk54N Y7.4 线索二叉树 tbnode * insuc ( tbnode *p ) if ( p - rtag = 1 ) return ( p - rchild ); else q = p - rchild; while ( q - ltag = 0 ) q = q - lchild; return(q); P有右孩子有右孩子Yq=p-rchildq有左孩子有左孩子q=q-lchildNreturn p-rchildreturn q 由讨论得流程图如下：由讨论得流程图如下：557.4 线索二叉树

45、(4) 中序前驱的求解中序前驱的求解 与中序后继对称与中序后继对称 分析分析： (a) 若有左孩子 前驱是左子树中序序列的最后一个结点； (b) 若无左孩子 前驱线索p-lchild。 tbnode * inpre ( tbnode *p ) if ( p - ltag = 1 ) return ( p - lchild ); else q = p - lchild; while ( q - rtag = 0 ) q = q - rchild; return(q); 567.4 线索二叉树 (5) 后序前驱后序前驱的求解的求解分析分析： (a) 若*p有右孩子 右孩子结点是其前驱； (b) 否

46、则，若*P有左孩子 左孩子结点是其前驱； (c) 否则 p - lchild是其前驱线索 。 与先序后继的求解方式与先序后继的求解方式对称对称。由此得由此得算法算法如下：如下： tbnode *postpre(tbnode *p) if ( p - rtag = 0 ) return ( p - rchild ); else return ( p - lchild ); P PLPR577.4 线索二叉树 (6) 后序后继的求解分析： (a) 根 无后继； (b) 若*p是其父结点的右孩子 父结点是其后继； (c) 若是父结点的左孩子 无右兄弟 父结点是其后继； 有右兄弟 右兄弟子树的后序序列

47、的第一个结点是其后继 右兄弟子树中最左下的叶子结点。P PLPR587.4 线索二叉树4. 线索二叉树中插入结点线索二叉树中插入结点在结构中插入一个元素或结点是常见的运算。在结构中插入一个元素或结点是常见的运算。在线索二叉树中插入一个结点时，在线索二叉树中插入一个结点时，不仅要实现指定结点的父子关系的运算，不仅要实现指定结点的父子关系的运算，还需要在插入结点后，还需要在插入结点后，通过修改线索，通过修改线索，以维护二叉树的线索关系。以维护二叉树的线索关系。例如例如，在右图线索二叉树中，在右图线索二叉树中，将某结点插入到作为结点将某结点插入到作为结点F的左孩子。的左孩子。如何实现相关的操作如何实

48、现相关的操作？s先序线索二叉树ABCDGFEHI597.4 线索二叉树分析：分析：对这类插入操作，通常从两个方面来考虑其实现：对这类插入操作，通常从两个方面来考虑其实现： （1）一个是父子关系的连接实现）一个是父子关系的连接实现 按照指定关系连接即可按照指定关系连接即可 （2）线索关系的维护）线索关系的维护 这一关系的实现有一定的难度。这一关系的实现有一定的难度。下面分别讨论。下面分别讨论。（1）父子关系的连接实现）父子关系的连接实现 对前述问题，由问题描述可知，对前述问题，由问题描述可知， 假设指针假设指针P指示到了指示到了F结点，结点， 连接操作如图所示，操作如下：连接操作如图所示，操作如

49、下： p-lchild=s; p-ltag=0;先序线索二叉树ABCDGFEHIPs607.4 线索二叉树（2）线索关系的维护）线索关系的维护这一操作主要由如下组成：这一操作主要由如下组成：（某些操作可能因具体问题而不同）（某些操作可能因具体问题而不同）o设置新插入结点的设置新插入结点的前驱、后继线索前驱、后继线索o修改新结点的修改新结点的前驱结点的后继线索前驱结点的后继线索o修改新结点的修改新结点的后继结点的前驱线索后继结点的前驱线索就本题而言，首先需要明确：就本题而言，首先需要明确：o新结点的前驱、后继位置及其指针：新结点的前驱、后继位置及其指针： 由图可知，前驱后继结点分别是由图可知，前

50、驱后继结点分别是 F结点和结点和G结点结点 更一般情况下，可由更一般情况下，可由*P及其后继求得。及其后继求得。 先序线索二叉树ABCDGFEHIPs617.4 线索二叉树下面先讨论线索操作的一般性方法，下面先讨论线索操作的一般性方法，然后给出本题的操作实现。然后给出本题的操作实现。假设当前结点为假设当前结点为*P，由于线索关系使得结点之间建立了线性关系，由于线索关系使得结点之间建立了线性关系，因此，插入结点时的线索维护类似于双链表中插入结点。因此，插入结点时的线索维护类似于双链表中插入结点。由于新结点是作为由于新结点是作为*P的后继，的后继，因此，可有如下的逻辑图：因此，可有如下的逻辑图：G

51、FPxs627.4 线索二叉树本题的线索维护操作如下：请标出其操作示意图。本题的线索维护操作如下：请标出其操作示意图。 s-lchild=p; s-ltag=1; s-rchild=p-rchild; s-rtag=1; if ( p-rtag=1 ) p-rchild=s; if (s-rchild-ltag=1) s-rchild-lchild=s;习题习题：设计算法将：设计算法将s结点作为结点作为A的右子树的最左下的叶子结点的右子树的最左下的叶子结点的左孩子插入到先序线索二叉树中，并维护其线索关系。的左孩子插入到先序线索二叉树中，并维护其线索关系。先序线索二叉树ABCDGFEHIPs63

52、7.4 线索二叉树o 思考： 设计按先序次序遍历先序线索二叉树T的非递归算法 void preorder ( tbnode * T )tbnode *p = T;while ( p != NULL )cout data;p = p-presuc(p); 647.4 线索二叉树o 5. 二叉树的线索化二叉树的线索化n 基本框架基本框架在遍历过程中实现对每个结点的线索化在遍历过程中实现对每个结点的线索化n 每访问一个结点，如何线索化？每访问一个结点，如何线索化？P后继后继P前驱前驱TPP的前驱线索化的前驱线索化 T-lchild = pre; T-ltag = 1;P的后继线索化的后继线索化前驱结

53、点的后继线索化；前驱结点的后继线索化；当前结点的前驱线索化；当前结点的前驱线索化；判断当前结点是否需要后继线索化判断当前结点是否需要后继线索化657.4 线索二叉树o 5. 二叉树的线索化算法实现二叉树的线索化算法实现n 先序线索化为例先序线索化为例void prethread( bnode * t, bnode * pre) if ( t != NULL ) if ( pre != NULL ) & ( pre-rtag=1) pre-rchild=t; if ( t-lchild = NULL ) t-lchild = pre; t-ltag=1; else t-ltag=0; i

54、f ( t-rchild = NULL ) t-rtag=1; else t-rtag=0; pre = t; if ( t-ltag=0) prethread( t-lchild, pre); / 需要对需要对pre进行更新吧？进行更新吧？ if ( t-rtag=0) prethread( t-rchild, pre); （看下课本上怎么写的？）（看下课本上怎么写的？）前驱结点的后继线索化；前驱结点的后继线索化；当前结点的前驱线索化；当前结点的前驱线索化；判断当前结点是否需要后继判断当前结点是否需要后继线索化线索化667.5 树和森林o7.5.1树树/森林的存储结构森林的存储结构1. 双亲

55、表示法双亲表示法 存储每个结点的双亲结点的位置信存储每个结点的双亲结点的位置信息。息。例如：例如： 优点优点：简洁，：简洁， 形式一致；形式一致； 搜索父结点、祖先容易搜索父结点、祖先容易 缺点缺点：搜索孩子结点费时；：搜索孩子结点费时； 插入删除时需注意维护关系插入删除时需注意维护关系A-1B0C0D0E1F1G2H3I3J3K4ABCGFEHIJKDdata parents012345678910677.5 树和森林2. 孩子链表表示法孩子链表表示法存储每个结点的孩子信息，因而是链表形式。存储每个结点的孩子信息，因而是链表形式。 优点优点：找孩子结点：找孩子结点/后代容易后代容易缺点缺点：

56、重复：重复 结构不一致结构不一致BCD EF G K H I J ABCGFEHIJKDABCDEFGHIJKdata children_link012345678910687.5 树和森林3. 孩子兄弟链表孩子兄弟链表表示法表示法表示方法表示方法：采用链表结构来存储树，：采用链表结构来存储树， 链表中结点与树中结点对应，链表中结点与树中结点对应， 每个结点存储其第一个每个结点存储其第一个孩子孩子结点结点 和下一个和下一个兄弟兄弟结点。结点。由此而得名。由此而得名。也叫也叫二叉链表表示法二叉链表表示法，或，或二叉树表示法。二叉树表示法。firstson data nextbrother 指向其

57、第一个孩子结点指向其下一个兄弟结点697.5 树和森林前述树所对应的存储结构如下：前述树所对应的存储结构如下： A F B G C K D J I H EABCGFEHIJKD707.5 树和森林将前述孩子兄弟链表顺时针旋转将前述孩子兄弟链表顺时针旋转45。，对应到一个对应到一个二叉链表二叉链表，因此也对应到一棵因此也对应到一棵二叉树二叉树。 H G D F A B C E I K J ABCGFEHIJKD717.5 树和森林如果是森林，其存储如何？如果是森林，其存储如何？ 森林 二叉链表（二叉树） 由图可知，这其实是二叉链表结构，所以任意一棵树（森林）必然由图可知，这其实是二叉链表结构，所

58、以任意一棵树（森林）必然与唯一的一棵二叉树一一对应。与唯一的一棵二叉树一一对应。ABCGFEHIJKDLMNABCGFEHIJKDMNL727.5 树和森林o 7.5.2 树树/森林与二叉树之间相互转换森林与二叉树之间相互转换1树树/森林森林 F=（T1，T2，Tm） = 二叉树二叉树 BT(1) T1的根 = BT的根(2) T1的子树/森林 = BT的左子树(3) （T2，Tm）= BT的右子树2二叉树二叉树 BT = 树树/森林森林 F=（T1，T2，Tm）如果BT不空，则：(1) BT的根 = T1的根(2) BT的左子树 = T1的子树/森林 (3) BT的右子树 =（T2，Tm）

59、737.5 树和森林练习练习：将下面的森林转换为对应的二叉树：将下面的森林转换为对应的二叉树。转换后二叉树的性质与树中性质与某些运算是否发生变化转换后二叉树的性质与树中性质与某些运算是否发生变化?(1) 某结点在树中为叶子结点，在二叉树中未必为叶子结点；某结点在树中为叶子结点，在二叉树中未必为叶子结点；(2) 二叉树中为叶子结点，在树中没有孩子的老小；二叉树中为叶子结点，在树中没有孩子的老小；(3) 两者分支数不一定相同。（树相同，森林则不同）两者分支数不一定相同。（树相同，森林则不同）ABCGFEHIJKDLMNOPQR747.5 树和森林 森林 二叉链表（二叉树） ABCGFEHIJKDL

60、MNABCGFEHIJKDMNL757.5 树和森林o 7.5.3 树树/森林的遍历森林的遍历按照根结点与子树的访问次序，按照根结点与子树的访问次序， 有两种遍历森林的方法。有两种遍历森林的方法。 先序遍历先序遍历和和后序遍历后序遍历。 1、先序遍历、先序遍历 树（森林）树（森林）F = （T1，T2，Tm）如果如果F不空，则：不空，则：(1) 访问访问T1的根；的根；(2) 先序遍历先序遍历T1的子树森林；的子树森林；(3) 先序遍历（先序遍历（T2，T3，Tm）。767.5 树和森林例如，对前述的森林，其先序遍历的序列其先序遍历的序列ABCGFEHIJKDLMNABCGFEHIJKDMNLABEKFCGDHIJLMNABEK