考研 期末 数据结构 第六章_树和二叉树

1、中国海洋大学信息学院中国海洋大学信息学院 魏振钢魏振钢Telelmail:Email:6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.5 6.5 树与等价问题树与等价问题（略）（略）6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.7 6.7 回溯法与树的遍历回溯法与树的遍历（略）（略）6.8 6.8 树的计数树的计数 基本内容：基本内容：6.1 6.1 树的定义和基本术语树的定义和基本术语 树（树（Tre

2、e）是）是n（n=0）个结点的有限集。在）个结点的有限集。在任意一棵非空树中任意一棵非空树中:1）有且仅有一个特定的称为根）有且仅有一个特定的称为根（Root）的结点；）的结点；2）当）当n1时，其余结点可分为时，其余结点可分为m（m0）个互不相交的有限集）个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子其中每一个集合本身又是一棵树，并且称为根的子树。树。其抽象数据类型定义如下：其抽象数据类型定义如下：数据对象数据对象 D：D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D D为空集，则称为空树为空集，则称为空树 。若。若D D仅含一

3、个数据元素，仅含一个数据元素， 则则R R为空为空集，否则集，否则R=HR=H，H H是如下二元关系是如下二元关系: (1) 在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；它在；它在H H下无前驱下无前驱 (2) 若若D D- root ，则存在，则存在D D- root的一个划分的一个划分D D1, D D2, , D Dm（m0)，对任意，对任意j k，有，有D Dj j D Dk k= = ,且对任意的且对任意的i i，唯一存在数，唯一存在数据元素据元素x xi iD Di i, ,有有root,x H H; (3) 对应于对应于D- rootD- root

4、的划分，的划分，H- H- ， 有惟有惟一的一个划分一的一个划分H H1,H Hm(m0)，对任意，对任意j k，有有H Hj j H Hk k= = ,且对任且对任意的意的i i，H Hi i是是D Di i上的关系，（上的关系，（D Di i, ,HHi i)是一棵符合本定义的树，是一棵符合本定义的树，称称为根为根root的子树。的子树。 数据关系数据关系 R：ADTADT Tree Root(T) / Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T

5、, cur_e) / Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(TLeftChild(T, cur_e) / , cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(TRightSibling(T, cur_e) / , cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(TTreeEmpty(T) / ) / 判定树是否为空树判定树是否为空树 TreeDepth(TTreeDepth(T) / ) / 求树的深度求树的深度TraverseTreeTraverseTree( T, V

6、isit() ) / ( T, Visit() ) / 遍历遍历基本操作：基本操作：InitTree(&TInitTree(&T) / ) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&TCreateTree(&T, definition) / , definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&TInsertChild(&T, &p, i, c) , &

7、amp;p, i, c) / / 将以将以c c为根的树插入为结点为根的树插入为结点p p的第的第i i棵子树棵子树 ClearTree(&TClearTree(&T) / ) / 将树清空将树清空 删除类：删除类：DestroyTree(&TDestroyTree(&T) / ) / 销毁树的结构销毁树的结构DeleteChild(&TDeleteChild(&T, &p, i) , &p, i) / / 删除结点删除结点p p的第的第i i棵子树棵子树ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(

8、H, I, J(M) )T1T3T2树根例如例如: :() 有确定的根；() 树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )对比对比树型结

9、构树型结构和和线性结构线性结构的结构特点的结构特点结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素及若干指向其子树的分支结点拥有的子树的数目树中所有结点的度的最大值度为零的结点度不为零的结点DHIJM基本术语基本术语(从根到结点的)路径：路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次: :树的深度树的深度(高度高度)： 由从根根到该结点所经分支和结点构成假设根结点的层次为1，根的孩子为第二层。第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次ABCDEFGHIJMKL例

10、如：例如：任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.2 6.2 二叉树二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构6.2.1 二叉树的定义 二叉树或为空树空树，或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCDEGFHK根结点左子树右子树数据对象数据对象 D：D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D= D= ，

