算法16--二叉排序树.pptVIP

2.二叉排序树的存储结构（二叉链表） 5.二叉排序树的删除 * 第8章 查找 8.2动态查找表 动态查找的特点是，表结构本身是在查找过程中动态生成的，即对给定关键字值key ，表中有具有此值的记录，则查找成功返回，否则插入此关键字的新记录。 ADT DynamicSearchTable { 数据对象D：具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据关系R：数据元素同属一个集合。 基本操作: InitDSTable(DT); //构造一个空的动态查找表DT DestroyDStable( DT); // 销毁查找表DT。 SearchDSTable(DT,key); //查找具有关键字key 的元素。 InsertDSTable(DT,e); //插入新记录。 DeleteDSTable(DT,key );//删除记录。 TraverseDSTable(DT,visit()); //遍历查找表。 } ADT DynamicSearchTable 动态查找表的抽象数据类型 8.2.1.二叉排序树和平衡二叉树 1.二叉排序树的定义 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： ? 若它的左子树不空,则左子树上所有结点的关键字都小于根结点的关键字。 ? 若它的右子树不空,则右子树上所有结点的关键字都大于根结点的关键字。 ? 左子树和右子树分别是二叉排序树。 不是二叉排序树 50 30 80 20 90 10 85 40 35 25 23 88 66 二叉排序树的例子 typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; ElemType data; } BiTNode, *BiTree; 3.二叉排序树的查找 算法思想： (1) p指向根； (2) p的关键字与key比较，有三种情况： p-data.key==key; 查找成功，返回p, 结束； p-data.keykey; 到左子树中找，p指向它左子女； p-data.keykey; 到右子树中找， p指向它右子女； (3) 重复(2)直到p为空，查找失败，返回空； 例 从空树出发，经一系列的查找插入操作之后，可生成一棵二叉排序树。设查找的关键字序列是 {45，24，53，45，12，24，90，48，78}，则生成的二叉排序树是： 45 24 78 48 90 12 53 算法1：在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，若查找成功，则返回指向该数据元素结点的指针，否则返回空指针。二叉排序树的存储结构为二叉链表。 BiTree SearchBST ( BiTree T, KeyType key ) { if (( ! T ) || EQ ( key, T－＞data.key )) return ( T ); //查找结束 else if LT ( key, T－＞data.key )) return ( SearchBST ( T－＞lchild, key )); //在左子树中继续查找 else return ( SearchBST ( T－＞rchild, key )); //在右子树中继续查找 }// SearchBST 算法2：在查找不成功时返回插入位置。 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素结点并返回TRUE。否则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL。 Status SearchBST ( BiTree T, KeyType key, BiTree f, BiTree p ) { if ( ! T ) { p = f; return FALSE; } //查找不