数据结构(严蔚敏)学习课件第6章.ppt

《数据结构(严蔚敏)学习课件第6章.ppt》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)学习课件第6章.ppt（176页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020年10月28日星期三,第1页,第六章 树和二叉树,2020年10月28日星期三,第2页,【课前思考】,上列家族谱系图可用如下关系表示： ， ，,2020年10月28日星期三,第3页,【学习目标】,1领会树和二叉树的类型定义，理解树和二叉树的结构差别。 2熟记二叉树的主要特性，并掌握它们的证明方法。3熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5熟练掌握二叉树和树的各种存储结构及其建立的算法。6学会编写实现树的各种操作的算法。7了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。,202

2、0年10月28日星期三,第4页,【重点和难点】,二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。,【知识点】,树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码,2020年10月28日星期三,第5页,【学习指南】,本章是整个课程的第二个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。本章必须完成的算法设计题为: 6.27,6.28,6.33,6.41,

3、6.43,6.45,6.46,6.47,6.49,6.50,6.51,6.57,6.59,6.68和6.66。,2020年10月28日星期三,第6页,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林的表示方法,6.7 树和森林的遍历,6.8 哈夫曼树与哈夫曼编码,2020年10月28日星期三,第7页,6.1 树的类型定义,树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继； （2）除根结点以外的其它n-1

4、结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,2020年10月28日星期三,第8页,ADT Tree 数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根

5、root的子树。,数据关系 R：,2020年10月28日星期三,第9页,基本操作：,查 找 类,插 入 类,删 除 类,ADT Tree,2020年10月28日星期三,第10页,Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, V

