《动态查找表》由会员分享，可在线阅读，更多相关《动态查找表（20页珍藏版）》请在金锄头文库上搜索。
1、9.2 动态查找表二叉排序树9.2 动态查找表n1. 动态查找表n2. 二叉排序树1. 动态查找表n动态查找表除查找操作外，还可以进行插入和 删除。n动态查找表本身是在查找过程中动态生成的。n动态查找表ADT定义。P2262. 二叉排序树-概念n（1）什么是二叉排序树nP227421365742186578中序遍历二叉排序树，得 到从小到大的有序序列。2. 二叉排序树-查找n（2）查找算法n首先与根结点关键字比较，若相等则查找成功 ；否则根据大小关系在左子树或右子树上继续 查找。data t-datat=?2. 二叉排序树-查找算法1n二叉排序树查找算法1 BstTree BstSearch
2、( BstTree t, ElemType x ) if ( t=NULL )return NULL;else if ( t-data=x )return bt;else if ( xdata )return BstSearch ( t-lchild, x);elsereturn BstSearch ( t-rchild, x); 继续在左子树查找继续在左子树查找2. 二叉排序树-查找算法2n查找过程正好走了一条从根结点到该结点的路 径。若走到空指针则查找失败。2. 二叉排序树-查找算法2n二叉排序树查找算法2 BstTree BstSearch ( BstTree t, ElemType x
3、 ) p = t;while ( p ) if ( p-data=x )return p; /查找成功else if ( xdata )p = p-lchild;elsep = p-rchild;return NULL; / 查找失败 2. 二叉排序树-插入n（3）插入n首先进行查找，如果找不到，则插入结点。n“找不到”时，查找过程必定走到某个空指针上 ，待插入结点就插入此处。ptksff指向p的双亲2. 二叉排序树-插入算法BstTree BstInsert ( BstTree f = NULL; / f 指向p的双亲while ( p ) if ( p-data=x ) return p;
4、 /查找成功else if ( xdata ) f = p; p = p-lchild; else f = p; p = p-rchild; / 未找到，插入 x 2. 二叉排序树-插入算法/ 未找到，插入 xs = malloc(sizeof(BiNode);s-data = x;s-lchild = s-rchild = NULL;if ( f = NULL ) t = s; / 插入s为根结点else if ( x data ) f-lchild = s;else f-rchild = s;return s; / 返回插入结点 2. 二叉排序树-建立n（4）建立二叉排序树n开始时，二叉树
5、为空，依次插入给定的关键字 即可建立。2. 二叉排序树-建立n例：给定关键字序列 53，45，12，24，90，45，80， 建立二叉排序树。n提示：从空二叉树开始，依次插入关键字。5345901224802. 二叉排序树-删除n（5）删除n首先进行查找，若找到，则删除结点。n删除结点时需要修改2. 二叉排序树-删除算法BstTree BstDelete ( BstTree f = NULL; / f 指向p的双亲while ( p ) if ( p-data=x ) break; /查找成功，进行删除else if ( xdata ) f = p; p = p-lchild; else f
6、= p; p = p-rchild; / 若找到，删除结点if ( p != NULL ) 2. 二叉排序树-删除算法n被删除结点分三种情况：na) 叶子nb) 左子树或右子树为空 nc) 左右子树都不空fp(a)fp(b)fpfpfpfp(c)2. 二叉排序树-删除算法/ 若找到，删除结点if ( p != NULL ) / a) p 是叶子if ( p-lchild=NULL else if ( f-lchild=p ) f-lchild = NULL;else f-rchild = NULL; / b) p 只有一个子树else if ( p-lchild=NULL ) / p只有右子树
7、if ( f=NULL ) t = p-rchild;else if ( f-lchild=p ) f-lchild = p-rchild;else f-rchild = p-rchild; else if ( p-rchild=NULL ) / p只有左子树if ( f=NULL ) t = p-lchild;else if ( f-lchild=p ) f-lchild = p-lchild;else f-rchild = p-lchild; / b) p 既有左子树也有右子树else /找到p的“前驱”（左子树上的最大元素）q = p; s = p-lchild;while ( s-rchild ) q = s; s = s-rchild; /用p的“前驱”s代替pp-data = s-data;/删除s（s的右子树必然为空）if ( q != p ) q-rchild = s-lchild;else q-lchild = s-lchild; / if (p!=NULL)/ 返回被删除结点，若未找到时返回NULLreturn p;
