数据结构清华大学殷人昆04.ppt

《数据结构清华大学殷人昆04.ppt》由会员分享，可在线阅读，更多相关《数据结构清华大学殷人昆04.ppt（202页珍藏版）》请在三一文库上搜索。

1、第4章 树与二叉树,清华大学计算机系 殷人昆,数据结构课件,第四章 树与二叉树,层层叠叠 纵向展开 化复杂为简单的参天大树,202-2,树的定义与基本概念 二叉树 二叉树遍历 二叉树的计数 线索二叉树 树与树的遍历 树的应用,第 4 章 树与二叉树,202-3,树和森林的概念,树的定义 树是由n (n0) 个结点组成的有限集合： 有一个特定的称之为根(root)的结点； 除根以外的其它结点划分为 m (m0) 个 互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树。 此定义是离散数学和图论中给出的。它们把树视为图的一个极小连通子图。有 n 个结点的树有 n-1

2、条边，而且不能有回路。,202-4,这种观点的典型代表是 Knuth。他认为图至少有一个顶点，树也必须至少有一个顶点。树不能是空树，但 N 叉树可以是空树。N 叉树是限制根的子树最多不能超过 N 棵的树。 随着对树讨论的深入，人们放宽了对树结构的限制。若把树当作层次结构单独对待，树中允许结点个数为0。这样，树与N叉树就没有不可逾越的鸿沟了。 从面向对象观点，N叉树是树的特殊实现：树是父类，N叉树是子类。N叉树继承了树的特性，它还有自己增加的特性，例如,202-5,理论上树不可是空树，N叉树可以是空树； 树的子树可以有序，也可以不要求有序，而N叉树的子树必须有序。 N叉树的定义也是递归的，递归到

3、空树终止；树则递归到只有一个结点的子树。 树的子树棵数不限，而N叉树中根的子树最多N棵。 树可以区分为外向树和内向树，而N叉树一般是外向树，即边是有向的，从父指向子。 树可以用N叉树实现。二叉树、B树等又都是N叉树的特殊情形。,202-6,树的特点,树是分层结构，又是递归结构。每棵子树的根结点有且仅有一个直接前驱，但可以有 0 个或多个直接后继。,202-7,结点 结点的度 分支结点 叶结点,子女 双亲 兄弟 祖先,树的度 树深度 树高度 森林,子孙 结点层次 结点深度 结点高度,202-8,注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从根向下逐层计算的；结点的高度是从下

4、向上逐层计算的：叶结点的高度为1, 其他结点的高度是取它的所有子女结点最大高度加一。 树的深度与高度相等。 树的深度按离根最远的 叶结点算，树的高度按 根结点算，都是6。 叶结点也称为终端结点， 非叶结点也称为非终端 结点。,高度=4,深度=3,202-9,二叉树的五种不同形态,L,L,R,R,二叉树 (Binary Tree),二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 这个定义是递归的。,202-10,二叉树的性质,性质1 若二叉树的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1 个结

5、点。( i1) 证明用数学归纳法 i = 1时，根结点只有1个，21-1 = 20 =1； 若设 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 层，各层最多结点个数相加，得到等比级数，求和得： 20 + 21 + 22 + + 2h-1 = 2h-1 空树的高度为 0，只有根结点的树的高度为 1。,202-

