第六章树与二叉树

《第六章树与二叉树》由会员分享，可在线阅读，更多相关《第六章树与二叉树（170页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章树和二叉树树和二叉树6.1树的类型定义树的类型定义6.2 6.2 二叉树的类型定义二叉树的类型定义6.2.3 二叉树的存储结构二叉树的存储结构6.3二叉树的遍历二叉树的遍历6.3.2线索二叉树线索二叉树6.4树和森林的表示方法树和森林的表示方法6.4.3树和森林的遍历树和森林的遍历6.6哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码6.1树的类型定义树的类型定义树的树的定义：定义：树是树是n（n=0)个结点的有限集。个结点的有限集。在任意一棵非空树中：在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；）有且仅有一个特定的称为根的结点；（2）当）当n1时，其余结点可分为时，其余结点

2、可分为m（m0）个互不相交的有限集个互不相交的有限集T1，T2，Tm,其中每一个集合本身又是一棵树其中每一个集合本身又是一棵树,并并称为根的子树。称为根的子树。DABCEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如: :树的图示表示法树的图示表示法树的广义表表示法树的广义表表示法ABDCHIJMFEGKL树的树的嵌套集合表示法嵌套集合表示法DABCEFG H IJMKLDABCEFG H IJMKL树的树的凹入表示法凹入表示法ABEKLFCGDHMIJ数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若

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

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

5、(&T,&p,i,c)/插入插入c为为T中中P所所指结点的第指结点的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树基基 本本 术术 语语结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素数据元素+ +若干指向子树的分支若干指向子树的分支分支的个数（子树的个数）分支的个数（子树的个数）树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点 度大于零的结点度

6、大于零的结点（包含根和中间节点（包含根和中间节点）DHIJM组织结构树组织结构树教师教师学生学生其他人员其他人员99级级 2000级级 2001级级 2002级级山东理工大学山东理工大学计算机系计算机系电子系电子系自控系自控系叶子叶子根根子树子树赵老根赵老根赵跃进赵跃进赵小康赵小康赵改革赵改革赵开放赵开放赵解放赵解放赵抗美赵抗美赵卫兵赵卫兵赵永红赵永红家谱树家谱树(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次: :树的深度：树的深度： 由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，

7、根的孩子为第二层，如果某节点在第L层,则其子树的根在L+1层。树中叶子结点所在的最大层次有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。任何一棵非空树是一个二元组Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构（非线性结构）（非线性结构）第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个

8、数据元素(无后继无后继)多个叶子多个叶子结点结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )6.2 二叉树的类型定义二叉树的类型定义 二叉树或为空树空树，或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不互不交的交的二叉树二叉树组成。(树的度最大为2)ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为