11、则，则R= R= ，称称BinaryTreeBinaryTree为空二叉树为空二叉树 。否则，。否则，R=HR=H，H H是如下二元关系是如下二元关系: (1) 在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；它在；它在H H下无前驱下无前驱 (2) 若若D D- root ，则存在，则存在D D- root= D Dl, D Dr, 且且D Dl l D Dr r= = ; (3) 若若D Dl l ，则，则D Dl l中存在惟一的元素中存在惟一的元素x xl l, ,H H，且存在，且存在D Dl上的关系上的关系H HlH H；若若D Dr r ，则，则D Dr

12、 r中存在惟一的元素中存在惟一的元素x xr r,root,x, H H，且存在，且存在D Dr r上的关系上的关系H Hr rH H； H=H= root,x,H,Hl l,H,HR R ；（4 4）( (D Dl l, ,HHl l)是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的左子树， (D(Dr r, ,HHr r)是一棵符合本定义的二叉树，称为根的右子树，是一棵符合本定义的二叉树，称为根的右子树， 数据关系数据关系 R：ADTADT BinaryTree二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子

13、树为空树L左子树为空树左子树为空树左右子树均不左右子树均不为空树为空树 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(); 二叉树的

14、主要基本操作二叉树的主要基本操作： InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR); 具体内容见讲义具体内容见讲义 P121-P123P121-P123性质性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点 (i1)。用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证

15、明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；即第j层上至多有2j-1个结点。二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。归纳假设6.2.2 6.2.2 二叉树的性质二叉树的性质性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。性质性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。证明：证

16、明：设设 二叉树上结点总数为n，则则 n = n0 + n1 + n2， 其中其中n1为度为为度为1的结点数。的结点数。又又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghijabcdeijabcdeg非完全二叉树非完全二叉树性质性质

17、4 ： 具有 n 个结点的完全二叉树的深度深度为 log2n +1 。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 ： 2k-1-1 n 2k-1 或 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。i/2 ii+12i2i+12i+32i+2(a) (a) 结点结点i i和和i+1i+1在同一层上；在同一层上；LCHILD(i)RCHILD(i)LCHILD(i+1)RCHILD(i+1)(b) (b) 结点结点

18、i i和和i+1i+1不在同一层上；不在同一层上；图图6.5 6.5 完全二叉树中结点完全二叉树中结点i i和和i+1i+1的左、右孩子的左、右孩子i+12i+22i+3i2i2i+1#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的节点元素，即将完全二叉树上编号为i的结点元

19、素存储在如上定义的一维数组中下标为i-1的分量中。例如例如: : A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEF1401326ADEBCF rootlchild data rchild结点结构结点结构:1. 1. 二叉链表二叉链表二、二叉树的链式存储表示二、二叉树的链式存储表示typedef structtypedef struct BiTNode / 结点结构结点结构 TElemType data; structstruct BiTNode * *l lchild, * *r rchild; / 左右孩子指针 BiTNode, * *BiT

20、ree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :rootADEBCF 2三叉链表三叉链表parent lchild data rchild结点结构结点结构: typedef structtypedef struct TriTNode / 结点结构结点结构 TElemType data; structstruct TriTNode * *l lchild, * *r rchild; / 左右孩子指针 structstruct TriTNode *parent; /双亲指针 TriTNode, * *TriTree;parent lchi

21、ld data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :0123456B2C0A -1D2E3F43 3双亲链表双亲链表 data parent结点结构结点结构:LRTagL LR RR RR RL L typedef struct BPTNode / 结点结构结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结

22、点数目 int root; / 根结点的位置 BPTree一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例6.36.3遍历二叉树和线索二叉树遍历二叉树和线索二叉树 何谓二叉树的遍历？ 一、问题的提出一、问题的提出 “访问访问”的含义可以很广，如：输出结点的信息等。 “遍历遍历”是任何类型均有的操作，对线性结构是任何类型均有的操作，对线性结构而言，只有一条搜索路径而言，只有一条搜索路径( (因为每个结点均只有一因为每个结点均只有一个后继个后

23、继) )，故不需要另加讨论。而二叉树是非线性，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按结构，每个结点有两个后继，则存在如何遍历即按什么样的什么样的搜索路径搜索路径遍历的问题。遍历的问题。 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一次均被访问一次，而且仅被访问一次仅被访问一次。 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：1先上后下先上后下的按层次遍历；2先左先左（子树）后右后右（子树）的遍历；3先右先右（子树）后左后左（子树）的遍历。二、先左后右的遍历算法二、先左后右的遍历算法 二叉树是由三个基本单元组成：

24、根结点、左子树和右子树。假设以L、D、R分别表示遍历左子树、访问根结点、遍历右子树。若规定先左后右，则有三种情况：DLR、LDR、LRD，分别称之为先先（根）序的遍历、中中（根）序的遍历、后后（根）序的遍历、 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（递归）（3）先序遍历右子树。（递归）先（根）序的遍历算法：先（根）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（递归）（2）访问根结点；（3）中序遍历右子树。（递归）中（根）序的遍历算法：中（根）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（递归）（2）后序遍历右

25、子树；（递归）（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：A AB BC CD DE EF FG GH HK 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 AStatus P PreO OrderTraverse( B BiT Treee T T, S Status ( * V Visit)(TElTElemT Type e) ) /采用二叉链表存储结构，采用二叉链表存储结构， VisitVisit是对数

26、据元素操作的应用是对数据元素操作的应用/函数，先序遍历二叉树函数，先序遍历二叉树T T的递归算法，对每个数据元素调用的递归算法，对每个数据元素调用/函数函数VisitVisit。最简单的最简单的VisitVisit函数是：函数是： / S Status P PrintElElement(TElTElemT Type e) /输出元素输出元素e e的值的值 / printf( e ); /实用时，加上格式串实用时，加上格式串 / return OKOK; / /调用实例调用实例： P PreO OrderT Traverse( T T, P PrintElElement);if (T T) if

27、 (V Visit(T T-data ) if (P PreO OrderT Traverse(T T-lchild, V Visit) if (P PreO OrderT Traverse(T T-rchild, V Visit) return OKOK; return ERROR ERROR; else return OKOK;/ P PreO OrderT Traverse算法算法 6.16.1S Status I InO OrderT Traverse( B BiT Treee T T, S Status ( * V Visit)(TElTElemT Type e) ) /采用二叉链表

28、存储结构，采用二叉链表存储结构， VisitVisit是对数据元素操作的应用是对数据元素操作的应用 /函数。中序遍历二叉树函数。中序遍历二叉树T T的非递归算法，对每个数据元素调用的非递归算法，对每个数据元素调用/函数函数VisitVisit。 InitStack(S); Push(S,TInitStack(S); Push(S,T); /); /根指针进栈根指针进栈 while (! StackEmpty(Swhile (! StackEmpty(S) ) while (GetTop(S,p) & p) Push(S,p-lchild while (GetTop(S,p) &

29、 p) Push(S,p-lchild);); / /向左走到尽头向左走到尽头 Pop(S,pPop(S,p); /); /空指针退栈空指针退栈 if (!StackEmpty(Sif (!StackEmpty(S) /) /访问结点，向右一步访问结点，向右一步 Pop(S,p); if( !Visit(pPop(S,p); if( !Visit(p-data) return ERROR;-data) return ERROR; Push(S,p-rchild Push(S,p-rchild);); /if /if /While /While return OK; return OK;/ In

30、OrderTraverse/ InOrderTraverse算法算法 6.26.2S Status InO OrderT Traverse( B BiT Treee T T, S Status ( * V Visit)(TElTElemT Type e) ) /采用二叉链表存储结构，采用二叉链表存储结构， VisitVisit是对数据元素操作的应用是对数据元素操作的应用/函数。中序遍历二叉树函数。中序遍历二叉树T T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调 /用函数用函数VisitVisit。 InitStack(SInitStack(S); p=T; ); p=T; wh

31、ile (p| !StackEmpty(Swhile (p| !StackEmpty(S) ) if (p) Push(S,p); p=p-lchildif (p) Push(S,p); p=p-lchild);); /根指针进栈，遍历左子树根指针进栈，遍历左子树 else else /根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树 Pop(S,p); if( !Visit(pPop(S,p); if( !Visit(p-data) return ERROR;-data) return ERROR; p=p-rchild p=p-rchild /elseelse /Whi

32、leWhile return OK; return OK; / InOrderTraverse InOrderTraverse算法算法 6.36.3ABCDEFG 遍历遍历是二叉树各种操作的基础，也可在遍是二叉树各种操作的基础，也可在遍历过程中生成结点，建立二叉树的存储结构。例如：历过程中生成结点，建立二叉树的存储结构。例如：对下面所示二叉树，按下列次序顺序读入字符对下面所示二叉树，按下列次序顺序读入字符A B C A B C D E D E G G F F 其中其中 表示空格字符，可建立相应的二叉链表。表示空格字符，可建立相应的二叉链表。Status CreateBiTree( BiTree

33、eStatus CreateBiTree( BiTreee &T ) &T ) /按先序次序输入二叉树中结点的值（一个字符），空按先序次序输入二叉树中结点的值（一个字符），空 /字符表示空树。构造二叉链表表示的二叉树字符表示空树。构造二叉链表表示的二叉树T T。 scanf(&chscanf(&ch); ); if (ch if (ch= ) T=NULL;= ) T=NULL; else else if( !(T=(BiTNode if( !(T=(BiTNode * * )malloc(sizeof(BiTNode) )malloc(sizeof(BiTNo

34、de) exit(OVERFLOWexit(OVERFLOW);); T-data=chT-data=ch; ; /生成根结点生成根结点 CreateBiTree(T-lchildCreateBiTree(T-lchild); ); /构造左子树构造左子树 CreateBiTree(T-rchildCreateBiTree(T-rchild); ); /构造右子树构造右子树 return OK; return OK; / CreateBiTree CreateBiTree算法算法 6.46.4例如:ABCD以字符“”表示A(B(,C(, ),D(, )空树空树只含一个根结点的二只含一个根结点的

35、二叉树叉树A以字符串“A ”表示以下列字符串表示ALARBLBRCLCRDLDRA B C D A BCD上页算法执行过程举例如下：ATBCD 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，由二叉树的先序和中序序列建二叉树由二叉树的先序和中序序列建二叉树 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列void CrtBT(BiTree& T,

36、 char pre, char ino, int ps, int is, int n ) / 已知preps.ps+n-1为二叉树的先序序列， / insis.is+n-1为二叉树的中序序列，本算 / 法由此两个序列构造二叉链表 if (n=0) T=NULL; else k=Search(ino, preps); / 在中序序列中查询 if (k= -1) T=NULL; else / / CrtBT T=(BiTNode*)malloc(sizeof(BiTNode);T-data = preps;if (k=is) T-Lchild = NULL;else CrtBT(T-Lchild,

37、 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 );三、算法的递归描述三、算法的递归描述void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树 if (T) visit(T-data); / 访问结点 Preorder(T-lchild, visit); / 遍历左子树 Preorder(T-rchild, visit);/ 遍历右

38、子树 四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; void Inorder_I(BiTree T, void (*visit) (TelemType& e) Stack *S; t = GoFarLeft(T, S); / 找到最左下的结点 while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-

39、rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束 / while/ Inorder_I 五五、遍历算法的应用举例遍历算法的应用举例1 1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 ( (先序遍历先序遍历) )2 2、求二叉树的深度、求二叉树的深度( (后序遍历后序遍历) )3 3、复制二叉树、复制二叉树( (后序遍历后序遍历) )4 4、建立二叉树的存储结构、建立二叉树的存储结构1 1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思

40、想: : 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参的参数，数，并将算法中“访问结点”的操作改为：若是叶若是叶子，则计数器增子，则计数器增1 1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf2 2、求二

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

42、 Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;3 3、复制二叉树、复制二叉树其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树( (后序遍历后序遍历) )BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNod

43、e *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else ne

44、wlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTreeABCDEFGHK D C B H K G F E A例如：下列二叉树的复例如：下列二叉树的复制过程如下：制过程如下：newT4 4、建立二叉树的存储结构、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的不同的定义方法相应有不同的存储结构的建立算法。建立算法。 以字符串的形式以字

45、符串的形式 根根 左子树左子树 右子树右子树定义一棵二叉树定义一棵二叉树例如:ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空树空树只含一个根结点的二只含一个根结点的二叉树叉树A以字符串“A ”表示以下列字符串表示StatusStatus CreateBiTree(BiTree & &T) scanfscanf(& &ch); ifif(ch=)T=NULLNULL; elseelse if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结

46、点 CreateBiTree(T-l lchild); / 构造左子树 CreateBiTree(T-r rchild); / 构造右子树 returnreturn OK; / CreateBiTreeA B C D A BCD上页算法执行过程举例如下：ATBCD 按给定的表达式建相应二叉树按给定的表达式建相应二叉树 由先缀表达式建二叉树由先缀表达式建二叉树例如：已知表达式的先缀表示式 - -+ + a b c / d e 由原表达式建二叉树由原表达式建二叉树例如：已知表达式 (a+b)c d/e d/e对应先缀表达式 - -+ + a b c / d e的二叉树的二叉树abcde- -+/特

47、点特点： 操作数为叶子叶子结点 运算符为分支分支结点scanf(&ch);if ( In(ch, 字母集 ) 建叶子结点;else 建根结点; 递归建左子树; 递归建右子树;由先缀表达式建二叉树的算法的基本操作：由先缀表达式建二叉树的算法的基本操作：a+b(a+b)c d/e d/ea+bc 分析表达式和二叉树的关系分析表达式和二叉树的关系:ab+abc+abc+(a+b)cabcde- -+/基本操作基本操作:scanf(&ch);if (In(ch, 字母集 ) 建叶子结点; 暂存; else if (In(ch, 运算符集) 和前一个运算符比较优先数; 若当前的优先数“高

48、”，则暂存; 否则建子树; void CrtExptree(BiTree &T, char exp ) InitStack(S); Push(S, #); InitStack(PTR); p = exp; ch = *p; while (!(GetTop(S)=# & ch=#) if (!IN(ch, OP) CrtNode( t, ch ); / 建叶子结点并入栈 else /Switch if ( ch!= # ) p+; ch = *p; / while Pop(PTR, T); / CrtExptree switch (ch) case ( : Push(S, ch)

49、; break; case ) : Pop(S, c); while (c!= ( ) CrtSubtree( t, c); / 建二叉树并入栈建二叉树并入栈 Pop(S, c) break; defult : / switch while(!Gettop(S, c) & ( precede(c,ch) CrtSubtree( t, c); Pop(S, c);if ( ch!= # ) Push( S, ch); break;建叶子结点的算法为：void CrtNode(BiTree& T,char ch) T=(BiTNode*)malloc(sizeof(BiTNode)

50、; T-data = char; T-lchild = T-rchild = NULL; Push( PTR, T );建子树的算法为：void CrtSubtree (Bitree& T, char c) T=(BiTNode*)malloc(sizeof(BiTNode); T-data = c; Pop(PTR, rc); T-rchild = rc; Pop(PTR, lc); T-lchild = lc; Push(PTR, T);ABCDEFGHK例如例如: :先序序列先序序列: : A B C D E F G H K中序序列中序序列: : B D C A H G K F

51、E后序序列后序序列: : D C B H K G F E A一、何谓线索二叉树？一、何谓线索二叉树？ 遍历二叉树的结果是，求得结点的一个线性序列。6.3.2 6.3.2 线索二叉树线索二叉树 在以二叉链表作为存储结构时，只能找到结点的左、右结点，但是得不到结点在任一序列中的前驱和后继结点，这种信息只能在遍历的过程中才能得到。 如何保存这种在遍历过程中得到的信息呢？可以利用二叉链表中的n+1个空链来存放结点的前驱和后继结点的信息。指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”与其相应的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的存储结构，称作 “线索链表线索链表

52、”例如：例如：A B C D E F G H K D C B E 对对线索链表线索链表中结点的约定：中结点的约定： 在二叉链表的结点中增加两个标志域增加两个标志域LTag 和RTag并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则Lchild域的指针指向其左子树， 且左标志域 LTag的值为 0“指针 Link”； 否则，Lchild域的指针指向其“前驱”， 且左标志LTag的值为 1“线索 Thread” 。若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树， 且右标志域RTag的值为 0 “指针 Link”；否则，rchild域的指针指向其“后继”，

53、 且右标志RTag的值为 1 “线索 Thread”。 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链线索链表表”。以某种次序遍历使其变为线索二叉树的过程。以某种次序遍历使其变为线索二叉树的过程叫做叫做线索化线索化例如，下图为一中序线索二叉树例如，下图为一中序线索二叉树ABCDEFGHKtypedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;线索链表的类型描述：

54、typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索二、线索链表的遍历算法二、线索链表的遍历算法: for ( p = firstNode(T); p; p = Succ(p) ) Visit (p); 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如例如: 对中序线索化链表的遍历算法对中序线索化链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 ？ 在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点。若若无右子树，则为则为

55、后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一第一个结点。个结点。具体算法见具体算法见 算法算法 6.5void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return error /访问其左子树为空的结点 while (p-RTag=Thread & p-rchi

56、ld!=T) p = p-rchild; Visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根 / InOrderTraverse_Thr算法算法 6.56.5 在中序遍历过程中修改结点的左、右指针域，在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的以保存当前访问结点的“前驱前驱”和和“后继后继”信息。信息。遍历过程中，附设指针遍历过程中，附设指针pre, 并始终保持指针并始终保持指针pre指向当前访问的指针指向当前访问的指针p所指结点的前驱。所指结点的前驱。三、如何建立线索链表？三、如何建立线索链表？Status InOrderThre

57、ading(BiThrTree &Thrt, BiThrTree T) / 中中序遍历二叉树T，并将其中序线索化，Thrt指向头结点 if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; /建头结点 Thrt-rchild = Thrt; / 右指针回指 if (!T) Thrt-lchild = Thrt; /若二叉树空,则左指针回指 else Thrt-lchild = T; pre = Thrt; InThreading(T);

58、 /中序遍历进行线索化 pre-rchild = Thrt; / 最后一个结点线索化 pre-RTag = Thread; Thrt-rchild = pre; return OK; / InOrderThreading 算法算法 6.66.6void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag

59、= Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InThreading算法算法 6.76.76.4 6.4 树和森林树和森林ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=7data parent一、双亲表示法一、双亲表示法: :6.4.1 树的存储结构树的存储结构#define MAX_TREE_SIZE 100 typedef struct PTNode Elem data; int parent; / 双

60、亲位置域 PTNode; data parent结点结构结点结构:C C语言的类型描述语言的类型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;树结构树结构:ABCDEFG二、孩子链表表示法二、孩子链表表示法: :0 A -11 B 02 C 03 D 04 E 25 F 26 G 4r=0n=7 data firstchild 1 2 34 56-1000224typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: child nextC C语言的类型描述语言的类型描述: :Next: 指向下一孩子结点的指针指向下一孩子结点的指针 typedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstch