数据结构-清华大学-殷人昆ppt课件

1、第第4章章 树与二叉树树与二叉树数据结构课件数据结构课件第第1;.202-2第第 4 章章 树与二叉树树与二叉树202-3树和森林的概念树和森林的概念n树的定义树的定义 r树是由树是由n (n0) 个结点组成的有限集合：个结点组成的有限集合：有一个特定的称之为根有一个特定的称之为根(root)的结点；的结点；除根以外的其它结点划分为除根以外的其它结点划分为 m (m0) 个个 互不相交的有限集合互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树。，每个集合又是一棵树，并且称之为根的子树。n此定义是离散数学和图论中给出的。它们把树视为图的一个极小连通子图。此定义是

2、离散数学和图论中给出的。它们把树视为图的一个极小连通子图。有有 n 个个结点的树有结点的树有 n-1 条边，而且不能有回路。条边，而且不能有回路。202-4n这种观点的典型代表是这种观点的典型代表是 Knuth。他。他认为认为图至少有一个顶点，树也必须至少有一个顶图至少有一个顶点，树也必须至少有一个顶点。点。树不能是空树，但树不能是空树，但 N 叉树可以是空树。叉树可以是空树。N 叉树是限制根的子树最多不能超过叉树是限制根的子树最多不能超过 N 棵的树。棵的树。n随着对树讨论的深入，人们放宽了对树结构的限制。若把树当作层次结构单独对待，随着对树讨论的深入，人们放宽了对树结构的限制。若把树当作层

3、次结构单独对待，树中允许结点个数树中允许结点个数为为0。这样，树与。这样，树与N叉树就没有不可逾越的鸿沟了。叉树就没有不可逾越的鸿沟了。n从面向对象从面向对象观点，观点，N叉树是树的特殊实现：树是父类，叉树是树的特殊实现：树是父类，N叉树是子类。叉树是子类。N叉树继承了叉树继承了树的特性，它还有自己增加的特性，例如树的特性，它还有自己增加的特性，例如202-5r理论上树不可是空树，理论上树不可是空树，N叉树可以是空树；叉树可以是空树；r树的子树可以有序，也可以不要求有序，而树的子树可以有序，也可以不要求有序，而N叉树的子树必须有序。叉树的子树必须有序。rN叉树的定义也是递归的，递归到空树终止；

4、树则递归到只有一个结点的子树。叉树的定义也是递归的，递归到空树终止；树则递归到只有一个结点的子树。r树的子树棵数不限，而树的子树棵数不限，而N叉树中根的子树最多叉树中根的子树最多N棵。棵。r树可以区分为外向树和内向树，而树可以区分为外向树和内向树，而N叉树一般是外向树，即边是有向的，从父叉树一般是外向树，即边是有向的，从父指向子。指向子。r树可以用树可以用N叉树实现。二叉树、叉树实现。二叉树、B树等又都是树等又都是N叉树的特殊情形。叉树的特殊情形。202-6树的特点树的特点n树是分层结构，又是递归结构。每棵子树的根结点有且仅有一个直接前驱，但可以树是分层结构，又是递归结构。每棵子树的根结点有且

5、仅有一个直接前驱，但可以有有 0 个或多个直接后继。个或多个直接后继。1层层2层层4层层3层层depth = 4height= 4ACGBDEFKLHMIJ前驱前驱后继后继202-71层2层4层3层depth = 4height = 4ACGBDEFKLHMIJ结点结点结点的度结点的度分支结点分支结点叶结点叶结点子女子女双亲双亲兄弟兄弟祖先祖先树的度树的度树树深度深度树高度树高度森林森林子孙子孙结点层次结点层次结点深度结点深度结点高度结点高度202-8n注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从根向下注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从

6、根向下逐层计算的；结点的高度是从下向上逐层计算的：逐层计算的；结点的高度是从下向上逐层计算的：叶结点的高度为叶结点的高度为1, 其他结点的高度其他结点的高度是取它的所有子女结点最大高度加一。是取它的所有子女结点最大高度加一。n树的深度与高度相等。树的深度与高度相等。树的深度按离根最远的树的深度按离根最远的叶结点算，树的高度按叶结点算，树的高度按根结点算，都是根结点算，都是6。l叶结点也称为终端结点，叶结点也称为终端结点，非叶结点也称为非终端非叶结点也称为非终端结点。结点。ABCDEFGHILKJ高度=4深度=3202-9二叉树的五种不同形态二叉树的五种不同形态LLRR二叉树二叉树 (Binar

7、y Tree)n二叉树的定义二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。分别称为左子树和右子树的、互不相交的二叉树组成。n这个定义是递归的。这个定义是递归的。202-10二叉树的性质二叉树的性质性质性质1 若二叉树的层次从若二叉树的层次从 1 开始开始, 则在二叉树的第则在二叉树的第 i 层最多有层最多有 2i-1 个结点。个结点。( i1)证明用数学归纳法证明用数学归纳法r i = 1时，根结点只有时，根结点只有1个，个，21-

8、-1 = 20 =1；r若设若设 i = k 时性质成立，即该层最多有时性质成立，即该层最多有 2k- -1 个结点，则当个结点，则当 i = k+1 时，由于第时，由于第 k 层层每个结点最多可有每个结点最多可有 2 个子女，第个子女，第 k+1 层最多结点个数可有层最多结点个数可有 2*2k-1 = 2k 个，故性个，故性质成立。质成立。202-11性质性质2高度为高度为 h 的二叉树最多有的二叉树最多有 2h -1个结点。个结点。(h1)证明用求等比级数前证明用求等比级数前k项和的公式项和的公式高度为高度为 h 的二叉树有的二叉树有 h 层，各层最多结点个数相加，得到等比级数，求和得：层

9、，各层最多结点个数相加，得到等比级数，求和得： 20 + 21 + 22 + + 2h-1 = 2h-1n 空树的高度为空树的高度为 0，只有根结点，只有根结点的树的高度为的树的高度为 1。202-12性质性质3对任何一棵二叉树对任何一棵二叉树, 如果其叶结点有如果其叶结点有 n0 个个, 度为度为2的非叶结点有的非叶结点有 n2 个个, 则有则有 n0n21证明：证明：若设度为若设度为 1 的结点有的结点有 n1 个，总结点个数为个，总结点个数为 n，总边数为，总边数为 e，则根据二叉树的定义，则根据二叉树的定义，n = n0+n1+n2 e = 2n2+n1 = n-1因此，有因此，有 2

10、n2+n1 = n0+n1+n2-1n2 = n0-1 n0 = n2+1n引申：可用于判断二叉树各类结点个数。引申：可用于判断二叉树各类结点个数。202-13定义定义1 满二叉树满二叉树 (Full Binary Tree) 定义定义2 完全二叉树完全二叉树 (Complete Binary Tree)r若设二叉树的高度为若设二叉树的高度为 h，则共有，则共有 h 层。除第层。除第 h 层外，其它各层层外，其它各层 (1h-1) 的结点数的结点数都达到最大个数，第都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。层从右向左连续缺若干结点，这就是完全二叉树。202-14性质性

11、质4具有具有 n (n0) 个结点的完全二叉树的高度为个结点的完全二叉树的高度为 log2(n+1) 证明：设完全二叉树的高度为证明：设完全二叉树的高度为 h，则有，则有 2h-1-1n 2h-1 上面上面h-1层结点数层结点数 包括第包括第h层的最大结点数层的最大结点数变形变形 2h-1n+12h 取对数取对数 h-1log2(n+1)h 有有 h = log2(n+1) 23-124-1202-1523-124-1注意：注意：n求高度的另一公式为求高度的另一公式为 log2n +1, 此公式对于此公式对于 n = 0 不适用。不适用。n若设完全二叉树中叶结点有若设完全二叉树中叶结点有 n0

12、 个个, 则该二叉树总的结点数为则该二叉树总的结点数为 n = 2n0, 或或 n = 2n0 1。n若完全二叉树的结点数为奇数，没有度为若完全二叉树的结点数为奇数，没有度为1的结点；为偶数，有一个度为的结点；为偶数，有一个度为1的结点。的结点。n右图为理想平衡树，右图为理想平衡树，上层都是满的，第上层都是满的，第 h 层结点分布在各层结点分布在各处。处。202-16性质性质5如将一棵有如将一棵有 n 个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号: 0, 1, 2, , n-1，则有以下关系：，则有以下关系： r若若i = 0

13、, 则则 i 无双亲；无双亲；若若i 0, 则则 i 的双亲为的双亲为 (i-1)/2 。r若若2*i+1 n, 则则 i 的左子女为的左子女为 2*i+1；若若2*i+2 1, 则则 i 的双亲为的双亲为 i / 2 。r若若2*i = n, 则则 i 的左子女为的左子女为 2*i；若若2*i+1 lchild ); visit ( T-data ); InOrder ( T-rchild ); nvisit()是输出数据值的操作，在实际使用时可用相应的操作来替换。是输出数据值的操作，在实际使用时可用相应的操作来替换。202-27前序遍历二叉树算法的框架是：前序遍历二叉树算法的框架是：n若二

