第五和六章二叉树和树.pps

《第五和六章二叉树和树.pps》由会员分享，可在线阅读，更多相关《第五和六章二叉树和树.pps（211页珍藏版）》请在三一文库上搜索。

1、1,二叉树的逻辑结构与存储结构 二叉树查找树 堆与优先队 哈夫曼树 树的逻辑结构与存储结构 K叉树,第3部分 二叉树和树,本章的主要内容是,2,树T：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点； 当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2, ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。,5.1 树的基本概念,树的固有特性-树的定义是采用递归方法,树的定义,3,(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构,5.1 树的基本概念,树的逻辑表示,1. 结点和结点间的连线表示

2、法,1=B,D,E,F,H,I 2=C,G,4,.文式图表示法-集合嵌套,3.凹式表示法-层次表表示,5.1 树的基本概念,5,树的应用举例文件结构,5.1 树的基本概念,6,树的基本概念,结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。,5.1 树的基本概念,树的相关术语,7,叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点，或 内部结点。,5.1 树的基本概念,8,孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结 点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 堂兄弟：双亲在同一层的孩子结点互称

3、为堂兄弟。,5.1 树的基本概念,9,路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1, n2, , nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,5.1 树的基本概念,10,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那 么x就称为y的祖先，而y称为x的子孙。,5.1 树的基本概念,结点为n的树，必然有n-1条边。,11,结点的深度：结点所在层数,根结点的层数为0；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数+1，也称高度。,5.1 树的基本概念,国内大部分

4、教材设为1,12,层序编号：将树中结点按照从上层到下层、同层从左到右的次 序依次给他们编以从1开始的连续自然数。,5.1 树的基本概念,13,有序树、无序树：如果一棵树中结点的各子树从左到右是有 次序的，称这棵树为有序树；反之，称为 无序树。,数据结构中讨论的一般都是有序树,5.1 树的基本概念,14,森林：m (m0)棵互不相交的树的集合。,5.1 树的基本概念,F=(T1,T2,.Tm),15,同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。,5.1 树的基本概念,16,树结构和线性结构的比较,线性结构,树结构,无前

5、驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,5.1 树的基本概念,17,二叉树的定义,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.2 二叉树的逻辑结构,二叉树的定义及主要特性,（1）二叉树的定义,18,（2）二叉树的特点,每个结点最多有两棵子树； 二叉树是有序的，其次序不能 任意颠倒。,5.2 二叉树的逻辑结构,19,（3）二叉树的基本形态,5.2 二叉树的逻辑结构,20,例:具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。

6、,树,二叉树,5.2 二叉树的逻辑结构,21,特殊的二叉树,(1)斜树 1 .所有结点都只有左子树的二叉树称为左斜树； 2 .所有结点都只有右子树的二叉树称为右斜树； 3.左斜树和右斜树统称为斜树。,1. 在斜树中，每一层只有一个结点； 2.斜树的结点个数与其深度相同。, 斜树的特点：,5.2 二叉树的逻辑结构,22,(2)满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树, 满二叉树的特点：,只有度为0和度为2的结点。,5.2 二叉树的逻辑结构,23,(3)完全二叉树 从根结点起每一层从左至右填充。一棵高度为d的完全二叉树除了d-1层以外，每一层都是满的，且底曾叶结点集中在左边的

7、若干位置上。,5.2 二叉树的逻辑结构,24,1. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。, 完全二叉树的特点：,5.2 二叉树的逻辑结构,25,(4)国内大部分教材定义 满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树 所有叶子都在同一层上, 满二叉树的特点：,叶子只能出现在最下一层； 只有度为0和度为2的结点。,5.2 二叉树的逻辑结构,26,不是完全二叉树,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一

8、棵完全二叉树。,需要注意的是：满二叉树与完全二叉树之间并没有任何特别关系。,5.2 二叉树的逻辑结构,27,按照上述（第二种）定义,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多,5.2 二叉树的逻辑结构,28,对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,按照上述（第二种）定义,5.2 二叉树的逻辑结构,29,二叉树的基本性质,性质5-1 二叉树的第i层上最多有2i-1个结点（i1）。,证明：当i=1时，

9、第1层只有一个根结点，而 2i-1=20 =1，结论显然成立。 假定i=k（1ki）时结论成立，即第k层上至多有2k-1个结点， 则 i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即22k-12k。结论成立。,5.2 二叉树的逻辑结构,30,性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,证明：由性质1可知，深度为k的二叉树中结点个数最多 = =2k-1； 每一层至少要有一个结点，因此深度为k的二叉树， 至少有k个结点。,5.2 二叉树的逻辑结构,31,性质5-

10、3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0n21。,证明: 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有： nn12n21 因此可以得到：n0n21 。,5.2 二叉树的逻辑结构,32,在有n个结点的满二叉树中，有多少个叶子结点？,5.2 二叉树的逻辑结构,33,性质5-4 具有n个结点的完全二叉树的深度为 log2n +1。,证明：假设具有n个结点的完全二叉树

11、的深度为k， 根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,5.2 二叉树的逻辑结构,34,证明(续)：,5.2 二叉树的逻辑结构,35,性质5-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点（简称为结点i），有： (1)如果i1，则结点i的双亲结点的序号为 i/2； 如果i1，则结点i是根结点，无双亲结点。 (2)如果2in，则结点i的左孩子的序号为2i； 如果2in，则结点i无左孩子。 (3)如果2i1n，则结点i的右孩子的序号为2i1； 如果2i1n，则结点 i无右孩子。,5.2 二叉树的逻辑结构,36,对一棵具有n个结点的完

12、全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2； 结点i的左孩子为2i； 结点i的右孩子为2i1。,性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,5.2 二叉树的逻辑结构,37,二叉树的抽象数据类型,ADT BiTree Data 由一个根结点和两棵互不相交的左右子树构成， 结点具有相同数据类型及层次关系 Operation InitBiTree 前置条件：无 输入：无 功能：初始化一棵二叉树 输出：无 后置条件：构造一个空的二叉树,5.2 二叉树的逻辑结构,38,DestroyBiTree 前置条件：二叉树已存在 输入：无 功能：销毁一棵二叉树 输出：无

13、 后置条件：释放二叉树占用的存储空间 InsertL 前置条件：二叉树已存在 输入：数据值x，指针parent 功能：将数据域为x的结点插入到二叉树中，作为结点parent的左孩子。如果结点parent原来有左孩子，则将结点parent原来的左孩子作为结点x的左孩子 输出：无 后置条件：如果插入成功，得到一个新的二叉树,5.2 二叉树的逻辑结构,39,DeleteL 前置条件：二叉树已存在 输入：指针parent 功能：在二叉树中删除结点parent的左子树 输出：无 后置条件：如果删除成功，得到一个新的二叉树 Search 前置条件：二叉树已存在 输入：数据值x 功能：在二叉树中查找数据元素

14、x 输出：指向该元素结点的指针 后置条件：二叉树不变,5.2 二叉树的逻辑结构,40,PreOrder 前置条件：二叉树已存在 输入：无 功能：前序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 InOrder 前置条件：二叉树已存在 输入：无 功能：中序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变,5.2 二叉树的逻辑结构,41,PostOrder 前置条件：二叉树已存在 输入：无 功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列 后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在 输入：无 功能：层序遍历二叉树 输出：二叉树中

15、结点的一个线性排列 后置条件：二叉树不变 endADT,5.2 二叉树的逻辑结构,42,/ Binary tree node abstract class template class BinNode public: virtual Elem,二叉树结点ADT的实现,5.2 二叉树的逻辑结构,P93,43,二叉树的遍历操作,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,5.2 二叉树的逻辑结构,44,二叉树的遍历方式： DLR、LDR、LRD、 DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种：

16、 前序：DLR 中序：LDR 后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,5.2 二叉树的逻辑结构,考虑二叉树的组成：,45,(1)前序（根）遍历 若二叉树为空，则空操作返回；否则： 访问根结点； 前序遍历根结点的左子树； 前序遍历根结点的右子树。,5.2 二叉树的逻辑结构,前序遍历序列：A B D G C E F,46,(2)中序（根）遍历 若二叉树为空，则空操作返回；否则： 中序遍历根结点的左子树； 访问根结点； 中序遍历根结点的右子树。,5.2 二叉树的逻辑结构,中序遍历序列：D G B A E C F,47,(3)后序（根）遍历 若二叉树为空，则空操作返回；否则： 后

17、序遍历根结点的左子树； 后序遍历根结点的右子树。 访问根结点；,5.2 二叉树的逻辑结构,后序遍历序列：G D B E F C A,48,(4)层序遍历 二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,5.2 二叉树的逻辑结构,层序遍历序列：A B C D E F G,49,(1)前序遍历的实现 方法1 Template void PreOrder(BinNode* subroot) if (subroot = NULL) return; visit(subroot); PreOrder(subroot-left(); P

18、reOrder(subroot-right(); ,5.2 二叉树的逻辑结构,二叉树遍历操作 C+语言的实现,P94,50,前序遍历算法的执行轨迹,前序遍历序列：A B D G C E F,5.2 二叉树的逻辑结构,51,方法2 template void preorder2(BinNode* subroot) visit(subroot); if (subroot-left() != NULL) preorder2(subroot-left(); if (subroot-right() != NULL) preorder2(subroot-right(); ,5.2 二叉树的逻辑结构,前序遍

19、历序列：A B D G C E F,P94,52,二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。 解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。,在前序遍历中，设要遍历二叉树的根指针为root，则有两种可能： 若root!=NULL，则表明？如何处理？ 若root=NULL，则表明？如何处理？, 非递归算法,5.2 二叉树的逻辑结构,53,访问结点序列:,A,栈S内容:,B,D,A,B,前序遍历的非递归实现,A,D,B,C,5.2 二叉树的逻辑结构,54,访问结点序列:,A,栈S内容:,B,D,A

20、,前序遍历的非递归实现,A,D,B,C,D,5.2 二叉树的逻辑结构,55,访问结点序列:,A,栈S内容:,B,D,C,前序遍历的非递归实现,A,D,B,C,C,5.2 二叉树的逻辑结构,56,1.栈s初始化； 2.循环直到root为空且栈s为空 2.1 当root不空时循环 2.1.1 输出root-data; 2.1.2 将指针root的值保存到栈中； 2.1.3 继续遍历root的左子树 2.2 如果栈s不空，则 2.2.1 将栈顶元素弹出至root； 2.2.2 准备遍历root的右子树；,伪代码描述,5.2 二叉树的逻辑结构,57,template void PreOrder(Bin

21、Node * subroot) top= -1; /采用顺序栈，并假定不会发生上溢 while (subroot!=NULL | | top!= -1) while (subroot!= NULL) coutdata; s+top= subroot; subroot = subroot -lchild; if (top!= -1) subroot =stop-; subroot = subroot -rchild; ,5.2 二叉树的逻辑结构,58,(2)中序遍历的实现 template void InOrder(BinNode* subroot) if(subroot = NULL) ret

22、urn; InOrder(subroot-left(); visit(subroot); InOrder(subroot-right(); ,课堂练习,中序遍历序列：D G B A E C F,59,(3)后序遍历的实现 template void PostOrder(BinNode* subroot) if(subroot = NULL) return; PostOrder(subroot-left(); PostOrder(subroot-right(); visit(subroot); ,后序遍历序列：G D B E F C A,课堂练习,60,课堂练习,遍历二叉树是二叉树各种操作的基础

23、 适当修改访问操作的内容，可以派生出很多关于二叉树的 应用算法。,void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); ,61,课堂练习,设计算法求二叉树的结点个数。 P95,Template int count(BinNode *subroot) if (subroot) Count(subroot-left(); n+; /n为全局量并已初始化为0 Count(subroot-right(); ,62,课堂练习,设计算法按前序

24、次序打印二叉树中的叶子结点。,void PreOrder(BiNode *root) if (root) if (!subroot-lchild ,63,课堂练习,设计算法求二叉树的深度。,int Depth(BiNode *root) if (root= =NULL) return 0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; ,64,课堂练习,设计算法求树中结点 x 的第 i 个孩子。,template TNode *Search(TNode *root, T x, int i)

25、 if (root-data= =x) j=1; p=root-firstchild; while (p!=NULL ,template struct TNode T data; TNode *firstchild, *rightsib; ;,65,5.2 二叉树的逻辑结构,若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？,例：已知前序序列为ABC，则可能的二叉树有5种。,66,5.2 二叉树的逻辑结构,例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。,若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？,67,若已知一棵

26、二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？,例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?,5.2 二叉树的逻辑结构,68,1. 根据前序序列的第一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在前序序列中确定左右子树的前序序列； 4. 由左子树的前序序列和中序序列建立左子树； 5. 由右子树的前序序列和中序序列建立右子树。,5.2 二叉树的逻辑结构,构造该二叉树的过程如下：,69,前序：A B C D E F G H I中序：B C A E D G H F

27、I,前序：B C 中序：B C,5.2 二叉树的逻辑结构,前序： D E F G H I 中序： E D G H F I,70,前序：F G H I 中序：G H F I,5.2 二叉树的逻辑结构,前序： D E F G H I 中序： E D G H F I,71,已知一棵二叉树的后序遍历序列和中序遍历序列分别为ABFHGDEC 和ABCEFGHD，请构造该二叉树。,课堂练习,72,二叉树的链式存储结构就是用指针体现结点之间的逻辑关系父子关系。,5.3 二叉树的存储结构及实现,链式存储结构,二叉链表,三叉链表,一叉链表,结点的存储结构,找父亲容易，找儿子难,73,5.3 二叉树的存储结构及实

28、现,二叉链表,具有n个结点的二叉链表中，有多少个空指针？,用指针实现的二叉树的结构图,74,二叉链表结点类的声明,5.3 二叉树的存储结构及实现,template class BinNodePtr : public BinNode private: Elem it; BinNodePtr* lc； BinNodePtr* rc； public: BinNodePtr() lc = rc = NULL; BinNodePtr(Elem e, BinNodePtr* l =NULL, BinNodePtr* r =NULL) it = e; lc = l; rc = r; ,75,Elem,二叉链

29、表结点类的声明,5.3 二叉树的存储结构及实现,76,若叶结点和分支结点分别存储不同类型的数据,5.3 二叉树的存储结构及实现,可采用联合结构实现(P97)-共用空间，但如果两种类型长度差别过大，就会使其变得低效。,77,分支与叶结点的不同表示,5.3 二叉树的存储结构及实现,class VarBinNode public: virtual bool isLeaf() = 0; class LeafNode : public VarBinNode private: Operand var; public: LeafNode(const Operand,使用C+的类继承和虚函数来实现，方法1 P

30、98,78,分支与叶结点的不同表示,5.3 二叉树的存储结构及实现,class IntlNode : public VarBinNode private: VarBinNode* left; VarBinNode* right; Operator opx; public: IntlNode(const Operator,79,void traverse(VarBinNode *subroot) if (subroot = NULL) return； if (subroot-isLeaf() cout value; else cout value(); traverse(IntlNode *)

31、subroot)-leftchild(); traverse(IntlNode *) subroot)-rightchild(); ,分支与叶结点的不同表示,5.3 二叉树的存储结构及实现,80,class VarBinNode public: virtual bool isLeaf() = 0; virtual void trav() = 0; ; class LeafNode:public VarBinNode private: Operand var; public: LeafNode(const Operand,使用C+的类继承和虚函数来实现，方法2 P100,分支与叶结点的不同表示,

32、5.3 二叉树的存储结构及实现,81,class IntlNode : public VarBinNode private: VarBinNode* lc; VarBinNode* rc; Operator opx; public: IntlNode(const Operator ,5.3 二叉树的存储结构及实现,分支与叶结点的不同表示,82,void trav() cout trav(); if (right() != NULL) right()-trav(); ; void traverse(VarBinNode *root) if (root != NULL) root-trav();

33、,5.3 二叉树的存储结构及实现,分支与叶结点的不同表示,83,建立二叉树,即建立二叉链表,为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，如“#”，用以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。,5.3 二叉树的存储结构及实现,如何由一种遍历序列生成该二叉树？,遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。,84,扩展二叉树的前序遍历序列: A B # D # # C # #,5.3 二叉树的存储结构及实现,例 前序建立二叉树的存储结构,85,template BinTree :BinTree(BiNode *s

34、ubroot) creat(subroot)； void BinTree :creat(BiNode *subroot) cinch; if (ch=# ) subroot=NULL; else subroot=new BinNode; subroot-data=ch; creat(root-lchild); creat(root-rchild); ,建立二叉递归算法,5.3 二叉树的存储结构及实现,86,5.3 二叉树的存储结构及实现,二叉树实现的结构性开销,自学 P99-101,87,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系

35、父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系 。,5.3 二叉树的存储结构及实现,顺序存储结构,88,完全二叉树的顺序存储,5.3 二叉树的存储结构及实现,以编号 为下标,89,Parent(r) = (r-1)/2 if r 0 and r 0, and r n. Rightsibling(r) = r + 1 if r is odd and r + 1 n.,5.3 二叉树的存储结构及实现,90,二叉树的顺序存储,5.3 二叉树的存储结构及实现,以编号 为下标,按照完全 二叉树编号,91,一棵斜树的顺序存储会怎样

36、呢？,深度为k的右斜树，k个结点需分配2k1个存储单元。,一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。,5.3 二叉树的存储结构及实现,二叉树的顺序存储结构一般仅存储完全二叉树,92,二叉查找树的定义,二叉查找树（也称二叉排序树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于根结点的值； 它的左右子树也都是二叉排序树。,二叉排序树的定义采用的是递归方法。,5.4 二叉查找树 BST,93,二叉排序树 非二叉排序树,中序遍历二叉排序树可以得到一个按关键码有

37、序的序列,5.4 二叉查找树 BST,94,二叉查找树的存储结构,以二叉链表形式存储，类声明如下：,/ BST implementation for the Dictionary ADT template class BST:public Dictionary private: BinNode* root; int nodecount; void clearhelp(BinNode*);,5.4 二叉查找树 BST,95,BinNode*inserthelp(BinNode*, const Elem,5.4 二叉查找树 BST,（续）,96,public: BST() root = NULL;

38、 nodecount = 0; BST() clearhelp(root); void clear() clearhelp(root); root = NULL;nodecount = 0; bool insert(const Elem ,5.4 二叉查找树 BST,（续）,97,bool removeAny(Elem ,5.4 二叉查找树 BST,（续）,98,二叉排序树的查找功能,在二叉排序树中查找给定值k, 若root是空树，则查找失败； 若kroot-data，则查找成功；否则 若kroot-data，则在root的左子树上查找；否则 在root的右子树上查找。 上述过程一直持续到k被

39、找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。 二叉排序树的查找效率在于只需查找二个子树之一。,5.4 二叉查找树 BST,99,例：在二叉排序树中查找关键字值为35，95的过程：,50,30,20,80,90,85,88,40,35,32,50,30,20,80,90,85,88,40,35,32,5.4 二叉查找树 BST,100,template bool BST: findhelp(BinNode* subroot, const Key ,P104,二叉排序树的查找算法实现,5.4 二叉查找树 BST,101,课堂练习,用迭代法实现二叉查找树的查找算法,102,二叉排序树

40、的查找性能分析,由序列3, 1, 2, 5, 4得到二叉排序树：,由序列1, 2, 3, 4, 5得到二叉排序树：,ASL =（1+2+3+4+5）/ 5= 3,ASL =（1+2+3+2+3）/ 5 = 2.2,通常情况下，二叉查找树的查找性能： 树的高度越小越好,5.4 二叉查找树 BST,103,例：插入值为98的结点,63,55,90,58,70,55,63,root,90,58,70,root,二叉查找树的插入,5.4 二叉查找树 BST,104,（1）若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。 （2）为插入新的

41、叶结点，首先要完成在该树中查找这个元素的操作。 查找失败，则将新结点插入在失败处； 查找成功，如果允许有相同的值存在，则将其插 入在 子树中。 （3）每次插入一个新结点，不需要移动其他结点，只要修改相应结点中的一个空指针即可。,5.4 二叉查找树 BST,二叉排序树的插入算法,右,105,template BinNode* BST: inserthelp(BinNode* subroot, const Elem ,二叉排序树的插入算法实现,5.4 二叉查找树 BST,106,template BinNode* BST: inserthelp(BinNode* subroot, const El

42、em ,二叉排序树的插入算法实现,5.4 二叉查找树 BST,如果不允许有相同的值存在呢？,107,构造一颗二叉查找树的过程是,例：关键码集合为 63，90，70，55，58， 二叉排序树的构造过程为：,63,从空的二叉查找树开始,依次插入查找集合中的每个元素的过程,5.4 二叉查找树 BST,108,二叉排序树的删除,在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。,分三种情况讨论： 被删除的结点是叶子； 被删除的结点或只有左子树，或者只有右子树； 被删除的结点既有左子树，也有右子树。,5.4 二叉查找树 BST,109,情况1被删除的结点是叶子结点-没有子结点,操作：将双亲结点中

43、相应指针域的值改为指向空。,5.4 二叉查找树 BST,110,操作：将双亲结点中相应指针域的值改为空。,5.4 二叉查找树 BST,111,情况2被删除的结点只有左子树或者只有右子树,操作：将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。,50,30,20,80,90,85,88,40,35,32,50,30,20,90,85,88,40,35,32,5.4 二叉查找树 BST,112,情况3被删除的结点既有左子树也有右子树,操作：或以其左子树中的最大值替代之，然后再删除该前驱结点。,50,30,20,80,90,85,88,40,35,32,40,30,20,80,90,85

44、,88,35,32,5.4 二叉查找树 BST,113,操作：或以其右子树中的最小值替代之，然后再删除该后继结点。,50,30,20,80,90,85,88,40,35,32,80,30,20,90,85,88,40,35,32,5.4 二叉查找树 BST,114,5.4 二叉查找树 BST,115,Remove Minimum Value,template BinNode* BST: deletemin(BinNode* subroot, BinNode* ,5.4 二叉查找树 BST,P105,116,二叉排序树的删除算法伪代码,5.4 二叉查找树 BST,1. 在二叉树中，查找结点p；

45、2. 如果查找成功，则： （1）若结点p只有右子树，则只需重接p的右子树； 若结点p只有左子树， 则只需重接p的左子树； （2）若结点p的左右子树均不空， 查找结点p的右子树上的 最左下结点s及其双亲结 点par；,117,5.4 二叉查找树 BST,（2）若结点p的左右子树均不空， 查找结点p的右子树上的最左下结点s 及其双亲结点par； 将结点s数据域替换到被删结点p的数据域； 若结点p的右孩子无左子树， 则将s的右子树接到par的右 子树上；否则，将s的右子 树接到结点par的左子树上； 删除结点s；,118,Remove,template BinNode* BST: removehel

46、p(BinNode* subroot, const Key,5.4 二叉查找树 BST,119,else BinNode* temp; t = subroot; if (subroot-left() = NULL) subroot = subroot-right(); else if (subroot-right() = NULL) subroot = subroot-left(); else / Both children are non-empty subroot-setRight( deletemin(subroot-right(), temp); Elem te = subroot-v

47、al(); subroot-setVal(temp-val(); temp-setVal(te); t = temp; return subroot; ,120,5.4 二叉查找树 BST,Cost of BST Operations,尽量保持二叉树平衡,即使其高度尽可能小,Find,insert,delete，最差情况？,等于该树的深度,如何解决？,如果二叉排序树是平衡的，则有n个结点的二叉树高度为log2n；如果二叉排序树完全不平衡（成一个链表），则有n个结点的二叉树高度为n。,121,二叉排序树的查找、插入和删除性能 取决于二叉排序树的形状，每次操作 平均情况 O(log2n) 最坏情况 O(n ) 设按照逐个插入的方式， 构建一棵有n个