6、12,性质3 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0n21 证明： 若设度为 1 的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1 引申：可用于判断二叉树各类结点个数。,202-13,定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为 h，则共有 h 层。除第 h 层外，其它各层 (

7、1h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,202-14,性质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-1,24-1,202-15,23-1,24-1,注意： 求高度的另一公式为 log2n +1, 此公式对于 n = 0 不适用。 若设完全二叉树中叶结点有 n0 个, 则该二叉树总的结点数为 n = 2n0, 或

8、 n = 2n0 1。 若完全二叉树的结点数为奇数，没有度为1的结点；为偶数，有一个度为1的结点。 右图为理想平衡树， 上层都是满的，第 h 层结点分布在各 处。,202-16,性质5 如将一棵有 n 个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号: 0, 1, 2, , n-1，则有以下关系： 若i = 0, 则 i 无双亲； 若i 0, 则 i 的双亲为(i-1)/2。 若2*i+1 n, 则 i 的左子女为 2*i+1； 若2*i+2 n, 则 i 的右子女为2*i+2。 若 i 为偶数, 且i != 0, 则 其左兄弟为i-1； 若 i 为奇数, 且i != n-1, 则其右

9、兄弟为i+1。,202-17,注意： 如果完全二叉树各层次结点从 1 开始编号：1, 2, 3, , n，则有以下关系： 若i = 1, 则 i 无双亲； 若i 1, 则 i 的双亲为i / 2。 若2*i = n, 则 i 的左子女为 2*i； 若2*i+1 = n, 则 i 的右子女为2*i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1； 若 i 为偶数, 且i != n, 则其右兄弟为i+1。,202-18,完全二叉树 一般二叉树 的顺序表示 的顺序表示,二叉树的顺序表示,202-19,极端情形: 只有右单支的二叉树,对于完全二叉树，因结点编号连续，数据存储密集，适于用顺序

10、表示； 对于一般二叉树，用链表表示较好；,202-20,lchild data rchild,data,lchild,rchild,左子女指针 右子女指针,二叉树的二叉链表表示,使用二叉链表，找子女的时间复杂度为O(1)，找双亲的时间复杂度为O(log2i)O(i)，其中，i 是该结点编号。,202-21,二叉树的三叉链表表示,使用三叉链表，找子女、双亲的时间都是O(1)。,202-22,二叉树 二叉链表 三叉链表,二叉树链表表示的示例,202-23,二叉树的定义,typedef char TElemType; /树结点数据类型 typedef struct node /树结点定义 TElem

11、Type data; /结点数据域 struct node *lchild, *rchild; /子女指针域 BiTNode; typedef BiTNode *BinTree; /树定义，代表树的根指针,202-24,二叉树遍历,树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设 访问根结点记作 V， 遍历根的左子树记作 L， 遍历根的右子树记作 R， 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,202-25,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点

12、(V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,中序遍历 (Inorder Traversal),-,-,/,+,*,a,b,c,d,e,f,202-26,二叉树递归的中序遍历算法,void InOrder ( BiTNode *T ) if ( T != NULL ) InOrder ( T-lchild ); visit ( T-data ); InOrder ( T-rchild ); visit()是输出数据值的操作，在实际使用时可用相应的操作来替换。,202-27,前序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 访问根结点 (V

13、)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,前序遍历 (Preorder Traversal),-,-,/,+,*,a,b,c,d,e,f,202-28,二叉树递归的前序遍历算法,void PreOrder (BiTNode *T) if (T != NULL) visit (T-data); PreOrder (T-lchild); PreOrder (T-rchild); 与中序遍历算法相比，visit() 操作放在两个子树递归前序遍历的最前面。,202-29,后序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则

14、后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / -,后序遍历 (Postorder Traversal),d,-,-,/,+,*,a,b,c,d,e,f,202-30,二叉树递归的后序遍历算法,void PostOrder (BiTNode *T) if (T != NULL) PostOrder (T-lchild); PostOrder (T-rchild); visit (T-data); 与中序遍历算法相比，visit() 操作放在两个子树递归前序遍历的最后面。,202-31,计算二叉树结点个数的递归算法,应用

15、二叉树遍历的事例,int Count (BiTNode *T) if (T = NULL) return 0; else return 1+ Count (T-lchild) + Count (T-rchild); 空二叉树的结点个数为 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) ?

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

17、a); if (p-rchild != NULL) Push(S, p-rchild); if (p-lchild != NULL) p = p-lchild; /进左子树 else Pop(S, p); /左子树空, 进右子树 ,202-35,a,b,c,d,e,b a,a,d a,a,左空,退栈 访问,左空,退栈 访问,退栈 访问,左空,e c,退栈访问,c,c,右空,退栈访问 栈空结束,利用栈的中序遍历的非递归算法,202-36,void InOrder(BinTree T) stack S; InitStack(S); /递归工作栈 BiTNode *p = T; /初始化 do wh