6、isit() ) / 遍历,2020年10月28日星期三,第11页,InitTree(n0,kielemtype R=r 其中，n为树中结点个数，若 n=0，则为一棵空树， n 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。,2020年10月28日星期三,第16页,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元

7、素 (一个前驱、 多个后继),2020年10月28日星期三,第17页,基 本 术 语,2020年10月28日星期三,第18页,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,H,I,J,M,2020年10月28日星期三,第19页,(从根到结点的)路径：,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点（即孩子结点）的层次为l

8、+1,树中叶子结点所在的最大层次,2020年10月28日星期三,第20页,任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,2020年10月28日星期三,第21页,6.2 二叉树的类型定义,2020年10月28日星期三,第22页,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,2020年10月28日星期三,第23页,二叉树的特点

9、： （1） 每个结点的度都不大于2，即每个结点的度为0、 1或2； （2） 每个结点的孩子结点次序不能任意颠倒。即每个孩子有左右之分。我们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。,2020年10月28日星期三,第24页,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,2020年10月28日星期三,第25页,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,2020年10月28日星期三,第26页,Root(T); Value(T, e); Parent(T, e); LeftChild(T, e);

10、 RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,查 找 类,2020年10月28日星期三,第27页,InitBiTree(,插 入 类,2020年10月28日星期三,第28页,ClearBiTree(,删 除 类,2020年10月2

11、8日星期三,第29页,二叉树的重要特性,2020年10月28日星期三,第30页,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,2020年10月28日星期三,第31页,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1

12、 = 2k-1 。,2020年10月28日星期三,第32页,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数(即边数) b = n1+2n2 而 n = b +1= b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,2020年10月28日星期三,第33页,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结

13、点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。,2020年10月28日星期三,第34页,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1-1 n 2k 1 或2k-1 n 2k 即 k-1 log2 n k, log2 n k log2 n +1 因为 k 只能是整数，因此， k =log2n + 1 。,2020年10月28日星期三,第35页,性质 5 ：,若对含 n 个

14、结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点；(2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,2020年10月28日星期三,第36页,可以用归纳法证明其中的（2）和（3）： 当i=1时，由完全二叉树的定义知，如果2i=2n，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2； 反之，如果2n，说明二叉树中

15、不存在序号为2的结点，其左孩子不存在。同理，如果2i+1=3n， 说明其右孩子存在且序号为3；如果3n，则二叉树中不存在序号为3的结点， 其右孩子不存在。 假设对于序号为j(1ji)的结点，当2jn时，其左孩子存在且序号为2j，当2jn 时，其左孩子不存在；当2j+1n时， 其右孩子存在且序号为2j+1，当2j+1n时，其右孩子不存在。,2020年10月28日星期三,第37页,当i=j+1时，根据完全二叉树的定义， 若其左孩子存在， 则其左孩子结点的序号一定等于序号为j的结点的右孩子的序号加1， 即其左孩子结点的序号等于 （2j+1）+1=2（j+1）=2i， 且有2in；如果2in， 则左孩

16、子不存在。 若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加1，即右孩子结点的序号为2i+1，且有2i+1n；如果2i+1n，则右孩子不存在。 故（2）和（3）得证。,2020年10月28日星期三,第38页,由（2）和（3）我们可以很容易证明（1）。 当i=1时， 显然该结点为根结点，无双亲结点。当i1时，设序号为i的结点的双亲结点的序号为m，如果序号为i的结点是其双亲结点的左孩子，根据（2）有i=2m，即m=i/2; 如果序号为i的结点是其双亲结点的右孩子，根据（3）有i=2m+1， 即m=（i-1）/2=i/2-1/2，综合这两种情况，可以得到，当i1时， 其双亲结点的序号

17、等于i/2 。证毕。,对完全二叉树，还有以下性质： （1）若结点j序号为奇数且不等于1，则它的左兄弟为j-1； （2）若结点j序号为偶数且不等于n，它的右兄弟为j+1； （3） 结点j所在层数(层次)为 log2j+1；,2020年10月28日星期三,第39页,6.3 二叉树的存储结构,二、二叉树的链式 存储表示,一、 二叉树的顺序 存储表示,二叉树的结构是非线性的， 每一结点最多可有两个后继。 二叉树的存储结构有两种： 顺序存储结构和链式存储结构。,2020年10月28日星期三,第40页,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemT

18、ype SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;,一、 二叉树的顺序存储表示,2020年10月28日星期三,第41页,例如:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。,2020年10月28日星期三,第42页,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,4线索链表,对于一棵二叉树,若采用顺序存

19、贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支,设高度为K,则需占用2K-1个存贮单元,而实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。,2020年10月28日星期三,第43页,A,D,E,B,C,F,root,lchild data rchild,结点结构:,1. 二叉链表,2020年10月28日星期三,第44页,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNod

20、e, *BiTree;,lchild data rchild,结点结构:,C 语言的类型描述如下:,2020年10月28日星期三,第45页,结论：若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域， 其中必有n1个空的链域。此结论证明如下： 证明：分支数目B=n-1，即非空的链域有n-1个，故空链域有2n-(n-1)=n+1个。 二叉链表的建立 为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设datatype 为char型）。 根据遍历方法，可采用相应的递归方法建立二叉树，如教科书P131算法6.4采用先序递归建立二叉树。 ,2020年10月28日星期三,第46页,Status

21、 CreateBiTree(BiTree / CreateBiTree,2020年10月28日星期三,第47页,A B C D,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,2020年10月28日星期三,第48页,下面讨论用队列（按层次进队出队）实现二叉树的建立。,假设二叉链表的数据类型描述如刚才所述，为建立二叉链表，用一个一维数组来模拟队列，存放输入的结点，但是，输入结点时，必须按完全二叉树形式，才能使结点间满足性质5，若为非完全二叉树，则必须给定一些假想结点(虚结点)，使之符合完全二叉树形式。为此，我们在输入结点值时，存在的结点则输入它对应的字符，不存在的结点(虚结点)，

22、输入逗号，最后以一个特殊符号 “#”作为输入的结束,表示建二叉链表已完成。建成的二叉链表可以由根指针root唯一确定。,2020年10月28日星期三,第49页,算法描述如下： #include typedef char DataType; typedef struct Node DataType data; struct Node *Lchild，*RChild; BiTNode, *BiTree; bitree *create() bitree *q100; /定义q数组作为队列存放二叉链表中结点，100为最大容量 bitree *s; /二叉链表中的结点 bitree *root ; /二

23、叉链表的根指针 int front=1,rear=0; /定义队列的头、尾指针,基本思想：用一个队列来存放所有结点（实结点或虚结点）。输入所有结点，并将其进队，若是实结点，则生成该结点将其作为队首结点的左或右孩子插入，若是虚结点，则以空指针进队。然后根据当前队尾判断是否出队，即根据性质5，当队尾为奇数时，队首的左右孩子已处理结束，应该出队。,2020年10月28日星期三,第50页,char ch; /结点的data域值 root=NULL; ch=getchar(); while(ch!=#) /输入值为#号,算法结束 s=NULL; if(ch!=,) /输入数据不为逗号,表示不为虚结点,否

24、则为虚结点 s=(bitree*)malloc(sizeof(BiTNode); s-data=ch; s-lchild=NULL; s-rchild=NULL; rear+; qrear=s; /新结点或虚结点进队 if(rear= =1) root=s; else if(s!=NULL) ,2020年10月28日星期三,第51页,例如，对下图左所示的二叉树，建立的二叉链表如右图所示。,对左图 (a)所示的二叉树，要用算法建成右图所示的二叉树链表，从键盘输入的数据应为：AB,C,D# 其中#为输入结束，为回车符。,2020年10月28日星期三,第52页,A,D,E,B,C,F,root,2三

25、叉链表,parent lchild data rchild,结点结构:,2020年10月28日星期三,第53页,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,2020年10月28日星期三,第54页,0 1 2 3 4 5 6,data parent,结点结构:,3双亲链表,

26、LRTag,L R R R L,Data:数据 Parent:指向双亲的指针 LRTag:左右孩子标志域,2020年10月28日星期三,第55页,typedef struct BPTNode / 结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根结点的位置 BPTree,2020年10月28日星期三,第56页,6.4

27、二叉树的遍历,2020年10月28日星期三,第57页,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、遍历算法的非递归描述,五、遍历算法的应用举例,2020年10月28日星期三,第58页,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结 点的信息等。,2020年10月28日星期三,第59页,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径

28、遍历的问题。,2020年10月28日星期三,第60页,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历； 2先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。,2020年10月28日星期三,第61页,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,2020年10月28日星期三,第62页,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,先（根）序的遍历算法：,2020年10月28日星期三,第63页,若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结

29、点； （3）中序遍历右子树。,中（根）序的遍历算法：,2020年10月28日星期三,第64页,若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后（根）序的遍历算法：,2020年10月28日星期三,第65页,最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+b*c）-d/e。该表达式用二叉树表示如下图所示。当对此二叉树进行先序、中序、后序遍历时，便可获得表达式的前缀、 中缀、 后缀书写形式： 前缀： -+a*bc/de 中缀： a+b*c-d/e 后缀： abc*+de/- 其中中缀形式是算术表达式的通常形式，只是没有括号。 前缀表

30、达式称为波兰表达式。算术表达式的后缀表达式被称作逆波兰表达式。 在计算机内， 使用后缀表达式易于求值。,图 算术式的二叉树表示,2020年10月28日星期三,第66页,三、算法的递归描述,void Preorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,2020年10月28日星期三,第67页,void Inorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,2020年10月28日星期三,第68页,void Postorder (BiTree T, void( *visit)(TElemType / 访

31、问结点 ,2020年10月28日星期三,第69页,四、遍历算法的非递归描述,利用一个一维数组作为栈，来存储二叉链表中结点。 算法思想为： 从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。,1. 先序遍历二叉树的非递归算法,2020年10月28日星期三,第70页,算法如下： void preorder1(bitree *root) bitree *p,*s100; int top=0; /top为栈顶指针 p=root; while(p!=

32、NULL)|(top0) while(p!=NULL) printf(“%c”,p-data); s+top=p; p=p-lchild; p=stop-; p=p-rchild; ,【算法】 先序遍历二叉树的非递归算法,2020年10月28日星期三,第71页,图 中序遍历二叉树的非递归算法处理流程,2. 中序遍历二叉树的非递归算法 利用一个一维数组作栈，来存贮二叉链表中结点。 算法思想为： 从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。,2020年10

33、月28日星期三,第72页,void InOrder（BiTree root）/* 中序遍历二叉树的非递归算法 */ InitStack ( ,【算法(a) 中序遍历二叉树的非递归算法(调用栈操作的函数)】,2020年10月28日星期三,第73页,/* sm 表示栈， top表示栈顶指针 */ void inorder(BiTree root) /* 中序遍历二叉树， root为二叉树的根结点 */ top=0; p=root; do do while(p! =NULL) top=top+1; stop=p; p=p-lchild ; /* 遍历左子树 */ if(top=0) p=stop;

34、top=top-1; Visit(p-data); /* 访问根结点 printf(“%c”,p-data); */ p=p-rchild; /* 遍历右子树 */ while(p! =NULL | top! =0) ,【算法(b) 中序遍历二叉树的非递归算法(直接实现栈操作),2020年10月28日星期三,第74页,3. 后序遍历二叉树的非递归算法 利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该结点还必须

35、再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。,2020年10月28日星期三,第75页,后序遍历二叉树的非递归算法如下： void postorder1( bitree *root) bitree *p,*s1100; /s1栈存放树中结点 int s2100,top=0,b; /s2栈存放进栈标志 p=root; do while(p!=NULL) s1top=p;s2top+=0; /第一次进栈标志为0 p=p-l

36、child; if(top0) b=s2-top; p=s1top;,2020年10月28日星期三,第76页,if(b=0) s1top=p;s2top+=1; /第二次进栈标志为1 p=p-rchild; else printf(“%c”,p-data); p=NULL; while(p!=NULL)|(top0); ,【算法 后序遍历二叉树的非递归算法(调用栈操作的函数)】,2020年10月28日星期三,第77页,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数 (先序遍历),2、求二叉树的深度(后序遍历),3、复制二叉树(后序遍历),4、建立二叉树的存储结构,2020年10月28日

37、星期三,第78页,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,2020年10月28日星期三,第79页,void CountLeaf (BiTree T, int / if / CountLeaf,2020年10月28日星期三,第80页,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左

38、、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,2020年10月28日星期三,第81页,int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,2020年10月28日星期三,第82页,3、复制二叉树,

39、其基本操作为：生成一个结点。,根元素,T,左子树,右子树,根元素,NEWT,左子树,右子树,左子树,右子树,(后序遍历),2020年10月28日星期三,第83页,BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; ,生成一个二叉树的结点 (其数据域为item,左指针域为lptr,右指针

40、域为rptr),2020年10月28日星期三,第84页,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); return newT; / CopyTree,2020年1

41、0月28日星期三,第85页,A,B,C,D,E,F,G,H,K, D ,C , B, H , K ,G, F ,E ,A,例如：下列二叉树的复制过程如下：,newT,2020年10月28日星期三,4、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,2020年10月28日星期三,第87页,以字符串的形式 根 左子树 右子树 定义一棵二叉树,例如:,A,B,C,D,以空白字符“ ”表示,A(B( ,C( , ),D( , ),空树,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示,2020年10月28日星期三,第88页,Status CreateBiTree(

42、BiTree / CreateBiTree,2020年10月28日星期三,第89页,A B C D,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,2020年10月28日星期三,第90页,按给定的表达式建相应二叉树, 由先缀表示式建树 例如：已知表达式的先缀表示式 -+ a b c / d e, 由原表达式建树 例如：已知表达式 (a+b)c d/e,2020年10月28日星期三,第91页,对应先缀表达式 -+ a b c / d e的二叉树,a,b,c,d,e,-,+,/,特点： 操作数为叶子结点 运算符为分支结点,2020年10月28日星期三,第92页,scanf( ,由先

43、缀表示式建树的算法的基本操作：,2020年10月28日星期三,第93页,a+b,(a+b)c d/e,a+bc,分析表达式和二叉树的关系:,a,b,+,a,b,c,+,a,b,c,+,(a+b)c,a,b,c,d,e,-,+,/,2020年10月28日星期三,第94页,基本操作:,scanf( ,2020年10月28日星期三,第95页,void CrtExptree(BiTree / CrtExptree, ,2020年10月28日星期三,第96页,switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= (

44、 ) CrtSubtree( t, c); / 建二叉树并入栈 Pop(S, c) break; defult : / switch, ,2020年10月28日星期三,第97页,while(!Gettop(S, c) ,2020年10月28日星期三,第98页,建叶子结点的算法为：,void CrtNode(BiTree ,2020年10月28日星期三,第99页,建子树的算法为：,void CrtSubtree (Bitree ,2020年10月28日星期三,第100页,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“

45、cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,2020年10月28日星期三,第101页,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,2020年10月28日星期三,第102页,void CrtBT(BiTree else / / CrtBT, ,Ps为先序序列的起始位置, is为中序序列的起始位置, n为结点数,2020年10月28日星期三,第103页,T=(BiTNode*)malloc(sizeof(BiTNod

46、e); T-data = preps; if (k=is) T-Lchild = NULL; else CrtBT(T-Lchild, pre, ino, ps+1, is, k-is ); if (k=is+n-1) T-Rchild = NULL; else CrtBT(T-Rchild, pre, ino, ps+1+(k-is), k+1, n-(k-is)-1 );,2020年10月28日星期三,第104页,6.5线索二叉树,何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？,2020年10月28日星期三,第105页,一、何谓线索二叉树？,遍历二叉树的结果是， 求得结点的一个线

47、性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列: 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,2020年10月28日星期三,第106页,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,与其相应的二叉树，称作 “线索二叉树”,包含 “线索” 的存储结构，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,2020年10月28日星期三,第107页,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域， 并作如下规定：,若该结点的左子树不空， 则Lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，Lc