CHAP006树和二叉树lhj

1、12数据结构数据结构: 线性结构线性结构(线性表线性表, 栈栈,队列队列,串，数组串，数组) 非线性结构非线性结构: 至少存在一个数据元至少存在一个数据元素有不止一个直接前驱或后继素有不止一个直接前驱或后继(树树,图图等等)36.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 二叉树的遍历和线索二叉树二叉树的遍历和线索二叉树6.4 树和森林树和森林6.6 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码4树是一类重要的非线性数据结构，是以分支关系定义的层次结构。56.1 树的定义和树的定义和基本术语基本术语6树(tree)是n(n0)个结点的有限集T，其中：（1）有且仅有一

2、个特定的结点，称为树的根根(root)；（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子子树树(subtree)。6.1.1 定义定义7 树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。8ACGBDEFKLHMIJA只有根结点的树只有根结点的树有有子树子树的树的树子树子树树的实例树的实例9数据对象数据对象 D：D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合。 若若D为空集，则称为空树；为空集，则称为空树； 否则否则: (1) 在在D中存在唯一的称为根的数据元素中

3、存在唯一的称为根的数据元素root, (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, , Tm, 其中每一其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：6.1.2 抽象类型定义抽象类型定义10 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类11 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e

4、) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历12InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur

5、_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树13 ClearTree(&T) / 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树146.1.3 6.1.3 基本术语基本术语15结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据

6、元素数据元素+ +若干指向子树的分支若干指向子树的分支分支的个数分支的个数树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点DHIJM16(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点、兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次: :树的深度：树的深度： 由从根到该结点由从根到该结点所经分支和结点构成所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为假设根结点的层次为1,1,第第l 层层的结点的子树根结点的层次的结点的子树根结点的层次为为l+1树中叶子结点所在的最大层次树中叶子结点所在的最大层次17任何

7、一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree = （root，F）其中：其中：root 被称为根结点，被称为根结点， F 被称为子树森林被称为子树森林森林：森林：是是m（m0）棵互）棵互不相交的树的集合不相交的树的集合ArootBCDEFGHIJMKLF18ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的

8、度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先196.1.4 6.1.4 树的表示树的表示1.1.树型表示树型表示bacghdefij202.凹入表表示凹入表表示abdeijfcghabdeijfcghabdeijfcgh213.3.嵌套集合表示嵌套集合表示嵌套括号表示嵌套括号表示ijdfghabcea ( b ( d, e ( i, j )，f）, c ( g, h ) ) )226.1.5 对比对比树型结构树型结构和和线性线性结构结构的结构特点的结构特点23线性结构线性结构树型结构树

9、型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )246.2 二叉树二叉树256.2.1定义：定义：二叉树或为空树空树；或是由一个根结点根结点加上两棵两棵分别称为左子左子树树和右子树右子树的、互不相交的互不相交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树26特点特点：（1）每个结点至多有二

10、棵子树）每个结点至多有二棵子树(即不存在度大即不存在度大于于2的结点的结点)。思考：与度为。思考：与度为2的树一样吗？的树一样吗？（2）二叉树的子树有左、右之分，且其）二叉树的子树有左、右之分，且其次序不次序不能任意颠倒能任意颠倒。ABCDFGHKABCDFGHK276.2.2二叉树的五种基本形态二叉树的五种基本形态N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树286.2.3 二叉树二叉树的重要性质的重要性质29 性质性质 1 ： 在二叉树的第 i 层上至多至多有2i-1 个结点。 (i1)12311458912

11、1367101415第第1 1层层第第2 2层层第第3 3层层第第4 4层层1 12 24 48 830 性质性质 1 ： 在二叉树的第 i 层上至多至多有2i-1 个结点。 (i1)用归纳法证明：用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点， 2i-1 = 20 = 1；假设对所有的假设对所有的 j，1 j i，命题成立命题成立;即第即第j层上至多有层上至多有2j-1个结点，个结点，j=i-1时时命题成立；即命题成立；即i-1层有层有2i-2个结点；个结点；二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则第则第