14、叉树为空，则空操作；若二叉树为空，则空操作；n否则否则u访问根结点访问根结点 (V)；u前序遍历左子树前序遍历左子树 (L)；u前序遍历右子树前序遍历右子树 (R)。遍历结果遍历结果 - - + a * b - - c d / e f前序遍历前序遍历 (Preorder Traversal)- -/ /+ +* *abcdef202-28二叉树递归的前序遍历算法二叉树递归的前序遍历算法void PreOrder (BiTNode *T) if (T != NULL) visit (T-data); PreOrder (T-lchild); PreOrder (T-rchild); n与中序遍历

15、算法相比，与中序遍历算法相比，visit() 操作放在两个子树递归前序遍历的最前面。操作放在两个子树递归前序遍历的最前面。202-29后序遍历二叉树算法的框架是：后序遍历二叉树算法的框架是：n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则否则u后序遍历左子树后序遍历左子树 (L)；u后序遍历右子树后序遍历右子树 (R)；u访问根结点访问根结点 (V)。遍历结果遍历结果 a b c d - - * + e f / - -后序遍历后序遍历 (Postorder Traversal)- -/ /+ +* *abcdef202-30二叉树递归的后序遍历算法二叉树递归的后序遍历算法void Po

16、stOrder (BiTNode *T) if (T != NULL) PostOrder (T-lchild); PostOrder (T-rchild); visit (T-data); n与中序遍历算法相比，与中序遍历算法相比，visit() 操作放在两个子树递归前序遍历的最后面。操作放在两个子树递归前序遍历的最后面。202-31计算二叉树结点个数的递归算法计算二叉树结点个数的递归算法应用二叉树遍历的事例应用二叉树遍历的事例int Count (BiTNode *T) if (T = NULL) return 0; else return 1+ Count (T-lchild) + Co

17、unt (T-rchild);n空二叉树的结点个数为空二叉树的结点个数为 0，可直接计算；否则可分别计算左、右子树的结点个数，再，可直接计算；否则可分别计算左、右子树的结点个数，再相加得到总结点个数。相加得到总结点个数。202-32求二叉树高度的递归算法求二叉树高度的递归算法int Height ( BiTNode *T ) if (T = NULL) return 0; else int m = Height (T-lchild); int n = Height (T-rchild); return (m n) ? m+1 : n+1; n空树的高度为空树的高度为 0；非空树情形，先计算根结

18、点左右子树的高度，取大者再加一得到二；非空树情形，先计算根结点左右子树的高度，取大者再加一得到二叉树高度。叉树高度。202-33abcecdcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 结束结束利用栈的前序遍历的非递归算法利用栈的前序遍历的非递归算法d dc202-34void PreOrder(BinTree T) stack S; InitStack(S); /递归工作栈递归工作栈 BiTNode * p = T; Push (S, NULL); while (p != NUL

19、L) visit(p-data); if (p-rchild != NULL) Push(S, p-rchild); if (p-lchild != NULL) p = p-lchild; /进左子树进左子树 else Pop(S, p); /左子树空左子树空, 进右子树进右子树 202-35abcdebaadaa左空左空退栈退栈访问访问左空左空退栈退栈访问访问退栈退栈访问访问左空左空ec退栈访问退栈访问cc右空右空退栈访问退栈访问 栈空结束栈空结束利用栈的中序遍历的非递归算法利用栈的中序遍历的非递归算法202-36 void InOrder(BinTree T) stack S; InitS

