数据结构PPT树和二叉树学习教案

1、会计学1数据结构数据结构(sh j ji u)PPT树和二叉树树和二叉树第一页，共188页。 引 言第1页/共188页第二页，共188页。第2页/共188页第三页，共188页。6.1 树的定义树的定义 和基本和基本(jbn)术语术语第3页/共188页第四页，共188页。 树的定义(dngy)第4页/共188页第五页，共188页。第5页/共188页第六页，共188页。数据数据(shj)对象对象 D：D是具有相同特性的数据元素是具有相同特性的数据元素(yun s)的集合。的集合。 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分

2、为(fn wi)m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系数据关系 R：ADT Tree第6页/共188页第七页，共188页。 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类第7页/共188页第八页，共188页。 Root(T) / 求树的根结点(ji din) 查找查找(ch zho)类：类：Value(T, cur_e) / 求当前求当前(dngqin)结点的元素值结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild

3、(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历第8页/共188页第九页，共188页。InitTree(&T) / 初始化置空树初始化置空树 插入插入(ch r)类：类：CreateTree(&T, definition) / 按定义按定义(dngy)构造树构造树Assign(T, cur_e,

4、value) / 给当前给当前(dngqin)结点赋值结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树第9页/共188页第十页，共188页。 ClearTree(&T) / 将树清空(qn kn) 删除删除(shnch)类：类：DestroyTree(&T) / 销毁销毁(xiohu)树的结构树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树第10页/共188页第十一页，共188页。 树的表示(biosh)形式第1

5、1页/共188页第十二页，共188页。ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根(sh n)例如例如(lr):(lr):第12页/共188页第十三页，共188页。第13页/共188页第十四页，共188页。基基 本本 术术 语语第14页/共188页第十五页，共188页。结点结点(ji din):(ji din):结点结点(ji din)(ji din)的度的度: :树的度树的度: :叶子叶子(y zi)(y zi)结点结点: :分支结点分支结点: :数据元素及若干指向子树的分支拥有的子树数树中所有结点的度的最大值度为零的结

6、点度大于零的结点DHIJM第15页/共188页第十六页，共188页。(从根到结点(ji din)的)路径：结点结点(ji din)(ji din)的层次的层次: :树的深度树的深度(shnd)： 由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点第16页/共188页第十七页，共188页。() 有确定(qudng)的根；

7、() 树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定(qudng)的次序关系。无序无序(w x)树：树：子树之间不存在确定的次序关系。第17页/共188页第十八页，共188页。任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为(chn wi)根结点 F 被称为(chn wi)子树森林森林森林(snln)：是m（m0）棵互不相交(xingjio)的树的集合ArootBCDEFGHIJMKLF第18页/共188页第十九页，共188页。对比对比(dub)树型结构和线性树型结构和线性结构的结构特点结构的结构特点第19页/共188页第二十页，共

8、188页。线性结构线性结构(jigu)树型结构树型结构(jigu)第一个数据元素第一个数据元素(yun s)(yun s) ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )第20页/共188页第二十一页，共188页。6.2 二二 叉叉 树树第21页/共188页第二十二页，共188页。6.2.1 二叉树的定义二叉树的定义 二叉树（二叉树

9、（Binary Tree）或为空）或为空树，或是由一个根结点加上两树，或是由一个根结点加上两棵分别棵分别(fnbi)称为左子树和右称为左子树和右子树的、互不相交的二叉树组子树的、互不相交的二叉树组成。成。ABCDEFGHK根结点(ji din)左子树右子树第22页/共188页第二十三页，共188页。二叉树的五种基本二叉树的五种基本(jbn)形态：形态：N空树空树只含根结点只含根结点(ji din)NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右左右(zuyu)子树子树均不为均不为空树空树第23页/共188页第二十四页，共188页。第24页/共188页第二十五页，共188页。二

