04-1第4章 树1.pptx

第1页：本节内容目录封面

4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6应用第四章树

第2页：树结构在客观世界中大量存

树结构在客观世界中大量存在，如家谱、行政组织机构等都可用树形象地表示。

第3页：

第4页：[企业管理机构]

[企业管理机构]在层次中地位最高的人(此处为总裁)在图中位置最高。在层次中地位次之的(即副总裁)在图中位于总裁之下等等。副总裁为总裁的下属，总裁是他们的上级。每个副总裁都有自己的下属，而其下属又有自己的下属。企业管理结构

第5页：树在计算机领域也有广泛的应用

树在计算机领域也有广泛的应用，如:•在编译中，用树来表示源程序的语法结构；•在数据库系统中，可用树来组织信息；•在分析算法时，可用树来描述其执行过程；•操作系统中，文件及文件夹的存储，软件工程中，软件的菜单等都是树。

第6页：递归定义

递归定义定义4.1：一个树（或树形）就是一个有限非空的结点集合T，其中：1.有一个特别标出的被称为该树（或树形）之根root(T)的结点；2.其余结点（根除外）被分成m≥0个不相交的集合T1，T2，…，Tm，且T1，T2，…，Tm又都是树（或树形）。树（或树形）T1，T2，…，Tm被称作root(T)的子树（或子树形）。

一、树的定义

第7页：定义的定义

定义4.2 树是包

含n(n≥1)个结点且满足如下条件的有限集合：1.存在一个唯一的结点v0，它没有前驱结点，称为树的根（或根结点）；2.任何非根结点都有且仅有一个前驱结点，称为该结点的父结点；3.任何结点都可能有多个（≤n−1）后继结点，称之为该结点的子结点；若某结点没有后继结点，则称之为叶结点。4.任一非根结点vk都有且仅有一条从v0到该结点的结点序列（或曰路径）v0→v1→…→vk，其中vi是vi−1（1≤i≤k）的子结点。非递归定义

第8页：为一棵由根结点

图4.1.1为一棵由根结点A出发的树，其中，A有三个子结点B、C和D；B有一个子结点E；E有一个子结点F；C有两个子结点G和H；D有一个子结点I；F，G，H，I是叶结点，因为它们没有子结点。从A到F的路径为A-B-E-F。AECDBIHGF图4.1.1树

第9页：本节内容目录

EBF（A）G（B）CHG（C）图4.1.2子树若断掉一个结点与其父结点的连接，把该结点和它的子孙们单独拿出，就是一棵以该结点为根结点的树，我们称之为“子树”。图4.1.2中的（A）、（B）、（C）均是图4.1.1所示树的子树。

第10页：树的相关术语

树的相关术语1．度一个结点的子结点的数目，称为该结点的度或次数。一棵树的度为maxi=1,…,nD(i)，其中n为树中结点总数，i指树中的第i个结点，D(i)表结点i的度。2．叶结点、分支结点度为0的结点被称为叶结点；度>0的结点被称为分支结点。在图4.1.1中：B有一个子结点E，度为1；A有三个子结点B、C和D（换言之，A是B、C和D的父结点），度为3，故这棵树的度也为3.

第11页：结点的层数树形T中结点的层数递归定义如下

3．结点的层数树形T中结点的层数递归定义如下：⑴root(T)层数为零；⑵其余结点的层数为其前驱结点的层数加1.

第12页：层次

AECDBIHGF层次0树的层数层次3层次1层次

第13页：路径树形中结点间

4．路径树形中结点间的连线被称为边。若树形T中存在结点序列vm→vm+1→…→vm+k，1≤k≤T的最大层数，满足vi+1是vi（m≤i≤m+k−1）的子结点，则称此结点序列为vm到vm+k的路径，该路径所经历的边数k被称为路径长度。5.子孙结点、祖先结点一棵树中若存在结点vm到vn的路径，则称vn为vm的子孙结点，vm为vn的祖先结点。

第14页：不难看出

不难看出，一个结点到它的某个子孙结点有且仅有一条路径。树中结点之间的父子关系具有如下特征：（1）树中任一结点都可以有零个或多个直接后继(即子结点)，但至多只能有一个直接前驱(即父结点)。（2）树中只有根结点无前驱，它是始结点；叶结点无后继，它们是终结点。（3）树中某些结点之间具有父子关系或者祖先、子孙关系，祖先、子孙关系是对父子关系的扩展，一些结点之间，如兄弟结点（同一个父亲的诸子结点被称为兄弟结点）之间就没有这种关系。