20、tack(S); /递归工作栈递归工作栈 BiTNode *p = T; /初始化初始化 do while (p != NULL) /子树非空找中序第一个子树非空找中序第一个 Push(S, p); p = p-lchild; /边找边进栈边找边进栈 if (!StackEmpty(S) /栈非空栈非空 Pop(S, p); /子树中序第一个退栈子树中序第一个退栈 visit(p-data); /访问之访问之 p = p-rchild; /向右子树走向右子树走 while ( p != NULL | !StackEmpty(S) );202-37n后序遍历时使用的栈的结点定义后序遍历时使用的栈

21、的结点定义typedef struct BiTNode *ptr; /结点指针结点指针 enum tag L, R ; /该结点退栈标记该结点退栈标记 StackNode; n根结点的根结点的rtag = L，表示从左子树退出，表示从左子树退出, 访问右子树。访问右子树。rtag = R, 表示表示从右子树退出从右子树退出, 访问根。访问根。ptr tagL,R 利用栈的后序遍历的非递归算法利用栈的后序遍历的非递归算法202-38abcdeaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaR202-39利用栈的后序遍历的非递归算法利用栈的后序

22、遍历的非递归算法void PostOrder(BinTree T) stack S; InitStack(S); StackNode w; BiTNode *p = T; do while (p != NULL) /向左子树走向左子树走 w.ptr = p; w.tag = L; Push(S, w); p = p-lchild; int succ = 1; /继续循环标记继续循环标记202-40 while (succ & !StackEmpty(S) Pop(S, w); p = w.ptr; switch (w.tag) /判断栈顶判断栈顶tag标记标记 case L : w.t

23、ag = R; Push(S, w); succ = 0; p = p-rchild; break; case R : visit(p-data); while ( !StackEmpty(S) );202-41二叉树的计数二叉树的计数n由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。n例例, 前序序列前序序列 ABHFDECKG 和中序序列和中序序列 HBDFAEKCG , 构造构造二叉树过程如下：二叉树过程如下：HBDFEKCGAEKCGABHDF202-42KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG20

24、2-43612345789612375849n如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。n问题是：固定前序排列，选择所有可能的中序排列，可以构造出多少种不同的二叉树？问题是：固定前序排列，选择所有可能的中序排列，可以构造出多少种不同的二叉树？202-44123123123123123n例如例如, 有有 3 个数据个数据 1, 2, 3 ，可得，可得 5 种不同的二叉树。它们的前序排列均为种不同的二叉树。它们的前序排列均为 123，中序，中序序列可能是序列可能是 123，132，213，231，321。n那么，如何

25、推广到一般情形呢？首先，只有一个结点的不同二叉树只有一个；有那么，如何推广到一般情形呢？首先，只有一个结点的不同二叉树只有一个；有 2 个个结点的不同二叉树只有结点的不同二叉树只有 2 种，其他情况呢？种，其他情况呢？202-45b0 =1b1 =1b2 =2b3 =5 b4 =14有有0个个, 1个个, 2个个, 3个结点的不同二叉树如下个结点的不同二叉树如下202-46n!n!(2n)!1n11n1bCn2nnbibn-i-111n0i1ininbbb计算具有计算具有 n 个结点的不同二叉树的棵数个结点的不同二叉树的棵数nCatalan函数函数n例例512345641131bC363141

26、234567851141bC484202-47线索二叉树线索二叉树 (Threaded Binary Tree)n又称为穿线树。又称为穿线树。n通过二叉树遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某通过二叉树遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。数据在这种排列下它的前驱和后继。n希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后下的前驱、后继关系记

27、在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。继。n为此，在二叉树存储结点中增加线索信息。为此，在二叉树存储结点中增加线索信息。202-48线索线索 (Thread)n增加前驱增加前驱Pred指针和后继指针和后继Succ指针的二叉树指针的二叉树pred lchild data rchild succabcdepredpredpredsuccsuccsuccDAEBCrootpredpredpredpredsuccsuccsuccsucc202-49n这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。n

28、改造树结点，将改造树结点，将 pred 指针和指针和 succ 指针压缩到指针压缩到 lchild 和和 rchild 的空闲指针中，并增设两的空闲指针中，并增设两个标志个标志 ltag 和和 rtag，指明指针是指示子女还是前驱后继。后者称为线索。，指明指针是指示子女还是前驱后继。后者称为线索。nltag (或或rtag) = 0，表示相应指针指示左子女（或右子女结点）；，表示相应指针指示左子女（或右子女结点）；nltag (或或rtag) = 1, 表示相应指针为前驱（或后继）线索。表示相应指针为前驱（或后继）线索。 lchild ltag data rtag rchild 202-50中

29、序线索二叉树及其链表表示中序线索二叉树及其链表表示lchild ltag data rtag rchild abcdepredpredpredsuccsuccsuccDAEBCrootpredpredsuccsucc0000111111202-51typedef int TTElemType;typedef struct node int ltag, rtag; struct node *lchild, *rchild; TTElemType data; ThreadNode, *ThreadTree;n注意，线索二叉树在树结点中增加了注意，线索二叉树在树结点中增加了ltag和和rtag，改变

30、了二叉树的结构。，改变了二叉树的结构。线索二叉树的结构定义线索二叉树的结构定义202-52通过中序遍历建立中序线索二叉树通过中序遍历建立中序线索二叉树void InThread (ThreadNode *t, ThreadNode *& pre) /预设了一个预设了一个 pre 指针，指示指针，指示 t 的中序前驱，在主的中序前驱，在主 /程序中预置为程序中预置为NULL if (t != NULL) InThread (t-lchild, pre); /递归递归, 左子树线索化左子树线索化 if (t-lchild = NULL) t-lchild = pre; t-ltag = 1

31、; /建立当前结点建立当前结点 t 的前驱线索的前驱线索202-53 if ( pre & pre-rchild = NULL ) pre-rchild = t; pre-rtag = 1; /建立前驱结点建立前驱结点 pre 的后继线索的后继线索pre = t;/前驱跟上当前指针前驱跟上当前指针InThread (t-rchild, pre); /递归递归, 右子树线索化右子树线索化 n使用此函数可以把以使用此函数可以把以 t 为根的子树一次中序线索化，但中序下最后一个结点的后继为根的子树一次中序线索化，但中序下最后一个结点的后继线索没有加上，指针线索没有加上，指针 pre 在退出时

32、正在指示这一结点。在退出时正在指示这一结点。202-54void CreateInThread (ThreadTree T) ThreadNode *pre = NULL; /前驱指针前驱指针 if ( T != NULL ) /树非空树非空, 线索化线索化 InThread (T, pre);/中序遍历线索二叉树中序遍历线索二叉树 pre-rchild = NULL; pre-rtag = 1; /后处理后处理, 中序最后一个结点中序最后一个结点 n通过该主程序实现了对二叉树的中序线索化。它是基于二叉树的中序遍历实现的。通过该主程序实现了对二叉树的中序线索化。它是基于二叉树的中序遍历实现的。

33、202-550 A 0 0 B 0 0 C 0 0 D 0 0 E 0 Tpre = NULLt202-560 A 0 1 B 0 0 C 0 0 D 0 0 E 0 Tpre = NULLt202-570 A 0 1 B 0 0 C 0 1 D 0 0 E 0 Tpret202-580 A 0 1 B 0 0 C 0 1 D 1 0 E 0 Tpret202-590 A 0 1 B 0 0 C 0 1 D 1 1 E 0 Tpret202-600 A 0 1 B 0 0 C 0 1 D 1 1 E 1 Tpret202-610 A 0 1 B 0 0 C 1 1 D 1 1 E 1 Tpre

34、后处理202-62寻找结点寻找结点 p 在中序下的后继在中序下的后继if (p-rtag =1) 后继为后继为 p-rchildelse /p-rtag != 1 后继为结点后继为结点 p 右子树右子树 q 中的中序下的第一中的中序下的第一 个结点个结点ABDECFHIKGJ202-63ThreadNode * First ( ThreadNode *t ) /函数返回以函数返回以 *t 为根的线索二叉树中的中序序列下为根的线索二叉树中的中序序列下/的第一个结点的第一个结点 ThreadNode *p = t; while ( p-ltag = 0 ) p = p-lchild; return

35、 p; /最左下的结点最左下的结点ThreadNode * Next ( ThreadNode * p ) /函数返回在线索二叉树中结点函数返回在线索二叉树中结点 *p 在中序下的后在中序下的后/继结点继结点202-64 if ( p-rtag = 0 ) return First(p-rchild); /p-rtag=0, 后继为右子树中序第一个结点后继为右子树中序第一个结点 else return p-rchild;/p-rtag=1, 直接返回后继线索直接返回后继线索void Inorder ( ThreadNode * t ) /以以 t 为根的线索二叉树的中序遍历为根的线索二叉树的中

36、序遍历 ThreadNode * p; for ( p = First (t); p != NULL; p = Next (p) ) cout data ltag=1) 前驱为前驱为 p-lchild else /p-leftThread=0 前驱为结点前驱为结点 p 左子树左子树 中序下的最后一个结中序下的最后一个结 点点 ABDECFHIKGJL202-66 A B D C Ep-ltag=1?前驱线索前驱线索 = 左子女左子女后继为后继为p-lchild= 无后继无后继 后继为后继为p-rchildABCED前序线索二叉树前序线索二叉树202-67 p-rtag=1?后继线索后继线索 =

37、 右子女右子女后继为后继为 的右子树中的右子树中后序下第一个结点后序下第一个结点 后继为后继为p-rchild= 无后继无后继 后继为后继为qABCEDq=p-parentq=NULL?q-rtag=1 |q-rchild=p?= 后序线索二叉树后序线索二叉树202-68n树的存储表示树的存储表示 双亲表示双亲表示r为了操作实现的方便，有时会规定结点的存放顺序。例如，可以按树的前序次序为了操作实现的方便，有时会规定结点的存放顺序。例如，可以按树的前序次序存放树中的各个结点，或按树的层次次序安排所有结点。存放树中的各个结点，或按树的层次次序安排所有结点。树与树的遍历树与树的遍历ABCDEFGda

38、taparentA B C D E F G- -1 0 0 0 1 1 30 1 2 3 4 5 6202-69子女链表表示子女链表表示n无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。ABCDEFG123456ABCDEFG0123456202-70子女指针表示子女指针表示n一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。数不同，每个结点设置数目不等的指针，将

39、很难管理。n为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。）。n这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。储浪费。202-71等数量的链域等数量的链域ABCDEFG data child1child2child3childdABCDEFG 空链域空链域2n+1个202-72子女子女-兄弟表示兄弟表示n也称为树的二叉树表示。结点构造为：也称为树的二叉树表示。结点构造为：nfirstChild

40、 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。女。nnextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。n若想找某结点的所有子女，可先找若想找某结点的所有子女，可先找firstChild,再反复用再反复用 nextSibling 沿链扫描。沿链扫描。 datafirstChildnextSibling202-73树的左子女树的左子女 - - 右兄弟表示右兄弟表示 datafchildnsiblingABCDEFGABCDGF

41、E202-74左子女左子女-右兄弟表示的树的结构定义右兄弟表示的树的结构定义typedef int TElemType;typedef struct node TElemType data; struct node *fchild, *nsibling; CSNode, *CSTree;n注意，虽然此定义与二叉树的类似，操作也类似，但语义是不同的。注意，虽然此定义与二叉树的类似，操作也类似，但语义是不同的。n树结构是递归的，可用递归函数实现相应操作。树结构是递归的，可用递归函数实现相应操作。202-75寻找双亲寻找双亲 子女子女 兄弟的操作兄弟的操作TreeNode *FindParent (

42、 CSNode *T, CSNode *p ) /在以在以 T 为根的树中找结点为根的树中找结点 p 的双亲的双亲 if (T = NULL | p = NULL) return NULL; CSNode *q = T-fchild, *s; while (q != NULL & q != p) /循根的长子的兄弟链循根的长子的兄弟链,递归在子树中搜索递归在子树中搜索 if (s = FindParent (q, p) ) != NULL) return s; /在以在以 q 为根的子树找到为根的子树找到 p 的双亲，返回的双亲，返回 q = q-nsibling; 202-76 if