18、ile (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-37,后序遍历时使用的栈的结点定义 typedef struct BiTNode *ptr; /结点指针 enum tag L, R ; /该结点退栈标记 StackNode; 根结点的 tag = L，表示从左子树退

19、出, 访问右子树。 tag = R, 表示从右子树退出, 访问根。,利用栈的后序遍历的非递归算法,202-38,a,b,c,d,e,aL,bL aL,bR aL,dL bR aL,dR bR aL,bR aL,aL,aR,eL cL aR,eR cL aR,cL aR,cR aR,aR,202-39,利用栈的后序遍历的非递归算法,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

20、, w); p = p-lchild; int succ = 1; /继续循环标记,202-40,while (succ ,202-41,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,202-42,202-43,6,1,2,3,4,5,7,8,9,6,1,2,3,7,5,8,4,9,如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。 问题是：固定前序排列，选择所有可能的中序排列，可以构造出多少种不同的二叉树？,202-44,1,2,3,1,2,3,1,2,3,1,2,

21、3,1,2,3,例如, 有 3 个数据 1, 2, 3 ，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 123，132，213，231，321。 那么，如何推广到一般情形呢？首先，只有一个结点的不同二叉树只有一个；有 2 个结点的不同二叉树只有 2 种，其他情况呢？,202-45,b0 =1,b1 =1,b2 =2,b3 =5,b4 =14,有0个, 1个, 2个, 3个结点的不同二叉树如下,202-46,bi,bn-i-1,1,计算具有 n 个结点的不同二叉树的棵数,Catalan函数 例,202-47,线索二叉树 (Threaded Binary Tree),又称为

22、穿线树。 通过二叉树遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。 希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。 为此，在二叉树存储结点中增加线索信息。,202-48,线索 (Thread),增加前驱Pred指针和后继Succ指针的二叉树,202-49,这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。 改造树结点，将 pred 指针和 succ 指针压缩到 lchild 和 rchild 的空闲指针中，并增设两个标志 l

23、tag 和 rtag，指明指针是指示子女还是前驱后继。后者称为线索。 ltag (或rtag) = 0，表示相应指针指示左子女（或右子女结点）； ltag (或rtag) = 1, 表示相应指针为前驱（或后继）线索。,202-50,中序线索二叉树及其链表表示,202-51,typedef int TTElemType; typedef struct node int ltag, rtag; struct node *lchild, *rchild; TTElemType data; ThreadNode, *ThreadTree; 注意，线索二叉树在树结点中增加了ltag和rtag，改变了二叉

24、树的结构。,线索二叉树的结构定义,202-52,通过中序遍历建立中序线索二叉树,void InThread (ThreadNode *t, ThreadNode * /建立当前结点 t 的前驱线索,202-53,if ( pre /递归, 右子树线索化 使用此函数可以把以 t 为根的子树一次中序线索化，但中序下最后一个结点的后继线索没有加上，指针 pre 在退出时正在指示这一结点。,202-54,void CreateInThread (ThreadTree T) ThreadNode *pre = NULL; /前驱指针 if ( T != NULL ) /树非空, 线索化 InThread

25、 (T, pre);/中序遍历线索二叉树 pre-rchild = NULL; pre-rtag = 1; /后处理, 中序最后一个结点 通过该主程序实现了对二叉树的中序线索化。它是基于二叉树的中序遍历实现的。,202-55,202-56,202-57,202-58,202-59,202-60,202-61,202-62,寻找结点 p 在中序下的后继,if (p-rtag =1) 后继为 p-rchild else /p-rtag != 1 后继为结点 p 右子树 q 中的中序下的第一 个结点,202-63,ThreadNode * First ( ThreadNode *t ) /函数返回以

26、 *t 为根的线索二叉树中的中序序列下 /的第一个结点 ThreadNode *p = t; while ( p-ltag = 0 ) p = p-lchild; return 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 ( Th

27、readNode * t ) /以 t 为根的线索二叉树的中序遍历 ThreadNode * p; for ( p = First (t); p != NULL; p = Next (p) ) cout data endl; ,202-65,寻找结点 p 在中序下的前驱,if (p-ltag=1) 前驱为 p-lchild else /p-leftThread=0 前驱为结点 p 左子树 中序下的最后一个结 点,202-66,前序线索二叉树,在前序线索二叉树中寻找当前结点的后继,202-67,后序序列 D B E C A,后序线索二叉树,在后序线索二 叉树中寻找当 前结点的后继,202-68,

28、树的存储表示 双亲表示 为了操作实现的方便，有时会规定结点的存放顺序。例如，可以按树的前序次序存放树中的各个结点，或按树的层次次序安排所有结点。,树与树的遍历,202-69,子女链表表示,无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。,202-70,子女指针表示,一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。 为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。 这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。,202-71,等数量的链域

29、,空链域2n+1个,202-72,子女-兄弟表示,也称为树的二叉树表示。结点构造为： firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。 nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。 若想找某结点的所有子女，可先找firstChild,再反复用 nextSibling 沿链扫描。,202-73,树的左子女 - 右兄弟表示,202-74,左子女-右兄弟表示的树的结构定义,typedef int TElemType; typedef struct node TElemType data; struct node *fchi

30、ld, *nsibling; CSNode, *CSTree; 注意，虽然此定义与二叉树的类似，操作也类似，但语义是不同的。 树结构是递归的，可用递归函数实现相应操作。,202-75,寻找双亲 子女 兄弟的操作,TreeNode *FindParent ( CSNode *T, CSNode *p ) /在以 T 为根的树中找结点 p 的双亲 if (T = NULL | p = NULL) return NULL; CSNode *q = T-fchild, *s; while (q != NULL ,202-76,if (q != NULL TreeNode * FindnextSibli

31、ng ( CSNode *p ) /在树中找结点 p 的兄弟,202-77,if ( p != NULL ) return p-nsibling; else return NULL; 深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历,树的遍历,二叉树表示,202-78,当树非空时 访问根结点 依次先根遍历根的各棵子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现,树的先根次序遍历,202-79,树的先根次序遍历的递归算法,void PreOrder ( CSNode

32、 *t ) /以指针 t 为根, 先根次序遍历 if ( t != NULL ) visit ( t-data ); /访问根结点 CSNode *p = t-fchild; /第一棵子树 while ( p != NULL ) PreOrder (p); /递归先根遍历子树 p = p-nsibling; ,202-80,当树非空时 依次后根遍历根的各棵子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现,树的后根次序遍历,202-81,树的后根次序遍历的递归

33、算法,void PostOrder ( CSNode *t ) /以指针 t 为根, 按后根次序遍历树 if ( t != NULL ) CSNode *p = t-fchild; while ( p != NULL ) PostOrder ( p ); p = p-nsibling; visit ( t-data ); /最后访问根结点 ,202-82,按广度优先次序遍历树的结果 ABCDEFG 广度优先遍历算法 void LevelOrder ( CSTree T ) /分层遍历树，算法用到一个队列 Queue Q; InitQueue(Q); CSNode *p; if ( T != N

34、ULL ) /树不空 EnQueue(Q, T); /根结点进队列,广度优先(层次次序)遍历,202-83,while ( ! QueueEmpty(Q) ) DeQueue(Q, p); visit(p-data); /队列中取一个并访问之 p = p-fchild; /待访问结点的子女结点进队列 while ( p != NULL ) EnQueue ( Q, p ); p = p-nsibling; ,202-84,森林与二叉树的转换,将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。 森林与二叉树表示的转换可以借助树的二叉树表示来实现。,202-85,A,F,H,T1 T2

35、 T3,A,B,C,D,G,I,J,E,K,F,B,C,D,E,G,H,I,K,J,A,B,C,E,D,H,I,K,J,F,G,3 棵树的森林,各棵树的二叉树表示,森林的二叉树表示,202-86,森林转化成二叉树的规则,若 F 为空，即 n = 0，则对应的二叉树 B 为空树。 若 F 不空，则 二叉树 B 的根是 F 第一棵树 T1 的根； 其左子树为 B (T11, T12, , T1m )，其中，T11, T12, , T1m 是 T1 的根的子树； 其右子树为 B (T2, T3, , Tn )，其中，T2, T3, , Tn 是除 T1 外其它树构成的森林。,202-87,二叉树转换

36、为森林的规则,如果 B 为空，则对应的森林 F 也为空。 如果 B 非空，则 F 中第一棵树 T1 的根为 B 的根； T1 的根的子树森林 T11, T12, , T1m 是由 B 的根的左子树 LB 转换而来； F 中除了 T1 之外其余的树组成的森林 T2, T3, , Tn 是由 B 的根的右子树 RB 转换而成的森林。,202-88,例题,设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为 m1，m2 和 m3。那么在由该森林转化成的二叉树中根结点的右子树上有（ ）个结点。 A. m1+m2 B. m2+m3 C. m3+m1 D. m1+m2+m3 【解答】在由森林转化成的二

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

38、的根的子树森林T11, , T1k； 先根遍历森林中除第一棵树外其他树组成的森林T2, .,Tm。 注意， 是一个循环，对于每一个T1i，执行树的先根次序遍历； 是一个递归过程，重新执行 T2 为第一棵树的森林的先根次序遍历。,森林的先根次序遍历,202-91,森林的先根次序遍历的结果序列 ABCDE FG HIKJ 这相当于对应二叉树的前序遍历结果。,202-92,森林的中根次序遍历,若森林 F = ，返回；否则 中根遍历森林 F 第一棵树的根结点的子树森林T11, , T1k； 访问森林的根结点 r1； 中根遍历森林中除第一棵树外其他树组成的森林T2, ., Tm。 注意，与先根次序遍历相

39、比，访问根结点的时机不同。所以在的情形，对以T2为第一棵树的森林遍历时，重复执行的操作。,202-93,森林的中根次序遍历的结果序列 BCEDA GF KIJH 这相当于对应二叉树中序遍历的结果。,202-94,广度优先遍历（层次序遍历）,AFH BCDGIJ EK,A,B,C,E,D,H,I,K,J,F,G,若森林 F 为空，返回； 否则 依次遍历各棵树的 根结点； 依次遍历各棵树根 结点的所有子女； 依次遍历这些子女 结点的子女结点； ,202-95,树的应用,二叉排序树 平衡二叉树 Huffman树 堆 并查集,202-96,二叉排序树 ( Binary Search Tree ),定义

40、 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相同。 左子树（如果非空）上所有结点的关键字都小于根结点的关键字。 右子树（如果非空）上所有结点的关键字都大于根结点的关键字。 左子树和右子树也是二叉排序树。,202-97,二叉排序树例,结点左子树上所有关键 字小于结点关键字； 结点右子树上所有关键 字大于结点关键字； 如果对一棵二叉排序树 进行中序遍历，可以按 从小到大的顺序将各结 点关键字排列起来。 注意，国外教材统称为二叉搜索树或二叉查找树。,202-98,例题,一棵二叉树是二叉排序树的（ ）条件是树中任一结点的

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

42、排序树。,202-100,二叉排序树的结构定义,typedef char BSTElemType;/树结点数据类型 typedef struct node /二叉排序树结点 BSTElemType data; struct node *lchild, *rchild; BSTNode, *BSTree;/二叉排序树定义 从面向对象观点来看，二叉排序树是二叉树的特殊情形，它继承了二叉树的结构，增加了自己的特性，对数据的存放增加了约束。,202-101,二叉排序树上的查找,查找45 查找成功,查找28 查找失败,在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它

43、可以是一个递归的过程。,202-102,假设想要在二叉排序树中查找关键字为x的元素，查找过程从根结点开始。 如果根指针为NULL，则查找不成功；否则用给定值 x 与根结点的关键字进行比较： 如果给定值等于根结点的关键字值，则查找成功。 如果给定值小于根结点的关键字值，则继续递归查找根结点的左子树； 否则。递归查找根结点的右子树。 查找成功时检测指针停留在树中某个结点。,202-103,可用判定树描述查找过程。内结点是树中原有结点，外结点是失败结点，代表树中没有的数据。 查找不成功时检测指针停留在某个失败结点。,查找22,查找45,202-104,二叉排序树的查找算法,void Find ( B

44、STNode * t, BSTElemType x, BSTNode *,202-105, 查找的关键字比较次数最多不超过树的高度。 每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。 为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。,二叉排序树的插入,202-106,为此，在插入之前先使用查找算法在树中检查要插入元素有还是没有。 查找成功：树中已有 这个元素,不再插入。 查找不成功：树中原 来没有关键字等于给 定值的结点，把新元 素加到查找操作停止 的地方。,202-107,void Insert ( BSTNode * ,202-108,输入

45、数据，建立二叉排序树的过程,输入数据 53, 78, 65, 17, 87, 09, 81, 15 ,202-109,同样 3 个数据 1, 2, 3 ，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。 如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最大。 2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1,202-110,二叉排序树的删除,在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。 为保证在删除后树的查找性能不至于降低，还需要防止重新链接后树的高度增加。 被删结点的右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。 被删结点的左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。 被删结点的左、右子树都不为空，可以在它,202-111,的右子树中寻找中序下的第一个结点(所有比被删关键字大的关键字中它的值最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。当然，也可以到它的左子树中寻找中序下的最后一个结点。,右子树空, 用 左子女顶替,202-112,左子树空, 用右子女顶替,在右子树上找中序下第一个结点填补,202-113,二叉排序树性能分析,对于有 n 个关键字的集合，其关键字