第15页：树的高度

6．树的高度树的高度为maxi=1,…,nNL(i)，其中n为树中结点总数，i指树中第i个结点，NL(i)之值为结点i的层数。树的高度是指树中结点的最大层数。

第16页：与线性结构

与线性结构的比较线性结构树结构第一个数据元素根结点(无前驱) (无前驱)最后一个数据元素多个叶子结点(无后继) (无后继)其它数据元素树中其它结点(一个前驱、一个后继) (一个前驱、多个后继)

第17页：树的特点

树的特点：①有一个总根。②没有分枝相交。③树有层次。

第18页：树的基本操作

树的基本操作1、创建树：CREATE_TREE(T)2、判树空：TREEEMPTY(T)3、求根：ROOT(T)4、求树的高度：TREEDEPTH(T)5、求某结点的兄弟: BROTHERS(T)6、求结点的双亲：PARENT(T)7、求结点的孩子：CHILD(T,e,i)8、遍历树：TRAVERSAL(T)9、插入结点：INSERT()10、删除结点：DELETE()11、在树T中搜索数据域为item的结点：SEARCH(T,item,i)

第19页：本节内容目录

4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6应用第四章树

第20页：本节内容目录（续2）

4.2二叉树4.2.1二叉树的定义和主要性质4.2.2二叉树的顺序存储4.2.3二叉树的链接存储4.2.4二叉树的遍历4.2.5二叉树遍历的应用

第21页：4.2.1 二叉树的主要性质

4.2.1二叉树的主要性质和定义●二叉树的定义：二叉树是结点的有限集合，它或者是空集，或者由一个根及两个不相交的称为这个根的左、右子树的二叉树构成。●二叉树的特征（1）二叉树每个结点最多有2个子结点；（2）二叉树的子树有左右之分。

第22页：二叉树的五种不同形态

二叉树的五种不同形态

第23页：树与二叉树的主要区别

树与二叉树的主要区别：二叉树中结点的子树分成左子树和右子树，即使某结点只有一棵子树，也要指明该子树是左子树，还是右子树，就是说二叉树是有序的；

第24页：树与二叉树的主要区别（续）

A(a)(b)(c)(d)(e)ACBACBCBACBACB含有3个结点的不同二叉树

第25页：二叉树的性质引理

二叉树的性质引理4.1二叉树中层数为i的结点至多有2i个，i≥0。证明：用数学归纳法。当i=0时，仅有一个根结点，其层数为0，因此i=0时引理成立。假定当i=j(j≥0)时引理成立，即第j层至多有2j个结点。对于二叉树的任意结点，其子结点个数最大为2，故第j+1层至多有2*2j=2j+1个结点，因此当i=j+1时，引理成立。

由数学归纳法可知，对于所有的i≥0，均有“第i层上至多有2i个结点”。证毕。▐

第26页：引理4.2

引理4.2 高度

为k的二叉树中至多有2k+1-1(k≥0)个结点。证明：根据引理4.1第0层上至多有20个结点，第1层上至多有21个结点,……，第k层上至多有2k个结点,因此，高度为k的二叉树中至多有20＋21＋……+ 2k=2k+1-1个结点。证毕。▐

第27页：高度

高度为k(k≥1)的二叉树中至少有k+1个结点。含有k(k≥1)个结点的二叉树高度至多为k−1.有4个结点、高度为3的二叉树CABD

第28页：引理4.3

引理4.3设T是由n个结点构成的二叉树，其中叶子结点个数为n0，度为2的结点个数为n2，则有：n0＝n2＋1证明：设度为1的结点有n1个，总结点个数为n，总边数为e，则：n=n0+n1+n2(1)e=n-1(2)e=2n2+n1(3)因此，有n0+n1+n2-1=2n2+n1n0=n2+1证毕。▐

第29页：定义的定义（续2）

定义4.4 一棵非空高度

为k(k≥0)的满二叉树，是有2k+1−1个结点的二叉树。564372981013111214151

第30页：高度为k

高度为k（非空）二叉树至多有2k+1−1个结点。满二叉树的特点是：–①叶结点都在第k层上；–②每个分支结点都有两个子结点；–③叶结点的个数等于非叶结点个数加

第31页：定义4.5一棵包含n个结点高

定义4.5 一棵包