43、 (q != NULL & q = p) return T; /找到双亲找到双亲 else return NULL; /未找到双亲未找到双亲TreeNode * FindfirstChild ( CSNode * p ) /在树中找结点在树中找结点 p 的第一个子女的第一个子女 if ( p != NULL ) return p-fchild; else return NULL;TreeNode * FindnextSibling ( CSNode *p ) /在树中找结点在树中找结点 p 的兄弟的兄弟202-77 if ( p != NULL ) return p-nsibling;

44、 else return NULL;n深度优先遍历深度优先遍历 r先根次序遍历先根次序遍历r后根次序遍历后根次序遍历n广度优先遍历广度优先遍历树的遍历树的遍历ABCDEFGABCEDGF二叉树表示二叉树表示202-78n当树非空时当树非空时r访问根结点访问根结点r依次先根遍历根的各棵子树依次先根遍历根的各棵子树n树先根遍历树先根遍历 ABEFCDG对应二叉树前序遍历对应二叉树前序遍历 ABEFCDGn树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树表示的前序遍历结果相同表示的前序遍历结果相同n树的先根遍历可以借助对应二叉树的前序遍历算法实现树的先根遍历可以借助对应二叉树的前序遍历算

45、法实现ABCEDGF树的先根次序遍历树的先根次序遍历ABCDEFG202-79树的先根次序遍历的递归算法树的先根次序遍历的递归算法void PreOrder ( CSNode *t ) /以指针以指针 t 为根为根, 先根次序遍历先根次序遍历 if ( t != NULL ) visit ( t-data ); /访问根结点访问根结点 CSNode *p = t-fchild; /第一棵子树第一棵子树 while ( p != NULL ) PreOrder (p); /递归先根遍历子树递归先根遍历子树 p = p-nsibling; 202-80n当树非空时当树非空时r依次后根遍历根的各棵子