12、i 层的结点数层的结点数 = 2i-2 2 = 2i-1 。31性质性质 2 ：深度为 k 的二叉树上至多至多含 2k-1 个结点。（k1）证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的二叉的二叉树上的结点数至多为：树上的结点数至多为： =20+21+ +2k-1 = 2k-1 122)(111kkikiii层的最大结点数第32 性质性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。证明：证明：设设 二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数 b = n1+2n2 而 b =

13、 n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1ABDECF33两类特殊的二叉树两类特殊的二叉树(1)满二叉树：满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树。个结点的二叉树。123456789 10 11 12 13 14 15特点：特点：每一层每一层上的结点数都上的结点数都是最大结点数。是最大结点数。34(2)完全二叉树完全二叉树：树中所含的树中所含的 n 个结点和个结点和满二叉树中满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。一一对应。特点：特点：(1)叶子结点只可能在层叶子结点只可能在层次最大的两层上出现。次最大的

14、两层上出现。(2)对任一结点，若其右对任一结点，若其右子树的最大层次为子树的最大层次为L，则，则其左子树的最大层次必为其左子树的最大层次必为L 或或L+1。123456789 10 11 1235性质性质 4 ： 具有具有 n 个结点的完全二叉个结点的完全二叉树的树的深度深度为为 log2n +1证明：证明：设设 完全二叉树的深度为 k 则根据性质2得： 2k-1-1 n 2k -1或2k-1 n 2k 即 k-1 log2 n 1 i1 双亲结点为双亲结点为 i/2i/2 2in 2in 无左孩子无左孩子2i=n 2in i+1n 无右孩子无右孩子2 2i+1=n i+1BDCD L R先序

15、遍历结果：先序遍历结果：A B D C先序遍历示例58写出先（根）序的遍历序列写出先（根）序的遍历序列遍历结果：遍历结果：a b d e h i j k c f g59 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。2. 中（根）序的遍历算法中（根）序的遍历算法60ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历示例61写出中（根）序的遍历序列写出中（根）序的遍历序列遍历结果：遍历结果： d b h e j

16、i k a f c g62 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。3. 后（根）序的遍历算法后（根）序的遍历算法63ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列： D B C A后序遍历示例B64写出后（根）序的遍历序列写出后（根）序的遍历序列遍历结果：遍历结果：d h j k i e b f g c a65三、遍历算法的实现三、遍历算法的实现1.1.递归算法的实现递归算法的实现66（1）先序遍历算法的递归描述）先序遍历

17、算法的递归描述void Preorder (BiTree T) / 先序遍历二叉树 if (T) Visit(T-data); Preorder(T-lchild); Preorder(T-rchild); / / Preorder主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBvisit(B);pre(T L);BTAvisit(A);pre(T L);ATDvisit(D);pre(T L);DTCvisit(C);pre(T L);C返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T

18、右是空返回右是空返回pre(T R);先序序列：先序序列：A B D C67（2）中序遍历算法的递归描述）中序遍历算法的递归描述void InOrder (BiTree T ) if ( T ) InOrder ( T-lchild ); / 遍历左子树 Visit( T-data); InOrder ( T-rchild ); / 遍历右子树 / InOrder68（3） 后序遍历算法的递归描述后序遍历算法的递归描述void PostOrder (BiTree T ) if ( T ) PostOrder(T-lchild ); / 遍历左子树 PostOrder(T-rchild ); /

19、 遍历右子树 Visit( T-data); / PostOrder69ADBC（4）层次遍历）层次遍历从上到下、从左到右访问各结点。从上到下、从左到右访问各结点。层次遍历序列：层次遍历序列： A B C D702. 非递归算法的实现非递归算法的实现 模仿递归算法中栈的状态变模仿递归算法中栈的状态变化即可写出非递归算法。化即可写出非递归算法。71ABCDEFGpLDR中序中序每进入一层递归，就把当前层的根结点指针压入栈顶每进入一层递归，就把当前层的根结点指针压入栈顶P-AP-BP-C访问：访问：C每退出一层递归，就从栈顶弹出当前层的根结点指针每退出一层递归，就从栈顶弹出当前层的根结点指针访问：

20、访问：B访问：访问：E访问：访问：G访问：访问：D访问：访问：F访问：访问：AP=NULLpP-DpP-EP=NULLpP-GpP=NULLpP=NULLP-FP=NULLP=NULL72Status InOrder_F( BiTree T)/非递归中序遍历二叉树 SqStack S; InitStack( S ); /初始化栈BiTNode *p=T; while (p | !StackEmpty(S) if(p) Push(S, p);p=p-lchild; / 根指针进栈，遍历左子树elsePop(S,p);/退栈Visit(p-data); /访问根p= p-rchild; /遍历右子

21、树 /if /while return OK;/ InOrder_F73void PreOrder_F( BiTree T ) / 非递归先序遍历二叉树 SqStack S; InitStack(S); /初始化栈 BiTNode * p = T; while (p | !StackEmpty(S) if(p)Visit(p-data);Push(S,p);p = p-lchild; /遍历左子树elsePop( S, p ); p= p-rchild ;/遍历右子树 /while/ PreOrder_FABDECF74typedef char TElemType;/ 非递归后序遍历二叉树ty

22、pedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;typedef struct BiTNode *ptr; /结点指针 int tag; /该结点退栈标记，tag=0，结点第1次入栈，暂不访问 / tag=1，结点第2次入栈，可以访问 SElemType;typedef struct SElemType *base; /栈底指针 SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的栈空间 SqStac

23、k;75void PostOrder_F( BiTree T ) SqStack S; InitStack(S); SElemType w; BiTNode *p = T; do if( p ) /向左子树走 w.ptr = p; w.tag = 0; Push (S, w); p = p-lchild; else if(!StackEmpty(S) Pop (S, w); p = w.ptr; /if switch ( w.tag ) /判断栈顶tag标记 case 0 : w.tag = 1;Push (S, w);p = p-rchild;break; case 1 : Visit( p

24、-data);p=NULL; /switch /if while ( p | !StackEmpty(S) ); / PostOrder_FABDECF76四、四、 遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4、建立二叉树的存储结构建立二叉树的存储结构771、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中

25、增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点” 的操作改为:若是叶子，则计数器增若是叶子，则计数器增1 1。78void CountLeaf (BiTree & T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 else CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafABDECF792、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想

26、算法基本思想 从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。80int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= De

27、pth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;/ DepthABDC813、复制二叉树、复制二叉树其基本操作为其基本操作为: :生成一个结点。生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树(后序遍历后序遍历)82ABCDEFGHK D C B H K G F E A例如例如: :下列二叉树下列二叉树的复制过程如下的复制过程如下: :newT83BiTNode *GetTree

28、Node(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(OVERFLOW) ; T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)84BiTNode *CopyTree(BiTNode *T) /复制二叉树 if (!T ) return NULL; if (T-lchild ) new

29、lptr = CopyTree(T-lchild);/复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTree854 4、建立二叉树的存储、建立二叉树的存储结构结构不同的定义方法相应有不同的不同的定义方法相应有不同的存储结构的建立算法存储结构的建立算法86（1）以字符串的形式）以字符串的形式 根根 左子树左子树 右子树

30、右子树定义一棵二叉树定义一棵二叉树例如例如: :ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示：以下列字符串表示：87Status CreateBiTree(BiTree &T) ch=getchar(); if (ch= ) T = NULL; else if (!(T=new BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild)

31、; / 构造右子树 return OK; / CreateBiTree88A B C D A BCD上页算法执行过程举例如下上页算法执行过程举例如下: :ATBCD89 仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，不能唯一确定一棵二叉树，（2）由二叉树的先序和中序序列建树）由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列如果同时已知二叉树的中序序列“cbdaegf”,则会如何？则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根90a b c d e f gc b d a e g f例如例如:

32、:aab bccddeeffggabcdefg先序序列中序序列91void CrtBT(BiTree& T, char pre, char ino, int ps, int is, int n ) / 已知preps.ps+n-1为二叉树的先序序列， / inois.is+n-1为二叉树的中序序列，本算 / 法由此两个序列构造二叉链表 if (n=0) T=NULL; else k=Search(ino, preps); /在中序序列中查询 if (k= -1) T=NULL; else / / CrtBT 92T=new BiTNode;T-data = preps;if (k=is

33、) 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 );93int Search(char ino, char x)char *pino=ino;int k=0;while(*pino!=0) & (x!=*pino)k+;pino+;if(x=*pino)return k;else ret

34、urn -1;94void main()BiTree T;char pre=abcdefg,ino=cbdaegf;int ps=0,is=0,n=7;CrtBT(T, pre, ino, ps, is, n );Preorder (T);coutendl;InOrder ( T ) ;coutlchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; /第一个结点 Visit(p); while (p-RTag=Thread & p-rchild!=T) p = p-rchild;

35、Visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根，有右子树 / InOrderTraverse_Thr109 在中序遍历过程中修改结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结左、右指针域，以保存当前访问结点的点的“前驱前驱”和和“后继后继”信息。遍历信息。遍历过程中，附设指针过程中，附设指针pre, 并始终保持指并始终保持指针针pre指向当前访问的、指针指向当前访问的、指针p所指所指结点的前驱。结点的前驱。三、如何建立线索链表？三、如何建立线索链表？110void InThreading(BiThrTree p, BiThrTr

36、ee &pre) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild,pre); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild,pre); / 右子树线索化 / if / InThreading111Status InOrderThreading(B

37、iThrTree &Thrt, BiThrTree T) / 构建中序线索链表 if (!(Thrt = new BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加头结点 return OK; / InOrderThreading 112if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T,pre); /中序线索化 pre-rchild = Thrt; / 处理最

38、后一个结点 pre-RTag = Thread; Thrt-rchild = pre; 113四、中序线索二叉树的应用四、中序线索二叉树的应用1.1.查找值为查找值为x x的结点的结点p p2.2.求给定结点的前驱求给定结点的前驱 3.3.求给定结点的后继求给定结点的后继4.4.插入结点插入结点1141.1.查找值为查找值为x x的结点的结点p pBiThrTree InOrderFind_Thr(BiThrTree Thrt,TElemType x)/查找值为x的结点p p = Thrt-lchild; / p指向根结点 while (p != Thrt ) / 空树或遍历结束时，p=Twh

39、ile (p-LTag=Link) p = p-lchild; /第一个结点 if(p-data=x) flag=1;break; 115 while (p-RTag=Thread & p- rchild!=Thrt) p = p-rchild; if(p-data=x) flag=1;break; / 沿后继结点查找/end whilep = p-rchild; /p进至其右子树根 end whileif(p-data=x) return p;else return NULL; / InOrderFind_Thr1162. 2. 求给定结点的前驱求给定结点的前驱 算法思想：算法思想：

40、 对于中序线索二叉树上的结点对于中序线索二叉树上的结点p，若其若其LTag=1，则，则lchild指向指向p的前驱；的前驱； 反之，反之，LTag=0，则，则p的前驱是以的前驱是以p结结点的左孩子为根结点的最右结点。点的左孩子为根结点的最右结点。117 求给定结点的前驱求给定结点的前驱 ABCDEFGHK118Status Prior_Thr(BiThrTree Thrt,TElemType x,BiThrTree &pre) / 在中序线索二叉树中寻找值为在中序线索二叉树中寻找值为x结点结点p的前驱结点的前驱结点pre p=InOrderFind_Thr(Thrt,x);/定位定位p

41、结点结点 if(!p) cout不存在值为不存在值为x的结点！的结点！lchild ; if(pre=Thrt) coutLTag =Link)while(pre-RTag =0) pre=pre-rchild ; return OK; / Prior_Thr 1193. 3. 求给定结点的后继求给定结点的后继 算法思想：算法思想： 对于中序线索二叉树上的结点对于中序线索二叉树上的结点p，若其若其RTag=1，则，则lchild指向指向p的后继；的后继； 反之，反之，RTag=0，则，则p的后继是以的后继是以p结结点的右孩子为根结点的最左结点。点的右孩子为根结点的最左结点。120求给定结点的后

42、继求给定结点的后继 ABCDEFGHK121Status Next_Thr(BiThrTree Thrt,TElemType x,BiThrTree &next) / 在中序线索二叉树中寻找值为在中序线索二叉树中寻找值为x结点结点p的后继结点的后继结点next p=InOrderFind_Thr(Thrt,x);/定位定位p结点结点 if(!p) cout“不存在值为不存在值为x的结点！的结点！ rchild ; if(next=Thrt) coutRTag =Link)while(next-LTag =0) next=next-lchild ; return OK; / Next_T

43、hr 1224.4.将值为将值为y y的新结点插入到二叉树中，的新结点插入到二叉树中，作为作为p p结点的右孩子结点的右孩子ABCDEpABCDEpYqYq两种情况两种情况q-rchild= p-rchild p-rchild=q q-lchild= p123将值为将值为y y的新结点插入到二叉树中，的新结点插入到二叉树中，作为作为p p结点的右孩子结点的右孩子ABCDEpYqFGHABCDEpYqFGH124将值为将值为y y的新结点插入到二叉树中，的新结点插入到二叉树中，作为作为p p结点的右孩子核心算法结点的右孩子核心算法q-rchild= p-rchild;q-Rtag=p-Rtag;

44、 p-rchild=q; p-Rtag-link; q-lchild= p;q-lTag=Thread;125Status InsertRChild_Thr(BiThrTree Thrt,TElemType x,TElemType y) p=InOrderFind_Thr(Thrt,x);/定位定位p结点结点if(!p) cout不存在值为不存在值为x的结点！的结点！data =y;q-rchild =p-rchild ;q-RTag =p-RTag ;q-lchild =p; q-LTag =Thread;p-rchild =q; p-RTag =Link;if(q-RTag =Link)N

45、ext_Thr(q, y,p);p-lchild =q; /区分两种情况return OK;126 6.4 树和森林树和森林 的表示方法的表示方法1276.4.1 树的三种存储结构树的三种存储结构一、一、双亲表示法双亲表示法二、二、孩子链表表示法孩子链表表示法三、三、树的二叉链表树的二叉链表( (孩子孩子- -兄弟）兄弟） 存储表示法存储表示法128ABCDEFG一、双亲表示法一、双亲表示法 以一组连续空间存以一组连续空间存储树的结点，同时在储树的结点，同时在结点中附设一个指针，结点中附设一个指针，存放双亲结点在链表存放双亲结点在链表中的位置。中的位置。特点：特点：找双亲容易，找双亲容易，找孩

46、子难找孩子难129ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent双亲表示法双亲表示法如何找孩子结点？如何找孩子结点？130 typedef struct PTNode TElemType data; int parent; / 双亲位置域 PTNode; data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述131typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTre

47、e;树结构树结构:132每个结点有多个指针域，分别指向其子树每个结点有多个指针域，分别指向其子树的根的根。（1 1）结点同构：结点的指针个数相等，结点同构：结点的指针个数相等，为树的度为树的度D D。浪费空间浪费空间（2 2）结点不同构：结点指针个数不等，结点不同构：结点指针个数不等，为该结点的度为该结点的度d d。操作不方便操作不方便二、孩子链表表示法二、孩子链表表示法data child1 child2 . childDdata degree child1 child2 . childd133ABCDEFG0 A 1 B 2 C 3 D 4 E 5 F 6 G r=0n=7 data fi

48、rstchild 1 2 34 56（3）孩子链表：）孩子链表：将每个结点的孩子链在该结点之将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表。后组成链表，再将所有头结点组成一个线性表。134typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: child nextC语言的类型描述语言的类型描述: :135 typedef struct TElemType data; ChildPtr firstchild; / 孩子链表头指针 CTBox;双亲结点结构双亲结点结构 data

49、 firstchild136typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;树结构树结构:137ABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 5r=0n=7 data firstchild 1 2 34 56（4）带双亲的孩子链表）带双亲的孩子链表138ABCDEFG AB C E D F Groot三、树的二叉链表三、树的二叉链表 (孩子孩子-兄弟）存储表示法兄弟）存储表示法双亲只管长子，双亲只管长子，长子连接兄弟长子连接兄弟139typedef struct C

50、SNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C语言的类型描述语言的类型描述: :结点结构结点结构: firstchild data nextsibling140 6.4.2 森林和二叉树的对应关系森林和二叉树的对应关系树与二叉树转换树与二叉树转换ACBED树树ABCDE二叉树二叉树 A B C D E A B C D E A B C D E 对应对应存储存储存储存储解释解释解释解释141一、将树转换成二叉树一、将树转换成二叉树加线：加线：在兄弟之间加一连线在兄弟之间加一连线抹线：抹线：对每个

51、结点，除了其左孩子对每个结点，除了其左孩子外，去除其与其余孩子之间的连线外，去除其与其余孩子之间的连线旋转：旋转：以树的根结点为轴心，将整以树的根结点为轴心，将整棵树顺时针转棵树顺时针转4545142ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空加线：在兄弟之间加一连线加线：在兄弟之间加一连线抹线：对每个结点抹线：对每个结点,除了其左孩子外除了其左孩子外,去除其与其余孩子之间连线去除其与其余孩子之间连线旋转：以树的根结点为轴心，将整棵树顺时针转旋转：以树的根结点为轴心，将整棵树顺时针转4

52、545143二、森林转换成二叉树二、森林转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连将每棵树的根结点用线相连以第一棵树根结点为二叉树以第一棵树根结点为二叉树的根，再以根结点为轴心，顺的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构时针旋转，构成二叉树型结构144ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林转换成二叉树森林转换成二叉树145三、将二叉树转换成树三、将二叉树转换成树加线：加线：若若p p结点是双亲结点的左孩子，结点是双亲结点的左孩子，则将则将p p的右孩子，右孩子的右孩的右孩子，右孩子的右孩子，子，

53、沿分支找到的所有右孩子，沿分支找到的所有右孩子，都与都与p p的双亲用线连起来的双亲用线连起来抹线：抹线：抹掉原二叉树中双亲与右孩子抹掉原二叉树中双亲与右孩子之间的连线之间的连线调整：调整：将结点按层次排列，形成树结构将结点按层次排列，形成树结构146ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI将二叉树转换成树将二叉树转换成树147四、二叉树转换成森林四、二叉树转换成森林抹线：抹线：将二叉树中根结点与其右将二叉树中根结点与其右孩子连线，及沿右分支搜索到的孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使所有右孩子间连线全部抹掉，使之变成孤立的

54、二叉树之变成孤立的二叉树还原：还原：将孤立的二叉树还原成树将孤立的二叉树还原成树148ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林二叉树转换成森林149 由此，树的各种操作均可对由此，树的各种操作均可对应二叉树的操作来完成。应二叉树的操作来完成。 应当注意的是，应当注意的是，和树对应的和树对应的二叉树，其左、右子树的概念二叉树，其左、右子树的概念已改变为：已改变为： 左是孩子，右是兄弟左是孩子，右是兄弟150树转换为树转换为二叉树二叉树ABCDEFGHIABCDEFGHI二叉树转二叉树转换为森林换为森林1516.4.3树和森林的遍历树和森林的

55、遍历152一、树的遍历一、树的遍历二、森林的遍历二、森林的遍历153一、树的遍历一、树的遍历 遍历遍历按一定规律走遍树按一定规律走遍树的各个顶点，且使每一顶点仅被的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规访问一次，即找一个完整而有规律的走法，以得到树中所有结点律的走法，以得到树中所有结点的一个线性排列。的一个线性排列。154树的遍历常用的方法树的遍历常用的方法:（3）按层次遍历按层次遍历（1）先根）先根(次序次序)遍历遍历（2）后根后根(次序次序)遍历遍历 若树不空，则先访问根结点，然后若树不空，则先访问根结点，然后依次先根遍历各棵子树。依次先根遍历各棵子树。 若树不空，则先依次

56、后根遍历各棵若树不空，则先依次后根遍历各棵子树，然后访问根结点。子树，然后访问根结点。 若树不空，则自上而下自左至右若树不空，则自上而下自左至右访问树中每个结点。访问树中每个结点。注意：树没有中序遍历，因为子树无左右之分。注意：树没有中序遍历，因为子树无左右之分。155 A B C DE F G H I J K 先根遍历时顶点先根遍历时顶点的访问次序：的访问次序：A B E F C D G H I J K 后根遍历时顶点后根遍历时顶点的访问次序：的访问次序：E F B C I J K H G D A 层次遍历时顶点层次遍历时顶点的访问次序：的访问次序：A B C D E F G H I J K

57、讨论：若采用讨论：若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样？方式，结果是否一样？abdec先序遍历：先序遍历：后序遍历：后序遍历：中序遍历：中序遍历：d e c b aabdeca b c d eb d c e aabdec先序遍历：先序遍历：后序遍历：后序遍历：a b c d eb d c e a结论：树的先序遍历与二叉树先序遍历相同；结论：树的先序遍历与二叉树先序遍历相同； 树的后序遍历相当于对应二叉树的中序遍历；树的后序遍历相当于对应二叉树的中序遍历；157 B C DE F G H I J K1.森林中第一棵树的根结点；2.森林中第一棵树的子树森林；3.森林中其它树构成

58、的森林。森林由三部分构成：二、森林的遍历二、森林的遍历1581. 先序遍历先序遍历 若森林不空，则访问访问森林中第一棵树的根结点;先序遍历先序遍历森林中第一棵树的子树森林;先序遍历先序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行先根遍历。先根遍历。159 2.中序遍历中序遍历 若森林不空，则中序遍历中序遍历森林中第一棵树的子树森林;访问访问森林中第一棵树的根结点;中序遍历中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根遍历。后根遍历。160先序遍历序列：先序遍历序列： A B C

59、 D E F G H I J中序遍历序列：中序遍历序列： B C D A F E H J I G161 树的遍历和二叉树遍历树的遍历和二叉树遍历的对应关系的对应关系先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历162 三、树的遍历的应用三、树的遍历的应用163typedef struct CSNode/孩子兄弟链表孩子兄弟链表 TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;1.求树的深度求树的深度2.输出树中所有从根到叶子

60、的路径输出树中所有从根到叶子的路径3.建树的存储结构建树的存储结构三、树的遍历的应用三、树的遍历的应用164 采用递归算法。求树的深度：即求以采用递归算法。求树的深度：即求以树树T的的firstchild 为根结点的树的深度为根结点的树的深度h1；求树求树T 的的nextsibling为根结点的树的深为根结点的树的深度度h2。1.求树的深度的算法求树的深度的算法树的深度？树的深度？ h1+1:h2165int TreeDepth(CSTree T) if(!T) return 0; else h1 = TreeDepth( T-firstchild ); h2 = TreeDepth( T-nextsibling); / TreeDepthreturn(h1+1h2)?h1+1:h2);求树的深度的算法求树的深度的算法1662.输出树中所有从