10、叉树的主要二叉树的主要(zhyo)基本操作：基本操作：查查 找找 类类插插 入入 类类删删 除除 类类第25页/共188页第二十六页，共188页。 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(

11、); LevelOrderTraverse(T, Visit();第26页/共188页第二十七页，共188页。 InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);第27页/共188页第二十八页，共188页。ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);第28页/共188页第二十九页，共188页。6.2.2 二叉树二叉树 的性质的性质(xngzh)第29页

12、/共188页第三十页，共188页。用归纳法证明用归纳法证明(zhngmng)： 归纳基：归纳基： 归纳假设：归纳假设： 归纳证明归纳证明(zhngmng)：i = 1 层时，只有一个层时，只有一个(y )根结点：根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。第30页/共188页第三十一页，共188页。证明证明(zhngmng)： 基于上一条性质(xngzh)，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。第31页/共188页第三十二页，共18

13、8页。证明证明(zhngmng)：设设 二叉树上结点总数二叉树上结点总数(zngsh) n = n0 + n1 + n2又又 二叉树上分支总数二叉树上分支总数(zngsh) b = n1+2n2 而而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。第32页/共188页第三十三页，共188页。两类特殊两类特殊(tsh)的二叉树：的二叉树：满二叉树：指的是满二叉树：指的是深度深度(shnd)为为k且且含有含有2k-1个结点的个结点的二叉树。二叉树。完全完全(wnqun)二叉树：树中所二叉树：树中所含的含的 n 个结点和个结点和满二叉树中编号满二叉树中编

14、号为为 1 至至 n 的结点的结点一一对应。一一对应。12345678910111213 1415abcdefghij第33页/共188页第三十四页，共188页。 性质性质 4 ： 具有具有 n 个结点个结点(ji din)的完全的完全二叉树的深度为二叉树的深度为 log2n +1 。证明证明(zhngmng)：设完全二叉树的深度为设完全二叉树的深度为 k 则根据则根据(gnj)第二条性质得第二条性质得 2k-1 n 2k 即即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为

15、其右孩子结点。第35页/共188页第三十六页，共188页。第36页/共188页第三十七页，共188页。6.2.3 二叉树的存储二叉树的存储(cn ch)结构结构二、二叉树的链式二、二叉树的链式 存储存储(cn ch)(cn ch)结构结构一、一、 二叉树的顺序二叉树的顺序(shnx) 存储结构存储结构第37页/共188页第三十八页，共188页。#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元号单元(dnyun)存储根结存储根结点点SqBiTree bt;一

16、、一、 二叉树的顺序存储结构二叉树的顺序存储结构(jigu)第38页/共188页第三十九页，共188页。左到右地给结点编号，就能得到一左到右地给结点编号，就能得到一个足以反映整个二叉树结构的线性个足以反映整个二叉树结构的线性序列，如下图所示。序列，如下图所示。二叉树的顺序存储结构二叉树的顺序存储结构(jigu)第39页/共188页第四十页，共188页。第40页/共188页第四十一页，共188页。第41页/共188页第四十二页，共188页。第42页/共188页第四十三页，共188页。练习练习(linx):ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 1

17、2 131401326第43页/共188页第四十四页，共188页。二、二叉树的链式存储二、二叉树的链式存储(cn ch)(cn ch)表示表示1. 1. 二叉链表二叉链表2三叉链表三叉链表3 3双亲双亲(shungqn)(shungqn)链表链表4线索线索(xin su)链表链表第44页/共188页第四十五页，共188页。ADEBCF rootlchild data rchild结点结点(ji din)结构结构:1. 1. 二叉链表二叉链表二叉链表二叉链表第45页/共188页第四十六页，共188页。ABCDEF二叉树二叉树第46页/共188页第四十七页，共188页。typedef struct

18、 BiTNode / 结点结点(ji din)结构结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结点(ji din)结构结构:C 语言(yyn)的类型描述如下:第47页/共188页第四十八页，共188页。ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结点(ji din)结构结构:第48页/共188页第四十九页，共188页。 typedef struct TriTNode / 结点(ji

19、 din)结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结点(ji din)结构结构:C 语言的类型(lixng)描述如下:第49页/共188页第五十页，共188页。0123456B2C0A -1D2E3F4 data parent结点结点(ji din)结构结构:3 3双亲双亲(shungqn)(shungqn)链表链表LRTagLRRRL第50页/共188页第五

20、十一页，共188页。 typedef struct BPTNode / 结点结构(jigu) TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构(jigu) BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根结点的位置 BPTree第51页/共188页第五十二页，共188页。6.3.1二叉树的遍历二叉树的遍历(bin l)6.3 遍历遍历(bin l)二二叉树和线索二叉树叉树和线

21、索二叉树第52页/共188页第五十三页，共188页。一、问题一、问题(wnt)的提出的提出二、先左后右的遍历二、先左后右的遍历(bin l)算法算法三、算法三、算法(sun f)的递归描述的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例第53页/共188页第五十四页，共188页。 如何按着某条搜索路径巡访二叉如何按着某条搜索路径巡访二叉树中的每个结点，使得树中的每个结点，使得(sh de)每个结每个结点均被访问一次，而且仅被访问一次。点均被访问一次，而且仅被访问一次。一、问题一、问题(wnt)的提出的提出“访问访问(fngwn)”的含

22、义可以很广，如：输出结的含义可以很广，如：输出结点的信息等。点的信息等。第54页/共188页第五十五页，共188页。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要(xyo)另加讨论。而二叉树是非线性结构， 每个结点有两个后继，每个结点有两个后继，则存在如何则存在如何(rh)遍历即按什么样的搜索遍历即按什么样的搜索路径遍历的问题。路径遍历的问题。第55页/共188页第五十六页，共188页。二叉树的遍历方法二叉树的遍历方法 二叉树由根、左子树、右子树三部分二叉树由根、左子树、右子树三部分(b fen)(b fen)组成组成 二叉树的遍历可以

23、分解为：访问根，遍历左子树和遍历右二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树子树令：令：L L：遍历：遍历(bin l)(bin l)左子左子树树 D D：访问根结点：访问根结点 R R：遍历：遍历(bin l)(bin l)右子右子树树 有六种遍历有六种遍历(bin l)(bin l)方方法：法： DLR DLR，LDRLDR，LRDLRD， DRL DRL，RDLRDL，RLDRLD 约定先左后右,有三种遍历方法(fngf)： DLR、LDR、LRD ，分别称为 先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B第56页/共188页第五十七页，

24、共188页。58 先序遍历(bin l)（ DLR ） 若二叉树非空 （1）访问根结点； （2）先序遍历(bin l)左子树； （3）先序遍历(bin l)右子树； 先序遍历先序遍历(bin l)(bin l)序列：序列： A A F F G G E E D D C C B B例：先序遍历例：先序遍历(bin l)(bin l)右图所示的二叉树右图所示的二叉树 （1 1）访问根结点）访问根结点A A （2 2）先序遍历）先序遍历(bin l)(bin l)左子树：即按左子树：即按DLRDLR的顺序遍历的顺序遍历(bin l)(bin l)左子树左子树 （3 3）先序遍历）先序遍历(bin l)

25、(bin l)右子树：即按右子树：即按DLRDLR的顺序遍历的顺序遍历(bin l)(bin l)右子树右子树ABCDFGE二、先左后右的遍历算法二、先左后右的遍历算法第57页/共188页第五十八页，共188页。59中序遍历（中序遍历（ LDR LDR ）若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问）访问(fngwn)(fngwn)根结点根结点（3 3）中序遍历右子树）中序遍历右子树 中序遍历中序遍历(bin l)(bin l)序列：序列： A A F F G G E E D D C C B B例：中序遍历右图所示的二叉树例：中序遍历右图所示的二叉树 （1 1

26、）中序遍历左子树：即按）中序遍历左子树：即按LDRLDR的顺序的顺序(shnx)(shnx)遍历左子树遍历左子树 （2 2）访问根结点）访问根结点 A A （3 3）中序遍历右子树：即按）中序遍历右子树：即按LDRLDR的顺序的顺序(shnx)(shnx)遍历右子树遍历右子树DBCGFAE第58页/共188页第五十九页，共188页。60后序遍历（后序遍历（LRDLRD）若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问）访问(fngwn)(fngwn)根结点根结点 后序后序(hu x)(hu x)遍历序列：遍历序列：例：后序遍

27、历右图所示的二叉树例：后序遍历右图所示的二叉树 （1 1）后序遍历左子树：即按）后序遍历左子树：即按LRDLRD的顺序的顺序(shnx)(shnx)遍历左子树遍历左子树 （2 2）后序遍历右子树：即按）后序遍历右子树：即按LRDLRD的顺序的顺序(shnx)(shnx)遍历右子树遍历右子树 （3 3）访问根结点）访问根结点 A A A A F F G G E E D D C C B BDGCEAFB第59页/共188页第六十页，共188页。61 e e d d c c b b f f a a + + * * / / - - - - 后序遍历后序遍历(bin l)(bin l)序列：序列： 中序

28、遍历中序遍历(bin l)(bin l)序列：序列： 先序遍历先序遍历(bin l)(bin l)序序列：列：例：先例：先中序遍历序遍历、中序遍历、中序遍历序遍历、中序遍历、后后序遍历下图所示的二叉树序遍历下图所示的二叉树前缀表达式前缀表达式中缀表达式中缀表达式后缀表达式后缀表达式-+a* b-cd/e fa+b* c-d-e /fa bcd-*+ef/-第60页/共188页第六十一页，共188页。R A DE C HF GBK练习：求下列二叉链表和二叉树的三种练习：求下列二叉链表和二叉树的三种(sn zhn)(sn zhn)遍历次序遍历次序ABCDEFGHK第61页/共188页第六十二页，共

29、188页。这实际上是先序遍历的递归定义这实际上是先序遍历的递归定义(dngy)(dngy)，我们知道递归定义，我们知道递归定义(dngy)(dngy)包括两个部分：包括两个部分：1 1）基本项（也叫终止项）；）基本项（也叫终止项）； 2 2）递归项）递归项 若二叉树非空若二叉树非空 （1 1）访问）访问(fngwn)(fngwn)根结点；根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；先序遍历先序遍历(bin l)(bin l)递归定义递归定义递归项递归项上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以上面介绍了三种遍历方法，显然

30、是用递归的方式给出的三种遍历方法，以先序为例：先序为例：先序遍历（先序遍历（D DL LR R）的定义：）的定义：该定义隐含着该定义隐含着若二叉树为空，结束若二叉树为空，结束 三、算法的递归描述三、算法的递归描述第62页/共188页第六十三页，共188页。上面先序遍历的定义等价上面先序遍历的定义等价(dngji)(dngji)于：于：若二叉树为空，结束若二叉树为空，结束 基本项（也叫终止项）基本项（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树； 下面给出先序、中序、

31、后序遍历递归算法，为了增加算法的可读下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错性，这里对书上算法作了简化，没有考虑访问结点出错(ch cu)(ch cu)的情况（即我们假设调用函数的情况（即我们假设调用函数visit( )visit( )访问结点总是成功的。访问结点总是成功的。第63页/共188页第六十四页，共188页。1先序遍历递归算法先序遍历递归算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visi

32、t( )是访问结点的函数。本算法是访问结点的函数。本算法/先序遍历以为根结点指针的二叉树，对每个数据元素调用函数先序遍历以为根结点指针的二叉树，对每个数据元素调用函数/Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，访问根结点；遍历左子树，遍历右子树若二叉树不为空，访问根结点；遍历左子树，遍历右子树 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse最简单的最简单的Visit函数是：函数是：

33、 Status PrintElement(TElemType e) /输出元素输出元素e的值的值 printf(e); return OK; D D A A B B C C E E FFT T第64页/共188页第六十五页，共188页。2 中序遍历递归算法中序遍历递归算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中序遍历是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据以为根结点指针的二叉树，对每个数据(shj

34、)元素调用函数元素调用函数Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，访问根结点，遍历右子树若二叉树不为空，遍历左子树，访问根结点，遍历右子树 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse 你能写出后序遍历你能写出后序遍历(bin l)(bin l)递归算法了吧递归算法了吧? ?第65页/共188页第六十六页，共188页。3 后序遍历递归算法后序遍历递归算法(sun f)

35、void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法是访问结点的函数。本算法(sun f)中序遍历以为根结点指针的二叉树，对每个数据元素调用中序遍历以为根结点指针的二叉树，对每个数据元素调用函数函数Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，遍历右子树，访问根结点若二叉树不为空，遍历左子树，遍历右子树，访问根结点 PostOrderTraverse(T-lchild

36、, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse 第66页/共188页第六十七页，共188页。G HD E FB CA第67页/共188页第六十八页，共188页。四、中序遍历四、中序遍历(bin l)算法的非递归描述算法的非递归描述Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数函数.中序遍历二叉树中序遍历二叉

37、树T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调/用函用函数数Visit。 InitStack(S); Push(S, T); / 根指针进栈根指针进栈 while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); / 向左走到尽头向左走到尽头 Pop(S, p); / 空指针退栈空指针退栈 if (!StackEmpty(S) / 访问结点访问结点(ji din)，向右一步向右一步 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchil

38、d); return OK; / InOrderTraverse第68页/共188页第六十九页，共188页。Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数。函数。中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调/用函数用函数Visit。 InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p =

39、p-lchild; / 非空指针进栈，继续非空指针进栈，继续(jx)左进左进 else /上层指针退栈，访问其所指结点，再向右进上层指针退栈，访问其所指结点，再向右进 Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse第69页/共188页第七十页，共188页。ABCDGEFABCNULLSGetToplchild)& (!T-rchild) count+; / 对叶子对叶子(y zi)结点计数结点计数 CountLeaf( T-lchild, count); Cou

40、ntLeaf( T-rchild, count); / if / CountLeaf第73页/共188页第七十四页，共188页。2、求二叉树的深度、求二叉树的深度(shnd)(后序遍历后序遍历)算法基本算法基本(jbn)(jbn)思想思想: : 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问(fngwn)结点”的操作为：求得左、右子树深度的最大值，然后加 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子树右子树深度深度之间的关系。第74页/共188页第七十五页，共188页。int Depth (BiTree T )

41、 / 返回返回(fnhu)二叉二叉树的深度树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;第75页/共188页第七十六页，共188页。3、复制、复制(fzh)二叉树二叉树其基本操作为：生成一个其基本操作为：生成一个(y )(y )结点。结点。根元素根元素(yun s)T左子树左子树右子树右子树根

42、元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树(后序遍历后序遍历)第76页/共188页第七十七页，共188页。BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点(ji din)(其数据域为其数据域为item,左

43、指针域为左指针域为lptr,右指针域为右指针域为rptr)第77页/共188页第七十八页，共188页。BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制(fzh)左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制(fzh)右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr

44、); return newT; / CopyTree第78页/共188页第七十九页，共188页。ABCDEFGHK D C B H K G F E A例如：下列例如：下列(xili)(xili)二叉树二叉树的复制过程如下：的复制过程如下：newT第79页/共188页第八十页，共188页。 为二叉树建立二叉链表 输入(shr)：二叉树的先序序列 结果：二叉树的二叉链表 遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有。是否可在利用遍历，建立二叉链表的所有(suyu)结点并完结点并完成相应结点的链接？