46、树依次后根遍历根的各棵子树r访问根结点访问根结点n树后根遍历树后根遍历 EFBCGDA对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAn树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树表示的中序遍历结果相同表示的中序遍历结果相同n树的后根遍历可以借助对应二叉树的中序遍历算法实现树的后根遍历可以借助对应二叉树的中序遍历算法实现ABCEDGF树的后根次序遍历树的后根次序遍历ABCDEFG202-81树的后根次序遍历的递归算法树的后根次序遍历的递归算法void PostOrder ( CSNode *t ) /以指针以指针 t 为根为根, 按后根次序遍历树按后根次序遍历树 if (

47、t != NULL ) CSNode *p = t-fchild; while ( p != NULL ) PostOrder ( p ); p = p-nsibling; visit ( t-data ); /最后访问根结点最后访问根结点 202-82 ABCDEFGvoid LevelOrder ( CSTree T ) /分层遍历树，算法用到一个队列分层遍历树，算法用到一个队列 Queue Q; InitQueue(Q); CSNode *p; if ( T != NULL ) /树不空树不空 EnQueue(Q, T); /根结点进队列根结点进队列广度优先广度优先(层次次序层次次序)遍

48、历遍历ABCEDGFABCDEFG202-83 while ( ! QueueEmpty(Q) ) DeQueue(Q, p); visit(p-data); /队列中取一个并访问之队列中取一个并访问之 p = p-fchild; /待访问结点的子女结点进队列待访问结点的子女结点进队列 while ( p != NULL ) EnQueue ( Q, p ); p = p-nsibling; 202-84森林与二叉树的转换森林与二叉树的转换n将一般树化为二叉树表示就是用树的子女将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。兄弟表示来存储树的结构。n森林与二叉树表示的转换可以借助