含n个结点高为k的二叉树T，当按层次顺序编号T的所有结点，对应于一棵高为k的满二叉树中编号由1至n的那些结点时，T被称为完全二叉树。56437298101

第32页：具有n个结点高为k的完全二叉树的特点

具有n个结点高为k的完全二叉树的特点是：⑴树中只有最下面两层结点的度可以小于2；⑵树中最下面一层的结点都集中在该层最左边的若干位置上（满二叉树意义上）；⑶树中叶结点只能在层数最大的两层上出现，即存在一个非负整数k使得树中每个叶结点在第k层或第k+1层；⑷对树中所有结点，按层次顺序，用自然数从1开始编号，仅仅编号最大的非叶结点可以没有右孩子，其余非叶结点都有两个孩子结点。

⑸树中所有结点对应于高度为k的满二叉树中编号由1至n的那些结点。

第33页：引理4.4

引理4.4若将一颗具有n个结点的完全二叉树按层次次序从1开始编号，则对编号为i(1≤i≤n)的结点有：①若i≠1，则编号为i的结点的父结点的编号为⌊i/2⌋。②若2i≤n，则编号为i的结点的左孩子的编号为2i，否则i无左孩子。③若2i+1≤n，则i结点的右孩子结点编号为2i+1，否则i无右孩子。

第34页：用归纳法证明

用归纳法证明若i=1，如果n≥2，则左孩子的编号显然为2.假定对所有满足j≤i的j，知j的左孩子编号为2j.那么对结点i+1，我们证明其左孩子编号为2(i+1).如果2(i+1)≤n，则由层次次序得知，i+1的左孩子之前的两个结点是i的左孩子和右孩子，因为i的左孩子编号为2i(归纳假设)，故i的右孩子编号为2i+1，从而i+1的左孩子编号为2i+2=2(i+1).证毕▐

第35页：引理4.5

引理4.5具有n个结点的完全二叉树的高度是⌊log2n⌋.证明：设二叉树高度为k，由定义知，完全二叉树的结点个数介于高度为k-1和高度为k的满二叉树的结点数之间，即有：2k-1< n≤2k+1-1从而有2k≤n<2k+1，即k≤log2n< k+1，因为k为整数，故有k=⌊log2n⌋.证毕▐

第36页：本节内容目录

4.2二叉树4.2.1二叉树的定义和主要性质4.2.2二叉树的顺序存储4.2.3二叉树的链接存储4.2.4二叉树的遍历4.2.5二叉树遍历的应用

第37页：要存储一棵二叉树

要存储一棵二叉树，必须存储其所有结点的数据信息、左孩子和右孩子地址，既可用顺序结构存储，也可用链接结构存储。二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中，同时反映出二叉树中结点间的逻辑关系。4.2.2二叉树的顺序存储

第38页：对于完全二叉树

对于完全二叉树，结点的层次顺序反映了其结构，可按层次顺序给出一棵完全二叉树之结点的编号，结点编号恰好反映了结点间的逻辑关系，事实上，这就是完全二叉树的顺序存储方法。只要对二叉树之结点按照层次顺序进行编号，就可利用一维数组A来存储一棵含有n个结点的完全二叉树，其中A[1]存储二叉树的根结点，A[i]存储二叉树中编号为i的结点，并且结点A[i]的左孩子（若存在）存放在A[2i]处，而A[i]的右孩子（若存在）存放在A[2i+1]处。

4.2.2二叉树的顺序存储

第39页：完全二叉树的顺序存储

完全二叉树的顺序存储A[1]A[2]A[3]A[4]A[5]A[6] A[7] A[8] A[9]A[10]31 23 12 66 94 17 5 70 62 491712523627049316694

第40页：这种顺序存储方式是完全二叉树最简单

这种顺序存储方式是完全二叉树最简单、最节省空间的存储方式。它实际上只存储了结点信息域之值，而未存储其左孩子和右孩子地址，通过计算可找到它的左孩子、右孩子和父结点，寻找子孙结点和祖先结点也非常方便。但这种方法应用到非完全二叉树时，却有很多缺点。如果采用上述的顺序存储方式，按照层次顺序，对非完全二叉树之结点进行编号，则这时的编号不能与结点一一对应。

为此，先加入若干虚结点将其转换成一棵“完全二叉树”，然后再对原来的结点和虚结点统一编号，最后完成顺序存储。但这增加了用于存储虚结点的空间。

第41页：一般二叉树也

