算法二叉排序树PPT学习教案

1、会计学1 算法二叉排序树算法二叉排序树 动态查找的特点是，表结构本身是在查动态查找的特点是，表结构本身是在查 找过程中动态生成的，即对给定关键字值找过程中动态生成的，即对给定关键字值key ，表中有具有此值的记录，则查找成功返回，表中有具有此值的记录，则查找成功返回， 否则插入此关键字的新记录。否则插入此关键字的新记录。 第1页/共26页 7/20/2021 ADT DynamicSearchTable ADT DynamicSearchTable 数据对象数据对象D D：具有相同特性的数据元素的集合。每个数据元素含具有相同特性的数据元素的集合。每个数据元素含 有类型相同的关键字，可唯一标识数

2、据元素。有类型相同的关键字，可唯一标识数据元素。 数据关系数据关系R R：数据元素同属一个集合。数据元素同属一个集合。 基本操作基本操作: : InitDSTable( /InitDSTable( /构造一个空的动态查构造一个空的动态查 找表找表DTDT DestroyDStable( / DestroyDStable( / 销毁查找表销毁查找表DTDT。 SearchDSTable(DT,key); /SearchDSTable(DT,key); /查找具有关键字查找具有关键字key key 的元的元 素。素。 InsertDSTable( /InsertDSTable( /插入新记录。插入

3、新记录。 DeleteDSTable(/DeleteDSTable(/删除记录。删除记录。 TraverseDSTable(DT,visit(); /TraverseDSTable(DT,visit(); /遍历查找表。遍历查找表。 ADT DynamicSearchTable ADT DynamicSearchTable 动态查找表的抽象数据类型动态查找表的抽象数据类型 第2页/共26页 1.1.二叉排序树的定义二叉排序树的定义 第3页/共26页 7/20/2021 不是二叉排序树不是二叉排序树 50 30 80 20 90 10 85 40 35 25 23 88 66 二叉排序树的例子二

4、叉排序树的例子 第4页/共26页 7/20/2021 typedef struct BiTNode / 结点结构结点结构 struct BiTNode *lchild, *rchild; ElemType data; BiTNode, *BiTree; 3.3.二叉排序树的查找二叉排序树的查找 算法思想：算法思想： (1) p指向根；指向根； (2) p的关键字与的关键字与key比较，有三种情况：比较，有三种情况： p-data.key=key; 查找成功，返回查找成功，返回p, 结束；结束； p-data.keykey; 到左子树中找，到左子树中找，p指向它左子女；指向它左子女； p-dat

5、a.keykey; 到右子树中找，到右子树中找， p指向它右子女；指向它右子女； (3) 重复重复(2)直到直到p为空，查找失败，返回空；为空，查找失败，返回空； 第5页/共26页 7/20/2021 从空树出发，经一系列的查找插入操作之后， 可生成一棵二叉排序树。设查找的关键字序列是 45，24，53，45，12，24，90，48，78，则生成 的二叉排序树是： 45 24 78 4890 12 53 第6页/共26页 7/20/2021 算法1：在根指针T所指二叉排序树中递归地查找某关键字 等于key的数据元素，若查找成功，则返回指向该数据元素结 点的指针，否则返回空指针。二叉排序树的存储

6、结构为二叉链 表。 BiTree SearchBST ( BiTree T, KeyType key ) if ( ! T ) | EQ ( key, Tdata.key ) return ( T ); /查找结束查找结束 else if LT ( key, Tdata.key ) return ( SearchBST ( Tlchild, key ); /在左子树中继续查在左子树中继续查 找找 else return ( SearchBST ( Trchild, key ); /在右子树中继续查找在右子树中继续查找 / SearchBST 第7页/共26页 7/20/2021 算法2：在查找

7、不成功时返回插入位置。 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据 元素，若查找成功，则指针p指向该数据元素结点并返回TRUE。否 则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f 指向T的双亲，其初始调用值为NULL。 Status SearchBST ( BiTree T, KeyType key, BiTree f, BiTree return FALSE; /查找不成功查找不成功 else if EQ ( key, Tdata.key ) p = T; return TRUE; /查找不成功查找不成功 else if LT ( key, Tdata.k

8、ey ) SearchBST ( Tlchild, key, key, T,p ); /在左子树中继续查找在左子树中继续查找 else SearchBST ( Trchild, key, T, p ); /在右子树中继续查找在右子树中继续查找 / SearchBST 第8页/共26页 7/20/2021 算法3：当二叉排序树T中不存在关键字等于e.key的数 据元素时，插入e并返回TRUE。否则返回FALSE。 Status Insert BST ( BiTree s data = e; s lchild = s rchild = NULL; if ( !p ) T = s; /被插结点被插结

9、点*s为新的根结点为新的根结点 else if LT ( e.key, pdata.key ) plchild = s; /被插结点被插结点*s为左孩子为左孩子 else prchild = s; /被插结点被插结点*s为右孩子为右孩子 Return TRUE; else return FALSE; /树中已有关键字相同的结点，不再插入树中已有关键字相同的结点，不再插入 / Insert BST 第9页/共26页 7/20/2021 二叉查找树的查找二叉查找树的查找 插入新结点插入新结点88 每次结点的插入，都要从根结点出发查找插入位每次结点的插入，都要从根结点出发查找插入位 置，然后把新结点

10、作为叶结点插入。置，然后把新结点作为叶结点插入。 4.4.二叉排序树的插入二叉排序树的插入 第10页/共26页 7/20/2021 输入数据序列输入数据序列 53,78,65,17,87,09,81,45,23 53,78,65,17,87,09,81,45,23 建立二叉排序树建立二叉排序树 第11页/共26页 7/20/2021 和插入相反，删除是在和插入相反，删除是在查找成功时查找成功时进行的，并且进行的，并且 要求在删除二叉排序树上某个结点之后，要求在删除二叉排序树上某个结点之后，仍然保持二仍然保持二 叉排序树的特性。叉排序树的特性。 三种情况三种情况讨论：讨论： （1 1）被删除的结

11、点）被删除的结点是叶子是叶子； （2 2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树； （3 3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树。 第12页/共26页 7/20/2021 其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空” 50 3080 2090 85 40 35 8832 例如例如: : 被删关键字被删关键字 = 2088 （1 1）被删除的结点是）被删除的结点是叶子结点叶子结点 第13页/共26页 7/20/2021 50 3080 2090 85 40 35 8832 删除删除40，80 其双亲结

12、点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点指向被删除结点 的左子树或右子树的左子树或右子树”。 （2 2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树 第14页/共26页 7/20/2021 （3）被删结点的左、右子树都存在 找到被删结点在中序下的前驱,设为B 1)将被删结点的左孩子代替被删结点,被删结点 的右子树改为B的右子树; 2)将B代替被删结点,被删结点的右子树改为B的 右子树,B的左子树成为B的双亲的右子树. 第15页/共26页 7/20/2021 50 40 3080 2090 8535 8832 91 40 以其前驱替代之

13、，然后再删除该前驱结以其前驱替代之，然后再删除该前驱结 点点 被删结点前驱结点 被删关键字被删关键字 = 50 20,30,32,35,40,50,80,85,88,90,91 左子树上最右下的结点左子树上最右下的结点 第16页/共26页 7/20/2021 （3）被删除的结点既有左子树，也有右子树既有左子树，也有右子树 另一种方法 *p为被删除结点， *f为*p的双亲结点， *c为*p左子树的根结点， *s为*p左子树上最右下的结点， 即在中序遍历中*p的直接前驱。 S C P F SL CL PR f p c s 第17页/共26页 7/20/2021 S C P F SL CL PR f

14、 p c s S C F SL CL PR f c s 第18页/共26页 7/20/2021 50 40 3080 2090 8535 8832 91 被删关键字被删关键字 = 50 80 90 85 88 无论哪种方法，都必须先找到被删结点左子树最右下的结点。无论哪种方法，都必须先找到被删结点左子树最右下的结点。 第19页/共26页 7/20/2021 第20页/共26页 BST树的结点删除情况树的结点删除情况 (e) 删除结点删除结点12 9 8 6 15 13 14 (d) 删除结点删除结点15 9 8 6 13 14 12 8 6 10 15 19 13 14 9 (a) BST树树

15、 12 8 6 10 15 13 14 9 (b) 删除结点删除结点19 12 8 6 9 15 13 14 (c) 删除结点删除结点10 第21页/共26页 7/20/2021 算法9.7：若二叉排序树T中存在关键字等于key的数据元素时， 则删除该数据元素结点，并返回TRUE，否则返回FALSE。 Status DeleteBST ( BiTree /不存在关键字等于不存在关键字等于key的数据元素的数据元素 else if EQ ( key, Tdata.key ) Delete ( T ); /找到关键字等于找到关键字等于key的数据元素的数据元素 else if LT ( key,

16、Tdata.key ) DeleteBST ( Tlchild, key ); else DeleteBST ( Trchild, key ); return TRUE; / DeleteBST 第22页/共26页 7/20/2021 算法算法9.8：从二叉排序树中删除结点：从二叉排序树中删除结点p，并重接它的左或右，并重接它的左或右 子树子树 void Delete ( BiTree p = plchild; free ( q); else if ( ! plchild ) /左子树空则只需重接它的右子左子树空则只需重接它的右子 树树 q = p; p = prchild; free ( q); else /左右子树均不空左右子树均不空 q = p; s = p lchild; while ( s rchild ) q = s; s = s rchild /转左，然后向右到尽头转左，然后向右到尽头 p data = s data; /s指向被删结点的指向被删结点的“ 前趋前趋” if ( q != p ) q rchild = s lchild; /重接重接*q的右子树的右子树 else q lchild = s lchild; /重接重接*q的的 左子树左子树/ Delete 第23页/共26页 由关键字序列 3，1，2，5，4构 造一