9、空树为空树二叉树的主要基本操作二叉树的主要基本操作：查查找找类类插插入入类类删删除除类类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();LevelOrderTraverse(T,Visit();查找类查找类 InitBiTree(&

10、T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插插入入类类ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删删除除类类二叉树二叉树的重要特性的重要特性性质性质1：在二叉树的第 i 层上至多有2i-1 个结点。 (i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；当j=i-1时, 命题成立最多有2

11、i-2 个节点个节点二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。性质性质2： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。 （等比数列求和）性质性质3： 对任何一棵二叉树，若它含有n0 个叶子结点（0度节点）、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。证明：证明：设设 二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2

12、 - 1由此，由此，n0 = n2 + 1 。两类两类特殊特殊的二叉树：的二叉树：满二叉树：满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉个结点的二叉树。树。完全二叉树完全二叉树：树中所含树中所含的的n 个结点和满二叉树个结点和满二叉树中中编号为编号为1 至至n 的结点的结点一一对应。（编号的规一一对应。（编号的规则为，由上到下，从左则为，由上到下，从左到右。）到右。）123456789 10 11 12 13 14 15abcdefghij1231145891213671014151231145891267101234567123456性质性质4： 具有具有n 个结点的

13、完全二叉树的个结点的完全二叉树的深度深度为为 log2n +1 。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，则该结点无左孩子，否则，编号为否则，编号为2i 的结点为其的结点为其左孩子左孩子结点；结点；(3)若若2i+1n，则该结点无右孩子结点，则该结点无右孩子结点，否则，编号为否则，编号为2i+1 的结点为其的结点为其右孩子右孩子结点。结点。6.2.3二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序存储表示存储表示#define MAX_TRE

14、E_SIZE 100 / 二叉树的最大结点数typedefTElemType SqBiTreeMAX_ TREE_SIZE; / 1号单元存储根结点SqBiTree bt;一、一、二叉树的顺序存储表示二叉树的顺序存储表示例如例如:ABCDEF A B D 0 C 0 E 0 0 0 0 0 0 F 1 2 3 4 5 6 7 8 9 10 11 12 13 142511437一般树按完全二叉的方式存储一般树按完全二叉的方式存储非常浪费空间！非常浪费空间！深度为深度为K的的单支树，需要单支树，需要2k-1个空间个空间（k=20,1M的空间）的空间）二、二叉树的链式存储表示二、二叉树的链式存储表示

15、1. 1. 二叉链表二叉链表2三叉链表三叉链表ADEBCF root1. 1. 二叉链表二叉链表ABCDEFlchild data rchild结点结构结点结构:typedefstruct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :ADEBCF root 2三叉链表三叉链表parentlchilddatarchild结点结构结点结构: typedefs

16、truct TriTNode / 结点结构结点结构 structTriTNode*parent; /双亲指针 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 TriTNode, *TriTree;parentlchilddatarchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :6.3二叉树的遍历二叉树的遍历 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出（一、问题的提出（寻找某个节点寻找某个节点）“访问访问”的含义可以很广

17、，如：输出结点的信息或判定节点满足某些条件等。 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。对对“二二叉叉树树”而而言言，可可以以有有三条搜索路径：三条搜索路径：1先上后下先上后下的按层次遍历；2先先左左（子树）后后右右（子树）的遍历；3先先右右（子树）后后左左（子树）的遍历。二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法 若二叉树为空

18、树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：ADBCDLRADLRDLRBDCDLR先序遍历序列：先序遍历序列：ABDC先序遍历: 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：ADBCLDRBLDRLDRADCLDR中序遍历序列：中序遍历序列：BDAC中序遍历: 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：ADBCLRDLRDL

19、RDADCLRD后序遍历序列：后序遍历序列：DBCA后序遍历:B三、算法的递归描述三、算法的递归描述voidPreOrderTraverse(BiTreeT,void(*visit)(TElemType&e) /T为树根的指针为树根的指针if(T)visit(T-data);/访问结点访问结点PreOrderTraverse(T-lchild,visit);/遍历左子遍历左子树树PreOrderTraverse(T-rchild,visit);/遍历右子树遍历右子树 ADB T A B DvoidInOrderTraverse(BiTreeT,void(*visit)(TElemType&e)

20、 /中序遍历二叉树，中序遍历二叉树，T为树根的指针为树根的指针if(T)InOrderTraverse(T-lchild,visit);/遍历左子遍历左子树树visit(T-data);/访问结点访问结点InOrderTraverse(T-rchild,visit);/遍历右子树遍历右子树 ADB T B A DvoidPostOrderTraverse(BiTreeT,void(*visit)(TElemType&e) /后序遍历二叉树，后序遍历二叉树，T为树根的指针为树根的指针if(T)PostOrderTraverse(T-lchild,visit);/遍历左子树遍历左子树PostOrd

21、erTraverse(T-rchild,visit);/遍历右子树遍历右子树visit(T-data);/访问结点访问结点 ADB T B DA 可以这样理解：无论先序、中序、可以这样理解：无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针沿二叉树外缘移的：从根节点出发，逆时针沿二叉树外缘移动对每个节点均途径三次。动对每个节点均途径三次。 先序遍历：第一次经过节点时访问。先序遍历：第一次经过节点时访问。 中序遍历：第二次经过节点时访问。中序遍历：第二次经过节点时访问。 后序遍历：第三次经过节点时访问。后序遍历：第三次经过节点时访

22、问。AB123先序：A B中序：A B后序： B A123 a a + + * * / /d d / - -rootroote e b b c c - -+ +* *a ab bc c/ /d de e a a+ + * * b b - -c c d d / / e e + + / / e e d d* *- - a a b b c cLDR:a*b-c+d/eLDR:a*b-c+d/e LRD:LRD:abcabc-*de/+-*de/+DLR:+*a-DLR:+*a-bcbc/de/de中序中序遍历二叉树的非递归算法遍历二叉树的非递归算法1StatusInOrderTraverse(BiT

23、reeT,Status(*Visit)(TElemTypee)InitStack(S);Push(S,T);/根指针进栈根指针进栈While(!StadkEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/向左走到尽头向左走到尽头Pop(S,p);/空指针出栈空指针出栈if(!StackEmpty(S)/访问结点访问结点,向右一步向右一步Pop(S,p);if(!visit(p-data)returnERROR;Push(S,p-rchild);/endif/endwhilereturnOK;/InOrderTraverse中序中序遍历二叉树的非递归算法

24、遍历二叉树的非递归算法2StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)InitStack(S);p=T;While(p|!StadkEmpty(S)if(p)Push(S,p);p=p-lchild;)/根指针进栈，遍历左子树根指针进栈，遍历左子树else/根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树Pop(S,p);if(!visit(p-data)returnERROR;p=p-rchild);/endif/endwhilereturnOK;/InOrderTraverse四、建立二叉树的存四、建立二

25、叉树的存储结构储结构不同的定义方法相应有不同的不同的定义方法相应有不同的存储结构的建立算法存储结构的建立算法以字符串的形式以字符串的形式根根左子树左子树右子树右子树定义一棵二叉树定义一棵二叉树例如:ABCD以空白字符“ ”表示AB C D空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以字符串表示Status CreateBiTree(BiTree *T) /按前序次序输入节点信息按前序次序输入节点信息scanf(&ch); if (ch= ) T = NULL; else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVE

26、RFLOW); T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; / CreateBiTree ,无头节点AB C D A BCD上页算法执行过程举例如下：ATBCD对于一个一般的二叉树，仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树。 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根

27、根abcdefgcbdaegf例如例如: :aabbccddeeffggabcdefg先序序列中序序列6.3.2线索二叉树线索二叉树 何谓线索二叉树？何谓线索二叉树？ 线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？一、一、何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是， 求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列: 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指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”与其相应的二叉树，称作 “线索

28、二叉树线索二叉树”包含 “线索” 的存储结构，称作 “线索链线索链表表”ABCDEDCBEA如何保存这种在遍历过程中得到的信息？如何保存这种在遍历过程中得到的信息？最简单的方法是在每个结点上最简单的方法是在每个结点上增加二个指增加二个指针域针域：fwd和和bkwd用来指示此结点在遍历用来指示此结点在遍历中的前驱和后继结点。中的前驱和后继结点。在在n个结点的二叉树中，个结点的二叉树中，有有n+1个空链域。个空链域。（空链域的个数空链域的个数=结结点数点数*2分支个数）分支个数）n结结点二叉树的空链域点二叉树的空链域=2*n-(n-1)=n+1我们可以利用这我们可以利用这n+1个空链域来存储线索个

29、空链域来存储线索使结点的存储密使结点的存储密度大大降低度大大降低对对线索链表线索链表中结点的约定：中结点的约定： 在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则Lchild域的指针指向其左子树， 且左标志域的值为“Link（指针）”； 否则，Lchild域的指针指向其“前驱”， 且左标志的值为“Thread（线索） ” 。若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树， 且右标志域的值为 “Link（指针）”；否则，rchild域的指针指向其“后继”， 且右标志的值为“Thread（线索） ”。 如此

30、定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。线索链表的结点定义： Lchild Ltag Data Rtag Rchild 0 lchild 域指示结点的左孩子 1 rchild 域指示结点的前驱Ltag= 0 lchild 域指示结点的右孩子 1 rchild 域指示结点的后继Rtag=以以这种结点结构构成的二叉链表作为这种结点结构构成的二叉链表作为二叉树的存储结构，叫做二叉树的存储结构，叫做线索链表线索链表。其中指向结点前驱和后继的指针，叫其中指向结点前驱和后继的指针，叫做做线索线索。加上线索的二叉树称之为加上线索的二叉树称之为线索二叉树线索二叉树。对二叉

31、树以某种对二叉树以某种次序遍历使其变为线次序遍历使其变为线索二叉树的过程叫做索二叉树的过程叫做线索化线索化。typedefstructBiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;线索链表的类型描述： #defineLink0/指针指针#defineThread1/线索线索typedefenumPointerTagLink,Thread; 定义枚举类型：Enum 枚举变量名 枚举变量的值二、线索链表的遍历

32、算法二、线索链表的遍历算法:由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。ABCD中序遍历二叉线索树：中序遍历二叉线索树：BCAD0A01B0thrt011C11D1例如例如：（对于利用空指针域的结构）（对于利用空指针域的结构）/中序线索化链表的遍历算法中序线索化链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 ？ 在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点。若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。st

33、atus InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p=T-lchild;/p指向根结点指向根结点 while(p!=T)/空树或遍历结束时，空树或遍历结束时，p=Twhile(p-LTag=Link)p=p-lchild;/第第一个结点一个结点if(!visit(p-data)returnERROR;while(p-RTag=Thread&p-rchild!=T)/访问后继结点访问后继结点p=p-rchild;Visit(p-data);/whilep=p-rchild;/p进至其右子树根进至其右子树根/while

34、returnOK； / InOrderTraverse_Thr在中序遍历过程中修改结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结左、右指针域，以保存当前访问结点的点的“前驱前驱”和和“后继后继”信息。遍历过信息。遍历过程中，附设指针程中，附设指针pre,并始终保持指并始终保持指针针pre指向当前访问的、指针指向当前访问的、指针p所指所指结点的前驱。结点的前驱。三、如何建立线索链表？三、如何建立线索链表？Status InOrderThreading(BiThrTree Thrt, BiThrTree T) /构建中序线索链表if (!(Thrt = (BiThrTree)mal

35、loc( sizeof( BiThrNode) exit(OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加头结点return OK; / InOrderThreading if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre=Thrt;InThreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt -rchild=pre;void InThreading(BiThrTre

36、e p) if (p) /对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 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); / 右子树线索化 /if / InThreading6.4树和森林树和森林 的表示方法的表示方法6.4.1树的存储结构树的存储结构一、一、双亲表示法

37、双亲表示法(顺序存储顺序存储)二、二、孩子链表表示法孩子链表表示法三、三、树的二叉链表树的二叉链表( (孩子孩子- -兄弟）兄弟） 存储表示法存储表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5根的位置：r=0总结点数：n=7data parent一、双亲表示法一、双亲表示法: typedefstruct PTNode TElemType data; int parent; / 双亲位置域 PTNode; dataparent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述: :typedefstr

38、uct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;树结构树结构:ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 2data parent特点：特点：求父亲容易求父亲容易求求孩子难孩子难如何求孩如何求孩子？子？需要遍历整个数组，找需要遍历整个数组，找出父亲域等于其数组下出父亲域等于其数组下标的所有结点。标的所有结点。二、孩子表示法二、孩子表示法:1、多重链表：、多重链表：（1）以结点的度作为孩子链域）以结点的度作为孩子链域 data degree child1 child2 child

39、d（2）以树的度作为孩子链域）以树的度作为孩子链域 data child1 child2 childd缺点缺点:结点不同构结点不同构,给操作带来麻烦给操作带来麻烦缺点缺点:结点同构结点同构,但空链域较多但空链域较多ABCDEFG0 A1 B2 C3 D4 E5 F6 Gr=0n=7 data firstchild 1 2 34 56-1000224找找孩子容易孩子容易找父亲难找父亲难parent2、孩子链表：、孩子链表：typedefstructCTNode int child; structCTNode *next; *ChildPtr;孩子结点结构孩子结点结构: childnextC语言的

40、类型描述语言的类型描述: : typedefstruct TElemType data; ChildPtr firstchild; / 孩子链的头指针 CTBox;表头结点结构表头结点结构 datafirstchildint parent; dataparentfirstchildtypedefstruct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;树结构树结构:ABCDEFGABCEDFGrootABCEDFG 三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）存储表示兄弟）存储表示法法typedefstruct CSNod

41、e TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C语言的类型描述语言的类型描述: :结点结构结点结构: firstchilddatanextsibling6.4.2树和二叉树的转换树和二叉树的转换将树转换成二叉树将树转换成二叉树加线：加线：在兄弟之间加一连线在兄弟之间加一连线抹线：抹线：对每个结点，除了其左孩子对每个结点，除了其左孩子外，去除与其余孩子之间的关系外，去除与其余孩子之间的关系旋转：旋转：以树的根结点为轴心，将整以树的根结点为轴心，将整树顺时针转树顺时针转45ABCDEFGHIAB

42、CDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空将将二叉二叉树转换成树树转换成树加线：加线：若若p结点是双亲结点的左孩子，结点是双亲结点的左孩子，则将则将p的右孩子，右孩子的右孩子，的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，沿分支找到的所有右孩子，都与都与p的双亲用线连起来的双亲用线连起来抹线：抹线：抹掉原二叉树中双亲与右孩抹掉原二叉树中双亲与右孩子之间的连线子之间的连线调整：调整：将结点按层次排列，形成树将结点按层次排列，形成树结构结构ABCDEFGHIABCDEFGHIABCDEFGHI要求要求 掌握将一棵树转化为二叉树方法掌握将一棵树转化为二叉树方法将转化二叉树还

43、原为一棵树方法将转化二叉树还原为一棵树方法ABCDEFGHIJKLABCDEFKLGHIJABCDEFGHIJKL森林和二叉树的对应关系森林和二叉树的对应关系设设森林森林F=(T1,T2,Tn);T1=(root，t11,t12,t1m);二叉树二叉树B=(LBT,Node(root),RBT);。T1T2T3T4TnT1T11T12T1m。T1T11T12T1m。T2T3Tn。森林转换成二叉树森林转换成二叉树1.将各棵树分别转换成二叉树将各棵树分别转换成二叉树2.将每棵树的根结点用线相连将每棵树的根结点用线相连3.以第一棵树根结点为二叉树以第一棵树根结点为二叉树的根，再以根结点为轴心，的根，

44、再以根结点为轴心，顺时针旋转，构成二叉树型顺时针旋转，构成二叉树型结构结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林二叉树转换成森林1.抹线：将二叉树中根结点与抹线：将二叉树中根结点与其右孩子连线，及沿右分支其右孩子连线，及沿右分支搜索到的所有右孩子间连线搜索到的所有右孩子间连线全部抹掉，使之变成孤立的全部抹掉，使之变成孤立的二叉树二叉树2.还原：将孤立的二叉树还原还原：将孤立的二叉树还原成树成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJ由森林转换成二叉树由森林转换成二叉树的转换规则为:若 F=，则 B=；否则， 由 ROOT(T1) 对应得

45、到 Node(root)； 由 (t11,t12,t1m) 对应得到 LBT； 由 (T2,T3,Tn) 对应得到 RBT。由二叉树转换为森林由二叉树转换为森林的转换规则为：若 B=， 则 F=；否则，由 Node(root) 对应得到 ROOT(T1 )；由LBT 对应得到 (t11,t12,，t1m)；由RBT 对应得到 (T2,T3,Tn)。 由此，树的各种操作均可对应二叉树的操作来完成。 应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。左是孩子，右是兄弟。6.4.3树和森林的遍历树和森林的遍历一、树的遍历一、树的遍历二、森林的遍历二、森林

46、的遍历三、树的遍历的应用三、树的遍历的应用树的遍历可有三条搜索路径树的遍历可有三条搜索路径:按层次遍历按层次遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历:若树不空，则先访问根结点，然后若树不空，则先访问根结点，然后依次先根遍历各棵子树。依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵若树不空，则先依次后根遍历各棵子树，然后访问根结点。子树，然后访问根结点。若树不空，则自上而下自左至右若树不空，则自上而下自左至右访问树中每个结点。访问树中每个结点。 A B C DE F G H I J K先根遍历时顶点先根遍历时顶点的访问次序：的访问次序：ABEFCDGHIJK后根遍历时

47、顶点后根遍历时顶点的访问次序：的访问次序：EFBCIJKHGDA层次遍历时顶点层次遍历时顶点的访问次序：的访问次序：ABCDEFGHIJK B C DE F G H I J K1森林中第一棵树的根结点；2森林中第一棵树的子树森林；3森林中其它树构成的森林。森林由三部分构成：1.先序遍历先序遍历森林的遍历森林的遍历 若森林不空，则访问访问森林中第一棵树的根结点；先序遍历先序遍历森林中第一棵树的子树森林；先序遍历先序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行先根遍历先根遍历。中序遍历中序遍历 若森林不空，则中序遍历中序遍历森林中第一棵树的子

48、树森林；访问访问森林中第一棵树的根结点；中序遍历中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根遍历后根遍历。树的遍历和二叉树遍历树的遍历和二叉树遍历的对应关系的对应关系？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历小结小结树和森林的遍历树和森林的遍历l树的遍历树的遍历遍历遍历按一定规律走遍树的各个顶点，且使每按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性

49、排列走法，以得到树中所有结点的一个线性排列常用方法常用方法先根（序）遍历：先访问树的根结点，然后先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点然后访问根结点按层次遍历：先访问第一层上的结点，然后按层次遍历：先访问第一层上的结点，然后依次遍历第二层，依次遍历第二层，第第n层的结点层的结点ABCDEFGHIJKLMNO先序遍历：先序遍历：后序遍历：层次遍历：A B EFIG C DH J KLNOME I F GB C J KNOLMHD AAB C D E FG

50、H I J K L MN O讨论：若采用讨论：若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样方式，结果是否一样？abdec先序遍历：先序遍历：后序遍历：后序遍历：中序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1. 树的先序遍历二法相同；树的先序遍历二法相同； 2. 树的树的后序后序遍历相当于对应二叉树的遍历相当于对应二叉树的中序中序遍历；遍历；3. 树没有中序遍历，因为子树无左右之分。树没有中序遍历，因为子树无左右之分。结论：结论：讨论：讨论：若采用若采用“先转换，后遍历先转换，后遍历”方式，结果是否相同方式，结果是否相同？森林：森林：A AB

51、BC CD DE EF FGGHHJ JI I先序序列：先序序列：中序序列：中序序列：A B C D E F G H I JB C D A F E H J I GA AB BC CD DE EF FGGHHJ JI I先序序列：先序序列：中序序列：中序序列：A B C D E F G H I JB C D A F E H J I G结论：森林的先序和中序遍历在结论：森林的先序和中序遍历在两种方式下的结果相同。两种方式下的结果相同。结论：结论：当以二叉链表做树的存储结当以二叉链表做树的存储结构时，树的先根序列和后根构时，树的先根序列和后根序列可借用二叉树的先序遍序列可借用二叉树的先序遍历和后序遍

52、历的算法实现之；历和后序遍历的算法实现之；对于森林也一样。对于森林也一样。6.6赫夫曼树及其应用赫夫曼树及其应用最优树的定义最优树的定义如何构造最优树如何构造最优树赫夫曼编码赫夫曼编码 一、最优树的定义一、最优树的定义树的路径长度树的路径长度定义为： 树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。路径：从一个结点到另一个结点之间的若干路径：从一个结点到另一个结点之间的若干个分支；个分支；路径长度：路径上的分支数目称为路径长度；路径长度：路径上的分支数目称为路径长度；结点的权：根据应用的需要可以给树的结点赋结点的权：根据应用的需要可以给树

53、的结点赋某种意义的实数称权值；某种意义的实数称权值；树的带权路径长度树的带权路径长度=树中所有叶子结点的带权路树中所有叶子结点的带权路径之和；通常记作径之和；通常记作nWPL= wk Lkk=1赫夫曼树：假设有赫夫曼树：假设有n个权值个权值(w1,w2,wn)，构造有构造有n个叶子结点的严格二叉树，每个叶子结个叶子结点的严格二叉树，每个叶子结点有一个点有一个wi作为它的权值。则带权路径长度最作为它的权值。则带权路径长度最小的严格二叉树称为最优二叉树（赫夫曼树）。小的严格二叉树称为最优二叉树（赫夫曼树）。22 4 75499WPL(T)= 72+52+23+43+92 =60WPL(T)= 72

54、+91+53+24+44 =625724579WPL(T)=9 2+7 2+5 2+2 3+4 3=60如何构造赫夫曼树如何构造赫夫曼树？ 根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；二、构造最优树（赫夫曼树）二、构造最优树（赫夫曼树）(1)(赫夫曼算法) 在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；(2) 从F中删去这两棵树，同时加入 刚

55、生成的新树； 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止。(3)(4)演示演示9例如: 已知权值 W= 5, 6, 2, 9, 7 5627257697671392576713925716671329WPL=6*2+7*2+9*2+5*3+2*3=12+14+18+15+6=659257163 3、哈夫曼树构造程序、哈夫曼树构造程序 一棵有n个叶子结点的Huffman树有2n-1个结点采用顺序存储结构一维结构数组存储结点信息结点类型定义为：typedef struct int weight; int parent, lchild, rchild;HTNode, *Huffma

56、nTree; void Huffman(HuffmanTree &HT,int * w ,int n) int i, j, k,m,s1,s2; HuffmanTree p; if (n=1) return ; m =2*n-1;HT=(HuffmanTree) malloc(m+1)*sizeof(HTNode);/0号单元未用for(p=HT,i=1; i=n ; + i,+p,+w) *p=*w,0,0,0;for ( ; i=m ; + i ,+p) *p=0,0,0,0; /初始化HT数组for(i=n+1;i=m; + i) /建赫夫曼树 Select (HT,i-1,s1,s2)

57、;/在HT1.i-1选择parent为-1且weight最小的两个结点,其序号分别为s1,s2HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTs1.weight + HTs2.weight; / Huffman构造赫夫曼树81321312567例：2，5，1，7，626005700160078006800373189621395421078123456789Weight parent lchild rchild Huffman树应用树应用_最佳判定树最佳判定树等级等级分数段分数段比例比例ABCDE

58、059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADBCa80a70a60a90EYNDYNCYNBYNA在进行数据通讯时，涉及数据编码问题。所谓数据编在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。码就是数据与二进制字符串的转换。例如：邮局发电报：例如：邮局发电报：例例要传输的原文为要传输的原文为ABACCDA等长编码等长编码A：00B：01C：10D：11发送方：发送方：ABACCDA转换成转换成0001001010

59、1100接收方：接收方：00010010101100还原为还原为ABACCDA三、赫夫曼编码三、赫夫曼编码不等长编码不等长编码A：0B：00C：1D：01发送方：发送方：将将ABACCDA转换成转换成000011010接收方：接收方：000011010转换转换成成A A A A C C D AA A A A C C D AB B C C D AB B C C D AA的编码是B的前缀原文原文电文（二进制字符串）电文（二进制字符串）原文原文发送方发送方接收方接收方 指的是，任何一个字符的编码都不是同一字符任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀集中另一个字符的编码的前缀。如A

60、B C D 四个字符的使用率由高到低，编码为A - 0 B - 10 C - 110 D - 111因此，若设计长短不等的编码，则必须是任何一个因此，若设计长短不等的编码，则必须是任何一个字符的编码都不是另一个字符的编码的前缀，这种字符的编码都不是另一个字符的编码的前缀，这种编码称做编码称做前缀编码前缀编码。 如何编制前缀码呢？如何编制前缀码呢？例如：（例如：（A B C D A B C D ）字符使用频度作为权值：字符使用频度作为权值： （3 3，1 1，2 2，1 1）构造哈夫曼树。构造哈夫曼树。将该将该哈夫曼树所有左分支标树所有左分支标记记0，所有右分支标记，所有右分支标记1；利用赫夫曼

61、树可以构造一种不等长的二进制编码，利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的并且构造所得的赫夫曼编码赫夫曼编码是一种是一种最优前缀编码最优前缀编码，即，即使所传使所传电文的总长度最短电文的总长度最短。A：0B：110C：10D：111 3 3 7 7 2 21 1 1 1 2 2 4 4000111ABCDHuffman编码：数据通信用的二进制编码编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造编码：根据字符出现频率构造Huffman树，然后树，然后将树中结点引向其左孩子的分支标将树中结点

62、引向其左孩子的分支标“0”，引向，引向其右孩子的分支标其右孩子的分支标“1”；每个字符的编码即为；每个字符的编码即为从根到每个叶子的路径上得到的从根到每个叶子的路径上得到的0、1序列序列例例要传输的字要传输的字符集符集D=C,A,S,T,;字符出现频字符出现频率率w=2,4,2,3,3CS3364224814T;A00110110T:00;:01A:10C:110S:111译码：从译码：从Huffman树根开始，从待译码电文中逐树根开始，从待译码电文中逐位取码。若编码是位取码。若编码是“0”，则向左走；若编码是，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一，则向右走，一旦到达

63、叶子结点，则译出一个字符；再重新从根出发，直到电文结束个字符；再重新从根出发，直到电文结束例例电文是电文是CAS;CAT;SAT;AT其编码其编码“11010111011101000011111000011000”电文为电文为“1101000”译文只能是译文只能是“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111例：例：ABCDEFGH在一段电文中出现的概率如下：在一段电文中出现的概率如下：7，19，2，6，32，3，21，10将概率作为叶子结将概率作为叶子结点的权值，构造一棵哈夫曼树。点的权值，构造一棵哈夫曼树。100602811173267

64、10523ABCDEFGH7，19，2，6，32，3，21，101010001000010011110001011011WPL=6*4+2*5+3*5+7*4+10*4+32*2+19*2+21*2=26100000011114019210111电文电文:101111110001译文译文:HEEBG Typedef char* *HuffmanCode; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)/从叶子到根逆向求每个字符的赫夫曼编码 int i, c,f ,start ; char *cd; HC=(HuffmanCod

65、e) malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量 cd=(char*) malloc(n)*sizeof(char);/分配求编码的工作空间 cdn-1=“0” ;/编码的结束符for(i=1; i=n ; + i)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位 for ( c=i,f=HTi.parent;f!=0 ; c=f,f= HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=“0”; /c是f的左孩子 else cd-start=“1”; /c是f的右孩子HCi=(char*) mal

66、loc(n-start)*sizeof(char*);Strcpy(HCi,&cdstart); /从cd复制编码到HC free(cd) ; /HuffamCodingvoid HuffmanCoding2(HuffmanTree &HT,HuffmanCode &HC,int n)/从根出发遍历赫夫曼树,求赫夫曼编码 int p,m, cdlen ; char *cd; HC=(HuffmanCode) malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量 p=m; cdlen=0 ; for(i=1; inodesr)visit(T-nodesr.data)

67、;for(p=T.nodesr.firstchild;p;p=p-next)PreTree(T,p-child,visit);returnOK;StatusPtree(CTreeT)/前序遍例算法前序遍例算法PreTree(&T,T.r,visit);returnOK;练习题练习题6.29讲述讲述练习题练习题6.30先序序列中先序序列中U在在V之前，则之前，则U为为V的祖先或左兄弟的祖先或左兄弟后序序列中后序序列中U在在V之后，则之后，则U为为V的祖先或右兄弟的祖先或右兄弟所以所以U为为V的祖先的祖先intIs_Descendant(intu,intv)/在孩子存储结构上判断在孩子存储结构上判

68、断u是否是否v的子孙的子孙,是则返回是则返回1,否则返回否则返回0if(u=Rv|u=Lv)return1;elseif(Lv)if(Is_Descendant(u,Lv)return1;if(Rv)if(Is_Descendant(u,Rv)return1;/这是个递归算法这是个递归算法return0;/Is_Descendant6.33intIs_Descendant_P(intu,intv)/在双亲存储结构上判断在双亲存储结构上判断u是否是否v的子孙的子孙,是则返回是则返回1,否则返回否则返回0for(p=u;p!=v&p;p=Tp);if(p=v)return1;elsereturn0

69、;/Is_Descendant_P6.346.36intBitree_Sim(BitreeB1,BitreeB2)/判断两棵树是否相似的递归算法判断两棵树是否相似的递归算法if(!B1&!B2)return1;elseif(Bitree_Sim(B1-lchild,B2-lchild)&Bitree_Sim(B1-rchild,B2-rchild)return1;elsereturn0;/Bitree_Simintc,k;/这里把这里把k和计数器和计数器c作为全局变量处理作为全局变量处理c=0voidGet_PreSeq(BitreeT)/求先序序列中第求先序序列中第k个位置的结点的值个位置的

70、结点的值if(T)c+;/每访问一个子树的根都会使前序序号计数器加每访问一个子树的根都会使前序序号计数器加1if(c=k)printf(“Valueis%dn”,T-data);exit(1);elseGet_PreSeq(T-lchild);/在左子树中查找在左子树中查找Get_PreSeq(T-rchild);/在右子树中查找在右子树中查找/Get_PreSeq6.416.42intLeafCount_BiTree(BitreeT)/求二叉树中叶子结点的数目求二叉树中叶子结点的数目if(!T)return0;/空树没有叶子空树没有叶子elseif(!T-lchild&!T-rchild)r

71、eturn1;/叶子结点叶子结点elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加上右子树的叶子数左子树的叶子数加上右子树的叶子数/LeafCount_BiTree方法方法26.43voidBitree_Revolute(BitreeT)/交换所有结点的左右子树交换所有结点的左右子树T-lchildT-rchild;/交换左右子树交换左右子树if(T-lchild)Bitree_Revolute(T-lchild);if(T-rchild)Bitree_Revolute(T-rchild);/左右子树再分别交换各自的左右子

72、树左右子树再分别交换各自的左右子树/Bitree_Revolute6.44intGet_Sub_Depth(BitreeT,intx)/求二叉树中以值为求二叉树中以值为x的结点为根的子树深度的结点为根的子树深度if(T-data=x)printf(%dn,Get_Depth(T);/找到了值为找到了值为x的结点的结点,求其深度求其深度exit1;elseif(T-lchild)Get_Sub_Depth(T-lchild,x);if(T-rchild)Get_Sub_Depth(T-rchild,x);/在左右子树中继续寻找在左右子树中继续寻找/Get_Sub_DepthintGet_Dept

73、h(BitreeT)/求子树深度的递归算法求子树深度的递归算法if(!T)return0;elsem=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return(mn?m:n)+1;/Get_Depth6.47voidLayerOrder(BitreeT)/层序遍历二叉树层序遍历二叉树InitQueue(Q);/建立工作队列建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)DeQueue(Q,p);visit(p);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-r

74、child);/LayerOrderintIsFull_Bitree(BitreeT)/节点个数大于节点个数大于1/判断二叉树是否完全二叉树判断二叉树是否完全二叉树,是则返回是则返回1,否则返回否则返回0InitQueue(Q);flag=0;EnQueue(Q,T);/建立工作队列建立工作队列while(!QueueEmpty(Q)DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;elseEnQueue(Q,p-lchild);EnQueue(Q,p-rchild);/不管孩子是否为空不管孩子是否为空,都入队都入队列列/whilereturn1;/I

75、sFull_Bitree6.496.55intDescNum(BitreeT)/求树结点求树结点T的子孙总数填入的子孙总数填入DescNum域中域中,并返回该数并返回该数if(!T)return-1;elsed=(DescNum(T-lchild)+DescNum(T-rchild)+2);/计算公式计算公式T-DescNum=d;returnd;/DescNum6.60intLeafCount_CSTree(CSTreeT)/求孩子兄弟链表表示的树求孩子兄弟链表表示的树T的叶子数目的叶子数目if(!T-firstchild)return1;/叶子结点叶子结点elsecount=0;for(c

76、hild=T-firstchild;child;child=child-nextsib)count+=LeafCount_CSTree(child);returncount;/各子树的叶子数之和各子树的叶子数之和/LeafCount_CSTree6.62intGetDepth_CSTree(CSTreeT)/求孩子兄弟链表表示的树求孩子兄弟链表表示的树T的深度的深度if(!T)return0;/空树空树elsefor(maxd=0,p=T-firstchild;p;p=p-nextsib)if(d=GetDepth_CSTree(p)maxd)maxd=d;/子树的最大深度子树的最大深度returnmaxd+1;/GetDepth_CSTree6.63/CTreeA;intGetDepth_CTree(CTreeA)/求孩子链表表示的树求孩子链表表示的树A的深度的深度returnSubDepth(A.r);/GetDepth_CTreeintSubDepth(intT)/求子树求子树T的深度的深度if(!A.nodesT.firstchild)return1;for(sd=1,p=A.nodesT.firstchild;p;p=p-next)if(d=SubDepth(p-child)sd)sd=d;returnsd+1;/SubDepth