45、成相应结点的链接？基本思想基本思想：输入（输入（在空子树处添加在空子树处添加* *的二叉树的）先序序列（设每个元素是的二叉树的）先序序列（设每个元素是一一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接链接第80页/共188页第八十一页，共188页。 D D A A B B C C E E F F T T 先序序列(xli)：A B D F C E（在空子树处添加（在空子树处添加(tin ji)(tin ji)* *的二叉树的）先序序列：的二叉树的）先序序列： A B D A B D * * F F * * *

46、 * * *C E C E * * * * * * A A F F E E D D C C B B* A A F F E E D D C C B B第81页/共188页第八十二页，共188页。Status CreateBiTree(BiTree &T) /输入（在空子(kng zi)树处添加*的二叉树的）先序序列（设每个元/素是一个字 符）按先序遍历的顺序，建立二叉链表，并将/该二叉链表根结点指针赋给T scanf (&ch); if (ch= = * )T=NULL; / 若ch= = * 则T=NULL返回 else / 若ch! = * if (! (T=(BiTNode

47、 * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（根）结点 CreateBiTree(T-lchild); /构造左子树 CreateBiTree(T-rchild); /构造右子树 return OK;/CreateBiTree第82页/共188页第八十三页，共188页。84分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外(ln wi)，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉

48、树：由二叉树的先序和中序序列由二叉树的先序和中序序列(xli)建立二叉树建立二叉树二叉树的先序序列(xli)二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根第83页/共188页第八十四页，共188页。851.1.用前序序列的第一个结点用前序序列的第一个结点(ji din)(ji din)作为根结作为根结点点(ji din);(ji din);2.2.在中序序列中查找根结点的位置在中序序列中查找根结点的位置(wi zhi)(wi zhi)，并以此为，并以此为界将中序序列划分为左、右两个序列界将中序序列划分为左、右两个序列( (左、右子树左、右子树););3.3.根据左、右

49、子树的中序序列中的结点根据左、右子树的中序序列中的结点(ji din)(ji din)个数，个数，将前序序列去掉根结点将前序序列去掉根结点(ji din)(ji din)后的序列划分为左、右两后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列个序列，它们分别是左、右子树的前序序列; ;4.4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。得左、右子树为空。假设前序序列为假设前序序列为ABDGHCEFIABDGHCEFI，中序序列为中序序列为GDHBAECIFGDHBAECIF， 则得到的二叉树如下

50、页所示则得到的二叉树如下页所示第84页/共188页第八十五页，共188页。861. A1. A为根结点为根结点(ji din)(ji din)A BDGH CEFI GDHB A ECIF BDGHCEFIA2. B2. B为左子树的根结点为左子树的根结点(ji din)(ji din)B DGHGDH BCEFIDHGBA3. D3. D为左子树的左子树为左子树的左子树的根结点的根结点(ji din)(ji din) A B G H D C E F I 第85页/共188页第八十六页，共188页。87 A B G H D C FI E 4. C4. C为右子树的根结点为右子树的根结点(ji

51、(ji din)din) A B G H D C F I E 5. F5. F为右子树的右子为右子树的右子树的根结点树的根结点(ji (ji din)din)C E FIE C IF第86页/共188页第八十七页，共188页。a b c d e f gc b d a e g f例如例如(lr):(lr):aab bccddeeffggabcdefg先序序列(xli)中序序列(xli)第87页/共188页第八十八页，共188页。ACBEDFGABCDEFGABCFDEG第88页/共188页第八十九页，共188页。第89页/共188页第九十页，共188页。遍历二叉树的结果是， 求得结点(ji di

52、n)的一个线性序列。ABCDEFGHK例如(lr):先序序列先序序列(xli):(xli): 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一、一、线索二叉树的定义线索二叉树的定义第90页/共188页第九十一页，共188页。在这样的线性序列中，很容易求得某个结点在某种遍历在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历就能下的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，

53、快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用存贮单元，存贮空间的利用(lyng)(lyng)率相当低率相当低( (一个结点中一个结点中有有4 4个指针，个指针，1 1个指左孩子，个指左孩子，1 1个指右孩子，个指右孩子，1 1个指前驱，个指前驱，1 1个个

54、指后继指后继) )，而原来的左、右孩子域有许多空指针又没有利用，而原来的左、右孩子域有许多空指针又没有利用(lyng)(lyng)起来。为了不浪费存贮空间，我们利用起来。为了不浪费存贮空间，我们利用(lyng)(lyng)原原有的孩子指针为空时来存放直接前驱和后继，这样的指针称有的孩子指针为空时来存放直接前驱和后继，这样的指针称为为“线索线索”，加线索的过程称为线索化，加了线索的二叉树，加线索的过程称为线索化，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。称为线索二叉树，对应的二叉链表称为线索二叉链表。一、线索一、线索(xin su)二叉树二叉树的定义的定义第91页/共18

55、8页第九十二页，共188页。指向(zh xin)该线性序列中的“前驱”和 “后继” 的指针，称作“线索”加了线索(xin su)的二叉树，称作 “线索(xin su)二叉树”包含 “线索(xin su)” 的二叉链表，称作 “线索(xin su)链表”A B C D E F G H K D C B E 第92页/共188页第九十三页，共188页。在线索(xin su)二叉树中，由于有了线索(xin su)，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此，在二叉链表结点中，还必须增加两个标志域

56、ltag、rtag。 ltag和rtag定义(dngy)如下： 0 lchild域指向结点的左孩子(hi zi) ltag= 1 lchild域指向结点在某种遍历下的直接前驱 0 rchild域指向结点的右孩子域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后继域指向结点在某种遍历下的直接后继 第93页/共188页第九十四页，共188页。这样，二叉链表中每个结点(ji din)还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点(ji din)结构可描述如下： lchild ltag data rtag rchild 第94页/共188

57、页第九十五页，共188页。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右左右(zuyu)指针指针 PointerThr LTag, RTag; / 左右左右(zuyu)标志标志 BiThrNode, *BiThrTree;二、线索(xin su)的描述：1、类型定义：、类型定义： typedef enum Link, Thread PointerThr; / Link=0:指针指针(zhzhn)，Thread=1:线索线索第95页/共188页第九十六页，共188页。2线索线索(xin

58、 su)的画的画法法在二叉树或二叉链表中，若左孩子(hi zi)为空，则画出它的直接前驱，右孩子(hi zi)为空时，则画出它的直接后继，左右孩子(hi zi)不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。第96页/共188页第九十七页，共188页。 A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二叉树 (b)先序线索二叉树 (c)先序线索二叉链表 图 先序线索示意图 先序序列(xli)为：ABCD第97页/共188页第九十八页，共188页。 A D C B NULL NULL （a）中序二叉树 （b） 中序线索

59、二叉链表 图 中序线索示意图 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列(xli)为：BADC第98页/共188页第九十九页，共188页。 C 0 A 0 1 B 1 0 C 1 1 D 1 root D B A NULL (a)后序线索二叉树 (b)后序线索二叉链表 图 后序线索示意图 后序(hu x)序列为：BDCA第99页/共188页第一百页，共188页。ABCDE第100页/共188页第一百零一页，共188页。ABCDE A B D C ET先序序列：ABCDE先序线索二叉链表0000111111第101页/共188页第一百零二页，共188页。ABCDE A B

60、 D C ET中序序列：BCAED中序线索二叉链表0000111111第102页/共188页第一百零三页，共188页。ABCDE A B D C ET后序序列：CBEDA后序线索二叉链表0000111111第103页/共188页第一百零四页，共188页。ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉链表 0 1头结点：ltag=0, lchild指向根结点rtag=1, rchild指向遍历序列中最后(zuhu)一个结点遍历序列中第一个结点的lchild域和最后(zuhu)一个结点的rchild域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉链表0000111111第104页/共188页第一百零五页，共188页。 建立线索二叉树，或