49、树的二叉树表示来实现。森林与二叉树表示的转换可以借助树的二叉树表示来实现。202-85T1 T2 T3AFHT1 T2 T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3 棵树的森林棵树的森林各棵树的二叉树表示各棵树的二叉树表示森林的二叉树表示森林的二叉树表示202-86森林转化成二叉树的规则森林转化成二叉树的规则若若 F 为空，即为空，即 n = 0，则对应的二叉树，则对应的二叉树 B 为空树。为空树。若若 F 不空，则不空，则二叉树二叉树 B 的根是的根是 F 第一棵树第一棵树 T1 的根；的根；其左子树为其左子树为 B (T11, T12, , T1m )，其中，其中，T

50、11, T12, , T1m 是是 T1 的根的子树；的根的子树；其右子树为其右子树为 B (T2, T3, , Tn )，其中，其中，T2, T3, , Tn 是除是除 T1 外其它树构成的外其它树构成的森林。森林。202-87二叉树转换为森林的规则二叉树转换为森林的规则如果如果 B 为空，则对应的森林为空，则对应的森林 F 也为空。也为空。如果如果 B 非空，则非空，则F 中第一棵树中第一棵树 T1 的根为的根为 B 的根；的根；T1 的根的子树森林的根的子树森林 T11, T12, , T1m 是由是由 B 的根的左子树的根的左子树 LB 转换而来；转换而来；F 中除了中除了 T1 之外

51、其余的树组成的森林之外其余的树组成的森林 T2, T3, , Tn 是由是由 B 的根的右子树的根的右子树 RB 转换而成的森林。转换而成的森林。202-88例题例题n设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为 m1，m2 和和 m3。那。那么在由该森林转化成的二叉树中根结点的右子树上有（么在由该森林转化成的二叉树中根结点的右子树上有（ ）个结点。）个结点。 A. m1+m2 B. m2+m3 C. m3+m1 D. m1+m2+m3【解答解答】在由森林转化成的二叉树中根结点的右子树上的结点是除第一棵外其他树上的结在由森林转

52、化成的二叉树中根结点的右子树上的结点是除第一棵外其他树上的结点，应有点，应有m2+m3 个，故选择个，故选择 B。 202-89森林的遍历森林的遍历n森林的遍历也分为深度优先遍历（包括先根次序遍历和中根次序遍历）和广度优先遍森林的遍历也分为深度优先遍历（包括先根次序遍历和中根次序遍历）和广度优先遍历。历。深度优先遍历深度优先遍历n给定森林给定森林 F，若，若 F = ，则遍历结束。否则，则遍历结束。否则n若若F = T1 = r1, T11, , T1k , T2, ., Tm，则可以导出先根遍历、中根遍历两种方法。，则可以导出先根遍历、中根遍历两种方法。其中，其中，r1 是第一棵树的根结点，

53、是第一棵树的根结点，T11, , T1k是第一棵树的子树森林，是第一棵树的子树森林，T2, .,Tm是除是除去第一棵树之后剩余的树构成的森林。去第一棵树之后剩余的树构成的森林。202-90n若森林若森林F = ，返回；否则，返回；否则r访问森林的根（也是第一棵树的根）访问森林的根（也是第一棵树的根）r1；r先根遍历森林第一棵树的根的子树森林先根遍历森林第一棵树的根的子树森林T11, , T1k；r先根遍历森林中除第一棵树外其他树组成的森林先根遍历森林中除第一棵树外其他树组成的森林T2, .,Tm。 注意，注意， 是一个循环，对于每一个是一个循环，对于每一个T1i，执行树的先根次序遍历；，执行树

54、的先根次序遍历； 是一个递归是一个递归过程，重新执行过程，重新执行 T2 为第一棵树的森林的先根次序遍历。为第一棵树的森林的先根次序遍历。森林的先根次序遍历森林的先根次序遍历202-91n森林的先根次序遍历的结果序列森林的先根次序遍历的结果序列ABCDE FG HIKJn这相当于对应二叉树的前序遍历结果。这相当于对应二叉树的前序遍历结果。T1 T2 T3AFHBCDGIJEKBAEDHIKJFGC202-92森林的中根次序遍历森林的中根次序遍历n若森林若森林 F = ，返回；否则，返回；否则r中根遍历森林中根遍历森林 F 第一棵树的根结点的子树森林第一棵树的根结点的子树森林T11, , T1k

55、；r访问森林的根结点访问森林的根结点 r1；r中根遍历森林中除第一棵树外其他树组成的森林中根遍历森林中除第一棵树外其他树组成的森林T2, ., Tm。注意，与先根次序遍历相比，访问根结点的时机不同。所以在注意，与先根次序遍历相比，访问根结点的时机不同。所以在的情形，对以的情形，对以T2为第一棵树的森林遍历时，重复执行为第一棵树的森林遍历时，重复执行的操作。的操作。202-93n森林的中根次序遍历的结果序列森林的中根次序遍历的结果序列BCEDA GF KIJHn这相当于对应二叉树中序遍历的结果。这相当于对应二叉树中序遍历的结果。T1 T2 T3AFHBCDGIJEKBAEDHIKJFGC202-

56、94广度优先遍历（层次序遍历）广度优先遍历（层次序遍历）AFH BCDGIJ EKABCEDHIKJFGn若森林若森林 F 为空，返回；为空，返回；否则否则r依次遍历各棵树的依次遍历各棵树的根结点；根结点；r依次遍历各棵树根依次遍历各棵树根结点的所有子女；结点的所有子女；r依次遍历这些子女依次遍历这些子女结点的子女结点；结点的子女结点；202-95树的应用树的应用n二叉排序树二叉排序树n平衡二叉树平衡二叉树nHuffman树树n堆堆n并查集并查集202-96二叉排序树二叉排序树 ( Binary Search Tree )n定义定义 r二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：二叉

57、排序树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为查找依据的关键字每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相，所有结点的关键字互不相同。同。左子树（如果非空）上所有结点的关键字都小于根结点的关键字。左子树（如果非空）上所有结点的关键字都小于根结点的关键字。右子树（如果非空）上所有结点的关键字都大于根结点的关键字。右子树（如果非空）上所有结点的关键字都大于根结点的关键字。左子树和右子树也是二叉排序树。左子树和右子树也是二叉排序树。202-97351545504025102030二叉排序树例二叉排序树例n结点左子树上所有关键结点左子树上所有关键字小于

58、结点关键字；字小于结点关键字；n结点右子树上所有关键结点右子树上所有关键字大于结点关键字；字大于结点关键字；n如果对一棵二叉排序树如果对一棵二叉排序树进行中序遍历，可以按进行中序遍历，可以按从小到大的顺序将各结从小到大的顺序将各结点关键字排列起来。点关键字排列起来。n注意，国外教材统称为二叉搜索树或二叉查找树。注意，国外教材统称为二叉搜索树或二叉查找树。202-98例题例题n一棵一棵二叉树是二叉排序树的（二叉树是二叉排序树的（ ）条件是树中任一结点的关键字值都大于左子女的关）条件是树中任一结点的关键字值都大于左子女的关键字值，小于右子女的关键字值。键字值，小于右子女的关键字值。 A. 充分但不

59、必要充分但不必要 B. 必要但不充分必要但不充分 C. 充分且必要充分且必要 D. 既不充分也不必要既不充分也不必要【解答解答】 B。通俗来讲，必要条件是指符合定义则必具有后续讲的特性。显然通俗来讲，必要条件是指符合定义则必具有后续讲的特性。显然一棵一棵二叉树是二叉排二叉树是二叉排序树，则树中任一结点的关键字值一定大于左子女的关键字值，小于右子女的关键字序树，则树中任一结点的关键字值一定大于左子女的关键字值，小于右子女的关键字值。充分条件是指满足值。充分条件是指满足202-99后续讲的特性则定义一定成立。就是说，如果一棵后续讲的特性则定义一定成立。就是说，如果一棵二叉树任一结点的关键字值都大于

60、二叉树任一结点的关键字值都大于左子女的关键字值，小于右子女的关键字值，则它一定是二叉排序树。这就不一定了。左子女的关键字值，小于右子女的关键字值，则它一定是二叉排序树。这就不一定了。右图描述的二叉树满足树中右图描述的二叉树满足树中任一结点的关键字值一定大任一结点的关键字值一定大于左子女的关键字值，小于于左子女的关键字值，小于右子女的右子女的关键字值，但它不关键字值，但它不是二叉排序树。是二叉排序树。2515353045102050202-100二叉排序树的结构定义二叉排序树的结构定义typedef char BSTElemType;/树结点数据类型树结点数据类型typedef struct node /二叉排序树结点二叉排序树结点 BSTElemType d