一般二叉树也可仿照完全二叉树那样存储。但可能会浪费很多存储空间。4CBA25731a[1]a[2]a[3]a[4]a[5]ABCa[6]a[7]

第42页：本节内容目录

4.2二叉树4.2.1二叉树的定义和主要性质4.2.2二叉树的顺序存储4.2.3二叉树的链接存储4.2.4二叉树的遍历4.2.5二叉树遍历的应用

第43页：二叉树的链接存储二

1、二叉树的链接存储二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。二叉树的结点结构二叉树结点包含三个域：数据域data、指针域left和指针域right，其中左、右指针分别指向该结点的左、右孩子结点.leftrightdata

第44页：二叉树的链接存储结构

二叉树的链接存储结构ADCBEFG∧∧∧∧∧∧∧∧ACBEFDG

第45页：二叉树结点类的定义

二叉树结点类的定义Template<class T>Class BinTreeNode{friendclassBinTree;private:BinTreeNode <T> *left;BinTreeNode <T> *right;public:Tdata;2、链接存储的二叉树的实现

第46页：构造函数

BinTreeNode(const T&item, BinTreeNode <T>*lptr=NULL, BinTreeNode <T>*rptr=NULL):data(item),left(lptr),right(rptr){ }//构造函数BinTreeNode<T>*GetLeft(void)const{ return Left;}

第47页：二叉树类

二叉树类BinTree的定义template< class T >classBinTree{ private:BinTreeNode<T> *root;//指向根结点public:BinTree(BinTreeNode<T> *t= NULL):root(t){ }//构造函数~ BinTree( ){ Del (root)；

}//析构函数——删除整棵二叉树

第48页：二叉树类（续）

BinTreeNode<T> *Father(BinTreeNode <T>* t, BinTreeNode<T>*p);

第49页：二叉树类（续2）

●二叉树类BinTree的部分实现(1)搜索父结点算法Father(t,p.q)//在以t为根的二叉树中搜索p的父结点F1[判断t是否存在及p是否为根结点]IF(t=NULLORp=t)THEN(q←NULL.RETURN).F2[若t为所求]IF left(t)=p OR right(t)=pTHEN ( q←t . RETURN).F3[递归调用]Father( left(t), p . qL).IF qL≠NULL THEN q←qL .ELSE (Father(right(t), p . qR).q←qR) . ▌ABDCL1L

第50页：搜索二叉树中符合数据域条件

(2)搜索二叉树中符合数据域条件的结点算法Find(t,item.q)Find1. [判断t是否为空或为所求]IFt= THEN (q← . RETURN. ).IFData(t)=itemTHEN (q←t. RETURN. ).Find2. [递归]Find (Left(t),item.p).IFp≠ THEN (q←p. RETURN. ).Find (Right(t),item.q).RETURN.▐

第51页：删除结点

(3)删除结点t及其左右子树算法DST(t)DST1. [t= ?]IFt= THEN RETURN .DST2. [t=root?]IFt=rootTHEN (Del(t) .root← . RETURN. )DST3. [找t的父结点q]p←t. Father(root,p.q).DST4. [修改q的指针域]IFLeft(q)=pTHENLeft(q)← .IFRight(q)=pTHENRight(q)← .DST5. [删除p及其子树]Del(p).▐

第52页：算法Del

算法Del(p)Del1. [p= ?]IFp= THEN RETURN.Del2. [递归删除]Del(Left(p)).Del(Right(p)).AVAIL←p.▐ABECDL1L

第53页：本节内容目录

4.2二叉树4.2.1二叉树的定义和主要性质4.2.2二叉树的顺序存储4.2.3二叉树的链接存储4.2.4二叉树的遍历4.2.5二叉树遍历的应用

第54页：4.2.4 二叉树的遍历

4.2.4二叉树的遍历●二叉树的遍历：按照一定次序访问二叉树中所有结点，并且每个结点仅被访问一次的过程。●二叉树的某种（先根、中根、后根或层次）遍历次序是二叉树中结点的一个有序序列，称为二叉树的先根（中根、后根或层次）序列。

第55页：二叉树的递归遍历算法遍历方式先根遍历

1.二叉树的递归遍历算法遍历方式先根遍历：DLR中根遍历：LDR后根遍历：LRDLDR二叉树

第56页：先根遍历(前/先序遍历)若二叉树为空

• 1)先根遍历(前/先序遍历)若二叉树为空，则空操作
• 否则–访问根结点
• –先根遍历左子树
• –先根遍历右子树。遍历结果-+a*b-c d/e f

第57页：二叉树先根遍历算法

二叉树先根遍历算法(递归)算法PreOrder(t)PreOrder1[递归遍历]IF t≠NULL THEN( PRINT(data(t)).PreOrder(left(t)).PreOrder(right(t)).)▌ABDFCE

第58页：遍历

//遍历以t为根的子树,C++实现void BinTree<T>::PreOrder ( BinTreeNode <T> * t ){if ( t != NULL ) {cout << t→data;PreOrder ( t→left );PreOrder ( t→right );}}

第59页：二叉树为空

若二叉树为空，则空操作；否则–中根遍历左子树；–访问根结点；–中根遍历右子树。遍历结果a+b*c-d-e/f2）中根遍历(中序遍历)表达式语法树

第60页：二叉树中根遍历算法

二叉树中根遍历算法(递归)算法InOrder(t)InOrder1[递归遍历]IF t≠NULL THEN(InOrder(left(t)).PRINT(data(t)).InOrder(right(t)).)▌

第61页：后根遍历(后序遍历)若二叉树为空

• 3）后根遍历(后序遍历)若二叉树为空，则空操作
• 否则–后根遍历左子树
• –后根遍历右子树
• –访问根结点。遍历结果a b c d-* +e f/-

第62页：二叉树后根遍历算法

二叉树后根遍历算法(递归)算法PostOrder(t)PostOrder1[递归遍历]IF t≠NULL THEN(PostOrder(left(t)).PostOrder(right(t)).PRINT(data(t)).)▌

第63页：先根遍历序列

ABDFCE先根遍历序列：A B C D E F中根遍历序列：B D C A F E后根遍历序列：D C B F E A

第64页：二叉树的非递归遍历算法

2.二叉树的非递归遍历算法——非递归的中根遍历递归算法InOrder(t)InOrder1[递归遍历]IF t≠NULL THEN(InOrder(left(t)).PRINT(data(t)).InOrder(right(t)). )▌ABECD

第65页：算法NIO

非递归的中根遍历算法算法NIO(t)NIO1. [初始化]CREATE (S).p←t. NIO2. [入栈]WHILEp≠ DO(S←p.p←Left(p) . )NIO3. [栈为空?]IFS为空THEN RETURN.ELSEp←S.NIO4. [访问p，更新p]PRINT (Data(p) ).p←Right(p).NIO5. [返回]GOTO NIO2 .▐

第66页：非递归的先根遍历算法

非递归的先根遍历算法，与非递归的中根遍历算法类似，区别在于输出语句的位置不同。先根和中根遍历的非递归算法，一个结点仅进栈出栈一次，我们能够判断其输出语句的位置，分别为结点进栈前及出栈后。而后根遍历输出结点的位置应为处理完右子树之后，如果每个结点还是进栈、出栈一次，则无法确定何时输出结点，即其左右子树是否已处理完。

第67页：非递归的后根遍历算法

非递归的后根遍历算法设置一个工作栈：结点所处状态i = 0, 1或2：0：结点及左右子树均未被访问；1：遍历左子树；2：遍历右子树。树中任一结点q都需进栈三次，出栈三次。第一次出栈是为遍历结点q的左子树，第二次出栈是为遍历结点q的右子树，第三次出栈是为访问结点q .结点结点状态i

第68页：根结点

1)将(根结点,0)压入堆栈。2)弹栈，对出栈元素(p,i)中标号i进行判断，•若i=0，则将(p,1)压入堆栈；若结点p的左指针不为空，则将(Left(p), 0)压入堆栈，准备遍历其左子树.•若i=1，此时已遍历完结点p的左子树，则将(p,2)压入堆栈；若右指针不为空，则将(Right(p), 0)压入堆栈，准备遍历其右子树.•若i=2，此时已遍历完结点p的右子树，访问结点p.

第69页：算法NPostOrder

算法NPostOrder(t)NPO1[建立堆栈]CREATS(S).NPO2[堆栈初始化]S←(t,0).NPO3[利用栈实现递归]WHILE NOT(StackEmpty(S)) DO( (P, i)←S.IF i=0 THEN ( S←(P,1).IF left(P)≠null THEN S←(left(P),0) . )IF i=1 THEN ( S←(P,2).IF right (P)≠null THEN S←(right(P),0). )IF i=2 THEN PRINT(data(P)) .)▌非递归的后根遍历算法

