课件第6二叉树

1、第第6章章 树和二叉树树和二叉树n学习要点学习要点: 熟练掌握二叉树的结构特性熟练掌握二叉树的结构特性熟悉二叉树的各种存储结构特点及使用范围熟悉二叉树的各种存储结构特点及使用范围熟练掌握各种遍历策略的递归和非递归算法，灵熟练掌握各种遍历策略的递归和非递归算法，灵活运用遍历算法实现二叉树的其他操作活运用遍历算法实现二叉树的其他操作熟练掌握二叉树的线索化过程以及在中序线索化熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法树上找给定结点的前驱和后继的方法掌握树和森林与二叉树的转换方法掌握树和森林与二叉树的转换方法学会编写实现树的各种操作的算法学会编写实现树的各种操作的算法了

2、解最优树的特性，掌握建立最优树和哈夫曼编了解最优树的特性，掌握建立最优树和哈夫曼编码的方法码的方法6.1 树的定义和基本术语树的定义和基本术语6.1.1 树的定义树的定义n树型结构：树型结构：非线性结构：至少存在一个数据元素有非线性结构：至少存在一个数据元素有两个两个或或两两个以上个以上的的直接前驱直接前驱(或或直接后继直接后继)元素的数据结构。元素的数据结构。用于描述层次结构的关系：用于描述层次结构的关系：n人类的族谱、操作系统的文件系统、人类的族谱、操作系统的文件系统、Internet中的中的DNS(域名系统域名系统)等等分等级的分类方案均可用层次结构来表示，可由分等级的分类方案均可用层次

3、结构来表示，可由此导出树型结构。此导出树型结构。n树的定义：树的定义： 是是n(n0)个结点的有限集合个结点的有限集合T，对于任意一棵，对于任意一棵非空树，它满足：非空树，它满足：有且有且仅有一个仅有一个特定的称为特定的称为根根(root)的结点；的结点；当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交的互不相交的有限集有限集T1，T2，.，Tm，其中每个集合本身又是，其中每个集合本身又是一棵树，称为根的一棵树，称为根的子树子树。上述上述树的定义是一个递归定义树的定义是一个递归定义。例如：例如：ABCDEFGHIJMKLAn树的类型定义：树的类型定义：ADT Tree 数据对

4、象数据对象：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系：若若D为空集，则称为空树；否则为空集，则称为空树；否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root, (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互不相个互不相交的有限集交的有限集T1, T2, , Tm, 其中每一棵子集本身又其中每一棵子集本身又是一棵符合本定义的树，称为根是一棵符合本定义的树，称为根root的子树。的子树。 基本操作基本操作：n查找类查找类n插入插入 n删除删除 ADT Tree查找类：查找类：nRoot(T) / 求

5、树的根结点求树的根结点 nValue(T, cur_e) / 求当前结点的元素值求当前结点的元素值nParent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点nLeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子nRightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟nTreeEmpty(T) / 判定树是否为空树判定树是否为空树nTreeDepth(T) / 求树的深度求树的深度nTraverseTree( T, Visit() ) / 遍历遍历插入：插入：nInitTree(&T) / 初始化置空树

6、初始化置空树nCreateTree(&T, definition) / 按定义构造按定义构造nAssign(T, cur_e, value) / 给当前结点赋值给当前结点赋值nInsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结为根的树插入为结 /点点p的第的第i棵子树棵子树删除：删除：nClearTree(&T) / 将树清空将树清空nDestroyTree(&T) / 销毁树的结构销毁树的结构nDeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子棵子例如：例如：ABCDEFG

7、HIJMKL(A( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根树根T1T2T36.1.2 基本术语基本术语n结点结点：包含一个数据元素包含一个数据元素及及若干指向其子树的分若干指向其子树的分支。支。n结点的度结点的度：结点拥有的：结点拥有的子树数子树数。如图：如图： A的度为的度为3， C的度为的度为1， E的度为的度为0。n叶子叶子(或终端或终端)结点：度为零的结点。结点：度为零的结点。n分支分支(或非终端或非终端)结点：度大于零的结点。结点：度大于零的结点。ABCDEFGHIJMKLn树的度树的度：树中所有结点的：树中所有结点的度的最大值度的最大值

8、。n结点的结点的子树的根子树的根称为该结点的称为该结点的孩子孩子(child) 。n相应的，该结点相应的，该结点称为孩子的称为孩子的双亲双亲(parent)。如图所示，树的度为如图所示，树的度为3；D为为A的子树的子树T3的根，则的根，则D是是A的孩子，而的孩子，而A则是则是D的双亲。的双亲。n同一个双亲同一个双亲的孩子之间互的孩子之间互 称称兄弟兄弟。如图所示中，如图所示中，H、I、J互称为兄弟。互称为兄弟。ABCDEFGHIJMKLE、G、H互称兄弟？互称兄弟？n双亲在同一层的结点互为双亲在同一层的结点互为堂兄弟堂兄弟。n结点的层次结点的层次：根结点的层次为：根结点的层次为1，第，第l层的

9、结点的层的结点的子树的根结点的层次为子树的根结点的层次为l+1。n树的深度树的深度：树中：树中叶子结点叶子结点所在的所在的最大层次最大层次。n森林森林：是：是m(m0)棵棵互不相交的互不相交的树的集合。树的集合。n任何一棵非空树是一个任何一棵非空树是一个二元组二元组Tree = (root，F)其中：其中： root 被称为根结点被称为根结点 F 被称为被称为子树森林子树森林ArootBCDEFGHIJMKLFn有序树有序树：子树之间存在确定的次序关系。：子树之间存在确定的次序关系。(树中结树中结点的各子树从左到右是有次序的，即不能互换点的各子树从左到右是有次序的，即不能互换)。n无序树无序树

10、：子树之间不存在确定的次序关系。：子树之间不存在确定的次序关系。n树型结构和线性结构的特点：树型结构和线性结构的特点：线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )6.2.1 二叉树的定义二叉树的定义n定义定义：是：是n(n=0)个结点的有限集合，它或为个结点的有限集合，

11、它或为空树空树(n=0)，或由，或由一个根结点一个根结点和和至多两棵至多两棵称为根的称为根的左子左子树树和和右子树右子树的互不相交的的互不相交的二叉树二叉树组成。组成。注：二叉树中不存在度大于注：二叉树中不存在度大于2的结点，并且二叉树的结点，并且二叉树的子树有左子树和右子树之分。的子树有左子树和右子树之分。6.2 二叉树二叉树ABCDEFGHK根结点根结点左子树左子树右子树右子树n二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树n二叉树的抽象数据类型定义：二叉树的抽象数

12、据类型定义：ADT BinaryTree 数据对象数据对象：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系：若若D为空集，则称为空树；否则为空集，则称为空树；否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root, . 基本操作基本操作：n查找类查找类n插入插入 n删除删除ADT BinaryTree 详细说明见教材详细说明见教材P121P1236.2.2 二叉树的性质二叉树的性质n性质性质1 ：在二叉树的第在二叉树的第 i 层上层上至多至多有有2i-1 个结点个结点(i1)。证明证明：(归纳法归纳法)归纳基：归纳基：i =

13、 1 层时，只有一个根结点：层时，只有一个根结点： 2i-1 = 20 = 1，命题成立。，命题成立。归纳假设：假设对所有的归纳假设：假设对所有的 j，1 j i，命题成立。命题成立。即第即第j层上至多有层上至多有2j-1个结点。个结点。归纳证明：归纳证明：j=i时，命题成立。时，命题成立。 二叉树上每个结点二叉树上每个结点至多有两棵子树至多有两棵子树，且由归，且由归纳假设有：第纳假设有：第i-1层上至多有层上至多有2i-2个结点个结点 第第 j=i 层的结点数至多层的结点数至多 = 2i-2 2 = 2i-1 。命题成命题成立立(证毕证毕)n性质性质2：深度为：深度为 k 的二叉树上的二叉树

14、上至多至多含含 2k-1 个结点个结点(k1)。证明：证明：基于性质基于性质1，深度为，深度为 k 的二叉树上的结点数至的二叉树上的结点数至多为：多为：20+21+ +2k-1 = 2k-1 。n性质性质3：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶子结个叶子结点、点、n2 个度为个度为2的结点，则必存在关系式：的结点，则必存在关系式：n0 = n2+1。证明：证明：设二叉树上结点总数设二叉树上结点总数 n = n0 + n1 + n2， 二叉树上分支总数二叉树上分支总数 b = n1+2n2， 而而 b = n-1 = n0 + n1 + n2 1 由由， n0 = n2

15、 + 1 。除根结点外，其余结点都有一个分支除根结点外，其余结点都有一个分支进入，设进入，设b为分支总数，则为分支总数，则n=b+1。n两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为：指的是深度为k且含有且含有2k-1个结点的二叉个结点的二叉树。树。完全二叉树完全二叉树：树中所含的：树中所含的 n 个结点和满二叉树中个结点和满二叉树中编编号为号为 1 至至 n 的结点的结点一一对应。一一对应。123456789101112131415abcdefghij特点特点：是：是每一层每一层上的结点数都是上的结点数都是最大结点数最大结点数。特点特点：叶子结点叶子结点只可能只可能在在层

16、次最大层次最大的两层的两层出现；出现；对任一结点，若其对任一结点，若其右右分支下的子孙的分支下的子孙的最大层次为最大层次为l，则其，则其左左分支下的子孙的分支下的子孙的最大层次为最大层次为l或或l+1。完全二叉树的性质：完全二叉树的性质：n性质性质4：具有具有n个结点的完全二叉树的个结点的完全二叉树的深度深度为为 log2n +1。证明：证明：设完全二叉树的深度为设完全二叉树的深度为k，则根据性质则根据性质2(深度深度为为k的二叉树至多有的二叉树至多有2k-1个结点个结点) 得得 2k-1-1 n 2k 1，或：，或： 2k-1 n 2k 即即 k-1 log2 n n，则该结点无左孩子，否则

17、，编号为，则该结点无左孩子，否则，编号为 2i 的结点为其的结点为其左孩子左孩子结点；结点；(3)若若 2i+1n，则该结点无右孩子结点，否则，编号，则该结点无右孩子结点，否则，编号为为2i+1 的结点为其的结点为其右孩子右孩子结点。结点。 i/2 i 2i 2i+1 i+1 2i+2 2i+3 i+1 2i+2 2i+3 i2i2i+1 .n性质练习：性质练习：1. 一棵二叉树在其第五层中有一棵二叉树在其第五层中有17个结点，可不可能？个结点，可不可能？2. 二叉树的根结点属于第二叉树的根结点属于第0层还是属于第层还是属于第1层？层？3. 已知一棵二叉树有已知一棵二叉树有20个结点，其中个结

18、点，其中6个结点为叶子，则该个结点为叶子，则该树中度为树中度为2的结点数为的结点数为 ？度为？度为0的结点为的结点为 ？4. 已知一棵完全二叉树中编号为已知一棵完全二叉树中编号为101的结点有的结点有LC和和RC结点，结点，则其则其LC结点编号为结点编号为 ，RC结点编号为结点编号为 ？5. 一棵深度为一棵深度为h的完全的完全k叉树，如果按层次自顶向下、同一层叉树，如果按层次自顶向下、同一层自左向右、顺序从自左向右、顺序从1开始对全部结点进行编号，试问：该开始对全部结点进行编号，试问：该树上最多有多少个结点？最少有多少个结点？树上最多有多少个结点？最少有多少个结点？第第i层上至多有层上至多有2

19、i-1个结点，则个结点，则25-1=16。所以，不可能。所以，不可能。第第1层层56由性质由性质3：n0=n2+1，则，则n2=n0-1=6-1=5。202203由性质由性质5，可知左孩子为，可知左孩子为2i，右孩子为，右孩子为2i+1由性质由性质1和定义，可知除第和定义，可知除第h层外，其余各层都是满的，所以：层外，其余各层都是满的，所以：1+k+k2+.+kh-2=(kh-1-1)/(k-1)，则最多有：，则最多有： (kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1)；最少有：最少有：(kh-1-1)/(k-1)+1课后作业课后作业P38：6.5P39：6.6(要求：写出推导

20、过程要求：写出推导过程)6.2.3 二叉树的存储结构二叉树的存储结构n顺序存储结构：顺序存储结构：#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点号单元存储根结点SqBiTree bt;特点：特点：n一组地址连续的存储单元存储各结点一组地址连续的存储单元存储各结点(定义一个一维定义一个一维数组数组)；n自根而下、自左而右存储结点；自根而下、自左而右存储结点；n按按完全二叉树完全二叉树上的上的结点位置结点位置进行编号和存储。进行编号和存储。例如：例如

21、：ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326在最坏的情况下，一个深度为在最坏的情况下，一个深度为k且只有且只有k个结点的单支树个结点的单支树(树中不存在度为树中不存在度为2的的结点结点)却需要却需要2k-1的一维数组。的一维数组。缺点：空间利用率太低！缺点：空间利用率太低！n链式存储结构：链式存储结构：二叉链表：二叉链表：ADEBCF rootlchild data rchild结点结构结点结构: :C语言的类型描述：语言的类型描述：typedef struct BiTNode / 结点结构结点结构 TElemType d

22、ata; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;三叉链表：三叉链表：ADEBCF root parent lchild data rchild结点结构结点结构: :typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 struct TriTNode *parent; /双亲指针双亲指针 TriTNode, *TriTree;6.3.1 遍历二叉树遍历二叉树n问

23、题的提出：问题的提出： 顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中的结点，使二叉树中的结点，使得每个结点得每个结点均被访问一次均被访问一次，而且，而且仅被访问一次仅被访问一次。注意：此处注意：此处“访问访问”的含义可以很广，如：输出的含义可以很广，如：输出结点的信息等。结点的信息等。 “遍历遍历”是任何类型均有的操作，对线性结构而言，是任何类型均有的操作，对线性结构而言，只有一条搜索路径只有一条搜索路径( (因为每个结点均只有一个后继因为每个结点均只有一个后继) )，故不需要另加讨论。而二叉树是非线性结构，每个结故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍

24、历即按什么样的搜索路点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。径遍历的问题。6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树n三条搜索路径：三条搜索路径：先上后下先上后下的按层次遍历；的按层次遍历；先左先左(子树子树)后右后右(子树子树)的遍历；的遍历；先右先右(子树子树)后左后左(子树子树)的遍历。的遍历。n先左后右的遍历算法：先左后右的遍历算法：先先(根根)序的遍历算法序的遍历算法中中(根根)序的遍历算法序的遍历算法后后(根根)序的遍历算法序的遍历算法根根左左子树子树右右子树子树先先(根根)序的遍历算法：序的遍历算法：若二叉树为空树，则空操作；否则，若二叉树为空树，则

25、空操作；否则， 访问根结点；访问根结点； 先序遍历左子树；先序遍历左子树； 先序遍历右子树。先序遍历右子树。中中(根根)序的遍历算法：序的遍历算法：若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， 中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点； 中序遍历右子树。中序遍历右子树。后后(根根)序的遍历算法：序的遍历算法：若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问根结点。访问根结点。例如：例如：ABCDEFGHK先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B

26、 C D E F G H KB D C A E H G K FD C B H K G F E AFn算法的递归实现：算法的递归实现：void Preorder (BiTree T, void ( *visit)(TElemType e) / 先序遍历二叉树先序遍历二叉树 if (T) visit(T-data); / 访问结点访问结点 Preorder(T-lchild, visit); / 遍历左子树遍历左子树 Preorder(T-rchild, visit); / 遍历右子树遍历右子树 写法比较：写法比较：nint ( *visit)(TElemType &e)的含义：的含义：

27、visit是指针，指向是指针，指向int类型的函数类型的函数nint *visit(TElemType &e)的含义：的含义： visit是函数，其返回值为指向是函数，其返回值为指向int的指针的指针最简单的最简单的visit函数是：函数是：Void PrintElement(TElemType e) Printf(e);例：对应表达式例：对应表达式 a+b*(c-d)-e/fabcde-+/f-中序遍历中序遍历此二叉树，可得到此二叉树此二叉树，可得到此二叉树的中序序列为的中序序列为a+b*c-d-e/f (表达式的表达式的中缀中缀表示表示)若若先序遍历先序遍历二叉树，按访问结点的先后

28、二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的次序将结点排列起来，可得到二叉树的先序序列为先序序列为 -+a*b-cd/ef (表达式的表达式的前缀前缀表示表示波兰式波兰式)后序遍历后序遍历此二叉树，可得到此二叉树的后序序此二叉树，可得到此二叉树的后序序列为列为abcd-*+ef/- (表达式的表达式的后缀后缀表示表示逆波兰式逆波兰式)n遍历的递归执行过程：遍历的递归执行过程：例如：表达式例如：表达式a*b-c的二叉树如下的二叉树如下a-b*c-*abc-*abc-cb*aab*c-12先序序列：先序序列：-*abc中序序列：中序序列：a*b-c后序序列：后序序列：ab*c-n中序

29、遍历的非递归算法：中序遍历的非递归算法：BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T;-*abcab*c-12TTlchildTlchildlchildTlchildlchildlchildTtoptoptoptoptopTlchildlchildrchildTlchildrchildTlchildrchildlchildTlchildrchildrchildvoid Inorder_I(BiTree T, voi

30、d (*visit) (TelemType& e) Stack *S; t = GoFarLeft(T, S); / 找到最左下的结点找到最左下的结点 while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束栈空表明遍历结束 / while/ Inorder_I n遍历算法的应用举例：遍历算法的应用举例：统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数n

31、算法基本思想算法基本思想： 先序先序(或中序或后序或中序或后序)遍历二叉树，在遍历过程中查找叶遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中：子结点，并计数。由此，需在遍历算法中：增添增添一个一个“计数计数”的参数的参数；将算法中将算法中“访问结点访问结点”的的操作改为操作改为：若是：若是叶子，则计数叶子，则计数器增器增1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数对叶子结点计数 CountLeaf( T-lchild

32、, count); /统计左子树叶子结点统计左子树叶子结点 CountLeaf( T-rchild, count); /统计右子树叶子结点统计右子树叶子结点 / if / CountLeaf求二叉树的深度求二叉树的深度(后序遍历后序遍历)分析分析：二叉树的深度：二叉树的深度h和它的左、右子树深度之间的和它的左、右子树深度之间的关系？关系？n算法基本思想算法基本思想：先先分别分别求得左、右子树求得左、右子树的深度；的深度；算法中算法中“访问结点访问结点”的的操作为操作为：求得左、右子树深度的：求得左、右子树深度的最大值，然后加最大值，然后加 1 。int Depth (BiTree T ) /

33、返回二叉树的深度返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); /求左子树深度求左子树深度 depthRight= Depth( T-rchild ); /求右子树深度求右子树深度 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;h=maxhl, hr+1复制二叉树复制二叉树(后序遍历后序遍历)：n其基本操作为：生成一个结点其基本操作为：生成一个结点根元素根元素T左子树左子树右子树右子树根元素根

34、元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树n算法思想算法思想：复制左、右子树；复制左、右子树；“访问结点访问结点”的操作为：生成一个结点。的操作为：生成一个结点。n生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(1); T- data = item; T- lch

35、ild = lptr; T- rchild = rptr; return T;n复制：复制：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; newT = GetTreeNode(T-data, newlptr, newrptr);

36、return newT; / CopyTree例如：下列二叉树的复制过程如下例如：下列二叉树的复制过程如下ABCDEFGHK D C B H K G F E AnewTn建立二叉树的存储结构：建立二叉树的存储结构：基本要点：基本要点： n以以“遍历遍历”为基本出发点为基本出发点n不同的遍历方法相应地有不同的建立算法代码不同的遍历方法相应地有不同的建立算法代码以以字符串字符串的形式的形式“根左子树右子树根左子树右子树”定义一定义一棵二叉树棵二叉树例如：例如：ABCD以空白字符以空白字符“ ”表示表示A(B( ,C( , ),D( , )空树空树只含一个根结点的二叉树只含一个根结点的二叉树A以字符

37、串以字符串“A ”表示表示以下列字符串表示以下列字符串表示Status CreateBiTree(BiTree &T) /先序次序输入结点先序次序输入结点 scanf(&ch); if (ch= ) T = NULL; /第一个字符为空白字符第一个字符为空白字符 else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结点生成根结点 CreateBiTree(T-lchild); / 构造左子树构造左子树 CreateBiTree(T-rchild); / 构造右子树构

38、造右子树 return OK; / CreateBiTree上述算法的执行过程：上述算法的执行过程：A B C D A BCDATBCD由二叉树的由二叉树的先序和中序先序和中序序列建树：序列建树：n仅知仅知二叉树的二叉树的先序序列先序序列“abcdefg” ，不能不能唯一确定唯一确定一棵二叉树。一棵二叉树。n如果同时已知二叉树的中序序列如果同时已知二叉树的中序序列“cbdaegf”，则会，则会如何？如何？二叉树的二叉树的先序先序序列序列二叉树的二叉树的中序中序序列序列左子树左子树右子树右子树根根左子树左子树右子树右子树根根abcdefgcbdaegf例如：例如：a b c d e f gc b

39、 d a e g faab bccddeeffggabcdefg先序序列先序序列中序序列中序序列课后作业课后作业1. P41：6.286.3.2 线索二叉树线索二叉树n何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如例如:先序序列先序序列: A B C D E F G H K中序序列中序序列: B D C A H G K F E后序序列后序序列: D C B H K G F E A“前驱前驱”和和“后继后继”的信息是在遍历的过程中的信息是在遍历的过程中动态动态得到的，不同的遍历算法，确定的得到的，不同

40、的遍历算法，确定的“前驱前驱”和和“后继后继”是不同的！是不同的！保保 存存？指向该指向该线性序列中线性序列中的的“前驱前驱”和和 “后继后继” 的指针，的指针，称作称作“线索线索”。A B C D E F G H K D C B E 包含包含“线索线索”的存储结构，的存储结构，称作称作“线索链表线索链表”。与其相应的二叉树，称作与其相应的二叉树，称作“线索二叉树线索二叉树”。n对线索链表中结点的约定：对线索链表中结点的约定： 在二叉链表的结点中在二叉链表的结点中增加两个标志域增加两个标志域，并作如，并作如下规定：下规定：若该结点的若该结点的左子树不空左子树不空， 则则lchild域的指针指向

41、其左子树，且左标志域的值域的指针指向其左子树，且左标志域的值为为“指针指针 Link”；否则，；否则，lchild域的指针指向其域的指针指向其“前驱前驱”，且左标志的值为，且左标志的值为“线索线索 Thread” 。若该结点的若该结点的右子树不空右子树不空， 则则rchild域的指针指向其右子树，且右标志域的值域的指针指向其右子树，且右标志域的值为为 “指针指针 Link”；否则，；否则，rchild域的指针指向其域的指针指向其“后继后继”，且右标志的值为，且右标志的值为“线索线索 Thread”。 n线索链表的存储描述：线索链表的存储描述：typedef enum Link, Thread

42、PointerThr; / Link=0:指针，指针，Thread=1:线索线索typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左、右指针左、右指针 PointerThr LTag, RTag; / 左、右标志左、右标志 BiThrNode, *BiThrTree;lchild LTag data RTag rchildp对二叉树对二叉树以某种次序遍历以某种次序遍历使其变为线索二叉树的过程使其变为线索二叉树的过程称为称为线索化线索化。思考：一棵二叉树的线索二叉树是唯一的吗？思考：一棵二叉树

43、的线索二叉树是唯一的吗？二叉线索链表二叉线索链表n二叉线索链表的遍历：二叉线索链表的遍历： 添加了遍历中得到的添加了遍历中得到的“前驱前驱”和和“后继后继”的信的信息，从而简化了遍历的算法。息，从而简化了遍历的算法。for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);例如：对中序线索化链表的遍历算法。例如：对中序线索化链表的遍历算法。中序遍历的第一个结点中序遍历的第一个结点 ？ 左子树上处于左子树上处于“最左下最左下”(没有左子树没有左子树)的结点。的结点。在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？n若结点无右子树若结点无右子

44、树, 则则右链域所指右链域所指结点即结点即为其后继为其后继；n否则对其否则对其右子树右子树进行中序遍历，进行中序遍历，访问的第一个结点访问的第一个结点。void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / T是是头结点指针头结点指针，p指向根结点指向根结点 while (p != T) / 空树或遍历结束时，空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; / 找到序列中第一个结点找到序列中第一个结点 if (!Visit(p-data) re

45、turn ERROR;/访问左子树为空的结点访问左子树为空的结点 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 访问后继结点访问后继结点 p = p-rchild; / p进入其右子树根进入其右子树根 / InOrderTraverse_Thr例如例如: 表达式的中序线索化链表的遍历。表达式的中序线索化链表的遍历。abcde-+/f-NILNIL010000110000111111001111-+abcd-*ef/thrtbtpa + b * c - d - e / fppp判断标志域，然后沿着指针判断标志域，然后沿着指针/ /线索线索访问后继结点！访问后继结点！n如何建立线索链表？如何建立线索链表？在中序遍历过程