《数据结构》课件第6章 树和二叉树

1、第6章 树和二叉树学习要点: 熟练掌握二叉树的结构特性熟悉二叉树的各种存储结构特点及使用范围熟练掌握各种遍历策略的递归和非递归算法，灵活运用遍历算法实现二叉树的其他操作熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法掌握树和森林与二叉树的转换方法学会编写实现树的各种操作的算法了解最优树的特性，掌握建立最优树和哈夫曼编码的方法6.1 树的定义和基本术语6.1.1 树的定义树型结构：非线性结构：至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构。用于描述层次结构的关系：人类的族谱、操作系统的文件系统、Internet中的DNS(域名系统)等分等级的

2、分类方案均可用层次结构来表示，可由此导出树型结构。树的定义： 是n(n0)个结点的有限集合T，对于任意一棵非空树，它满足：有且仅有一个特定的称为根(root)的结点；当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，.，Tm，其中每个集合本身又是一棵树，称为根的子树。上述树的定义是一个递归定义。例如：ABCDEFGHIJMKLA树的类型定义：ADT Tree 数据对象：D是具有相同特性的数据元素的集合。 数据关系：若D为空集，则称为空树；否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , T

3、m, 其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 基本操作：查找类插入 删除 ADT Tree查找类：Root(T) / 求树的根结点 Value(T, cur_e) / 求当前结点的元素值Parent(T, cur_e) / 求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子RightSibling(T, cur_e) / 求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树TreeDepth(T) / 求树的深度TraverseTree( T, Visit() ) / 遍历插入：InitTree(&T) / 初始化置空树C

4、reateTree(&T, definition) / 按定义构造Assign(T, cur_e, value) / 给当前结点赋值InsertChild(&T, &p, i, c) / 将以c为根的树插入为结 /点p的第i棵子树删除：ClearTree(&T) / 将树清空DestroyTree(&T) / 销毁树的结构DeleteChild(&T, &p, i) / 删除结点p的第i棵子例如：ABCDEFGHIJMKL(A( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根T1T2T36.1.2 基本术语结点：包含一个数据元素及若干指向其子树的分支。结点

5、的度：结点拥有的子树数。如图： A的度为3， C的度为1， E的度为0。叶子(或终端)结点：度为零的结点。分支(或非终端)结点：度大于零的结点。ABCDEFGHIJMKL树的度：树中所有结点的度的最大值。结点的子树的根称为该结点的孩子(child) 。相应的，该结点称为孩子的双亲(parent)。如图所示，树的度为3；D为A的子树T3的根，则D是A的孩子，而A则是D的双亲。同一个双亲的孩子之间互 称兄弟。如图所示中，H、I、J互称为兄弟。ABCDEFGHIJMKLE、G、H互称兄弟？双亲在同一层的结点互为堂兄弟。结点的层次：根结点的层次为1，第l层的结点的子树的根结点的层次为l+1。树的深度：

6、树中叶子结点所在的最大层次。森林：是m(m0)棵互不相交的树的集合。任何一棵非空树是一个二元组Tree = (root，F)其中： root 被称为根结点 F 被称为子树森林ArootBCDEFGHIJMKLF有序树：子树之间存在确定的次序关系。(树中结点的各子树从左到右是有次序的，即不能互换)。无序树：子树之间不存在确定的次序关系。树型结构和线性结构的特点：线性结构树型结构第一个数据元素 (无前驱) 根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素(一个前驱、 一个后继)其它数据元素(一个前驱、 多个后继)6.2.1 二叉树的定义定义：是n(n=0)个结点的

7、有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分。6.2 二叉树ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的抽象数据类型定义：ADT BinaryTree 数据对象：D是具有相同特性的数据元素的集合。 数据关系：若D为空集，则称为空树；否则: (1) 在D中存在唯一的称为根的数据元素root, . 基本操作：查找类插入 删除ADT BinaryTree 详细说明见教材P121P1

8、236.2.2 二叉树的性质性质1 ：在二叉树的第 i 层上至多有2i-1 个结点(i1)。证明：(归纳法)归纳基：i = 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 。命题成立(证毕)性质2：深度为 k 的二叉树上至多含 2k-1 个结点(k1)。证明：基于性质1，深度为 k 的二叉树上的结点数至多为：20+21+ +

9、2k-1 = 2k-1 。性质3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为2的结点，则必存在关系式：n0 = n2+1。证明：设二叉树上结点总数 n = n0 + n1 + n2， 二叉树上分支总数 b = n1+2n2， 而 b = n-1 = n0 + n1 + n2 1 由， n0 = n2 + 1 。除根结点外，其余结点都有一个分支进入，设b为分支总数，则n=b+1。两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。123456789101112131415abcde

10、fghij特点：是每一层上的结点数都是最大结点数。特点：叶子结点只可能在层次最大的两层出现；对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l或l+1。完全二叉树的性质：性质4：具有n个结点的完全二叉树的深度为 log2n +1。证明：设完全二叉树的深度为k，则根据性质2(深度为k的二叉树至多有2k-1个结点) 得 2k-1-1 n 2k 1，或： 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。i/2 i 2i 2i

11、+1 i+1 2i+2 2i+3 i+1 2i+2 2i+3 i2i2i+1 .性质练习：1. 一棵二叉树在其第五层中有17个结点，可不可能？2. 二叉树的根结点属于第0层还是属于第1层？3. 已知一棵二叉树有20个结点，其中6个结点为叶子，则该树中度为2的结点数为 ？度为0的结点为 ？4. 已知一棵完全二叉树中编号为101的结点有LC和RC结点，则其LC结点编号为 ，RC结点编号为 ？5. 一棵深度为h的完全k叉树，如果按层次自顶向下、同一层自左向右、顺序从1开始对全部结点进行编号，试问：该树上最多有多少个结点？最少有多少个结点？第i层上至多有2i-1个结点，则25-1=16。所以，不可能。

12、第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(要求：写出推导过程)6.2.3 二叉树的存储结构顺序存储结构：#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_S

13、IZE; / 0号单元存储根结点SqBiTree bt;特点：一组地址连续的存储单元存储各结点(定义一个一维数组)；自根而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储。例如：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的一维数组。缺点：空间利用率太低！链式存储结构：二叉链表：ADEBCFrootlchild data rchild结点结构:C语言的类型描述：typedef struct BiTNode / 结点结构 TE

14、lemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;三叉链表：ADEBCFrootparent lchild data rchild结点结构:typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;6.3.1 遍历二叉树问题的提出： 顺着某一条搜索路径巡访二叉树中的结点，使得每个结

15、点均被访问一次，而且仅被访问一次。注意：此处“访问”的含义可以很广，如：输出结点的信息等。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。6.3 遍历二叉树和线索二叉树三条搜索路径：先上后下的按层次遍历；先左(子树)后右(子树)的遍历；先右(子树)后左(子树)的遍历。先左后右的遍历算法：先(根)序的遍历算法中(根)序的遍历算法后(根)序的遍历算法根左子树右子树先(根)序的遍历算法：若二叉树为空树，则空操作；否则， 访问根结点； 先序遍历左子树

16、； 先序遍历右子树。中(根)序的遍历算法：若二叉树为空树，则空操作；否则， 中序遍历左子树； 访问根结点； 中序遍历右子树。后(根)序的遍历算法：若二叉树为空树，则空操作；否则， 后序遍历左子树； 后序遍历右子树； 访问根结点。例如：ABCDEFGHK先序序列：中序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E AF算法的递归实现：void Preorder (BiTree T, void ( *visit)(TElemType e) / 先序遍历二叉树 if (T) visit(T-data); / 访问结点 Preorde

17、r(T-lchild, visit); / 遍历左子树 Preorder(T-rchild, visit); / 遍历右子树 写法比较：int ( *visit)(TElemType &e)的含义： visit是指针，指向int类型的函数int *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 (表达式的中缀表示)若

18、先序遍历二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序序列为 -+a*b-cd/ef (表达式的前缀表示波兰式)后序遍历此二叉树，可得到此二叉树的后序序列为abcd-*+ef/- (表达式的后缀表示逆波兰式)遍历的递归执行过程：例如：表达式a*b-c的二叉树如下a-b*c-*abc-*abc-cb*aab*c-12先序序列：-*abc中序序列：a*b-c后序序列：ab*c-中序遍历的非递归算法：BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T

19、= T-lchild; return T;-*abcab*c-12TTlchildTlchildlchildTlchildlchildlchildTtoptoptoptoptopTlchildlchildrchildTlchildrchildTlchildrchildlchildTlchildrchildrchildvoid Inorder_I(BiTree T, void (*visit) (TelemType& e) Stack *S; t = GoFarLeft(T, S); / 找到最左下的结点 while(t) visit(t-data); if (t-rchild) t = GoF

20、arLeft(t-rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束 / while/ Inorder_I 遍历算法的应用举例：统计二叉树中叶子结点的个数算法基本思想： 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中：增添一个“计数”的参数；将算法中“访问结点”的操作改为：若是叶子，则计数器增1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchil

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

22、d ); /求左子树深度 depthRight= Depth( T-rchild ); /求右子树深度 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;h=maxhl, hr+1复制二叉树(后序遍历)：其基本操作为：生成一个结点根元素T左子树右子树根元素NEWT左子树右子树左子树右子树算法思想：复制左、右子树；“访问结点”的操作为：生成一个结点。生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode *GetTreeNode(TElemTyp

23、e item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T;复制：BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /复制左子树 else newlptr = NULL; if (T-rchild ) newr

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

25、以下列字符串表示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); / 构造右子树 return OK; / CreateBiTree上述算法的执行过程：A B C D ABCDATBCD由二叉树的

26、先序和中序序列建树：仅知二叉树的先序序列“abcdefg” ，不能唯一确定一棵二叉树。如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树右子树根左子树右子树根abcdefgcbdaegf例如：a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列中序序列课后作业1. P41：6.286.3.2 线索二叉树何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列: A B C D E F G H K中序序列: B D C A H G K F E后序序列: D C B

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

28、， 则rchild域的指针指向其右子树，且右标志域的值为 “指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。 线索链表的存储描述：typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左、右指针 PointerThr LTag, RTag; / 左、右标志 BiThrNode, *BiThrTree;lchild LTag d

29、ata RTag rchild对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。思考：一棵二叉树的线索二叉树是唯一的吗？二叉线索链表二叉线索链表的遍历： 添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);例如：对中序线索化链表的遍历算法。中序遍历的第一个结点 ？ 左子树上处于“最左下”(没有左子树)的结点。在中序线索化链表中结点的后继 ？若结点无右子树, 则右链域所指结点即为其后继；否则对其右子树进行中序遍历，访问的第一个结点。void InOrderTraverse_

30、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) return ERROR;/访问左子树为空的结点 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 访问后继结点 p = p-rchild; / p进入其右子树根 / InO

31、rderTraverse_Thr例如: 表达式的中序线索化链表的遍历。abcde-+/f-NILNIL010000110000111111001111-+abcd-*ef/thrtbtpa+b*c-d-e/fppp判断标志域，然后沿着指针/线索访问后继结点！如何建立线索链表？在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中：附设指针pre, 并始终保持pre指向当前访问的结点；另设指针p指向当前递归调用中正在访问的结点，则pre指向p的前驱。void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子