第70页：先根序列

由先根序列和中根序列可以唯一地确定一棵二叉树。[例]先根序列AB C K D E H F中根序列B K CAH E D F

第71页：先根序列（续2）

先根序列AB C KD E H F中根序列B K CAH E D FABCKDEHFABEDCKFHABDCKEHF

第72页：后根序列

由后根序列和中根序列可以唯一地确定一棵二叉树。[例]后根序列C E F D B H GA中根序列C B E D FAG H

第73页：后根序列（续2）

后根序列C E F DBH GA中根序列CBE D FAG HACBEDFGHABCDEFGHABCGDEHF

第74页：二叉树的层次遍历按层数由小到大

3、二叉树的层次遍历按层数由小到大，同层由左向右的次序访问结点。遍历结果:A B E C F DABDFCE

第75页：通过观察发现

通过观察发现，第i层上，若结点x在结点y的左边，则x一定在y之前被访问。同理，第i+1层上，x的子结点一定在y的子结点前被访问。若访问第i层上的所有结点，必须知道该层上所有结点的地址，地址保存在其父结点的left和right指针中。用一个队列来实现。

第76页：二叉树层次遍历算法

二叉树层次遍历算法需要一个辅助队列具体方法如下：根结点入队.重复本步骤直至队为空:若队非空，取队头结点并访问；若其左指针不空，将其左孩子入队；若其右指针不空，将其右孩子入队.ABFEDC

第77页：算法LevelOrder

算法LevelOrder(t)LevelOrder1. [建空队]CREATE (Q).LevelOrder 2. [入队]p←t.IFp≠ THENQ←p.LevelOrder 3. [层次遍历]WHILEQ非空DO(p←Q.PRINT (Data(p) ) .IFLeft(p)≠ THENQ←Left(p) .IFRight(p)≠ THENQ←Right(p) . ) ▐

第78页：本节内容目录

4.2二叉树4.2.1二叉树的定义和主要性质4.2.2二叉树的顺序存储4.2.3二叉树的链接存储4.2.4二叉树的遍历4.2.5二叉树遍历的应用

第79页：二叉树的遍历算法

由二叉树的遍历算法，很容易想到用遍历方法去创建二叉树。例如，从先根遍历思想出发来构造二叉树。但先根序列不能唯一确定二叉树之结构，两棵不同的二叉树却可能有相同的先根序列。1.创建二叉树

第80页：用“#”表示空指针

用“#”表示空指针，对图4.15(a)所示二叉树的先根序列是ABDEC，加入‘#’表示空指针位置后变为ABD##E##C##.对图4.15(b)所示二叉树之先根序列ABDEC，加入‘#’表示空指针位置后变为ABD#E###C##.递归算法CreateBinTree（简记为CBT）以包含空指针信息的先根序列为输入序列，以根指针t为输出参数.当读入‘#’字符时，将其初始化为一个空指针；

否则生成一个新结点并初始化其父结点之左、右指针.

第81页：算法CBT

算法CBT (tostop.t)CBT1. [读数据]READ (ch) . CBT2. [ch=tostop? ]IFch=tostopTHEN (t← . RETURN. )ELSE (t←AVAIL .Data(t)←ch. )CBT3. [构造左子树]CBT (tostop.s).Left(t)←s.CBT4. [构造右子树]CBT (tostop.s).Right(t)←s.▐

第82页：复制二叉树可以按先根遍历

2 .复制二叉树可以按先根遍历、中根遍历或后根遍历的方式复制二叉树。以后根遍历为例进行复制。复制过程：先复制子结点，再复制父结点，将父结点与子结点连接起来。

第83页：树中结点

ABECD该树中结点的复制顺序为：CBEDA

第84页：算法CopyTree

算法CopyTree(t.p)CopyTree1. [递归出口]IFt= THEN (p← .RETURN).CopyTree2. [复制左子树]IFLeft(t)≠ THEN CopyTree(Left(t) .newlptr)ELSEnewlptr← .CopyTree3. [复制右子树]IFRight(t)≠ THEN CopyTree(Right(t).newrptr)ELSEnewrptr← .CopyTree4. [生成结点]p←AVAIL.Data(p)←Data(t) .Left(p)←newlptr.Right(p)←newrptr.RETURN. ▐

第85页：课后作业

课后作业129页4-2、4-3、4-5