大学《数据结构》第八章：查找-第三节-树表的查找（一）

第三节树表的查找（一）一、二叉排序树1、二叉排序树的概念（1）二叉排序树的定义二叉排序树(BinarySortTree，BST)又称二叉查找，是一种特殊的二叉树，二叉排序树或者是空树，或者是满足如下性质的二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又各是一棵二叉排序树。【例】下图的就是一棵二叉排序树中序遍历序列：15，16，18，19，20，22，30，35，42（2）二叉排序树的重要性质中根遍历一棵二叉排序树所得的结点访问序列是按键值的递增序列。（3）二叉排序树的数据类型定义typedefstructnode{KeyTypekey；//关键字DataTypeother；//其他数据域structnode*lchild，*rchild；//左右子树指针}BsTNode；//结点类型typedefBsTNode*BsTree；//二叉排序树类型2、二叉排序树的插入（1）算法思想在二叉排序树中插入新结点，要保证插入后仍满足BST性质。其插入过程是：①若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；②若二叉排序树T不为空，则将key和根的关键字比较：若二者相等，则说明树中已有此关键字key，无须插入。若key<T→key，则将key插入根的左子树中。若key>T→key，则将它插入根的右子树中。子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。（2）实例分析【例】写出把无序序列（20，10，30，15，25，5，35，12，27）建成二叉排序树的过程。【解答】采用逐点插入结点的方法即可建立相应的二叉排序树。建成二叉排序树的过程如图所示（3）算法描述BSTreeInsertBST(BSTreeT，BSTNode*S){BSTNode*f，*p=T；while(p)//找插入位置｛f=p；//f记录p的双亲，为将来插入结点if(S->key<p->key)p=p->lchild；elsep=p->rchild；}if(T==NULL)T=S；//T为空树，新结点作为根结点elseif(S->key<f->key)f->lchild=S；//作为双亲的左孩子插入elsef->rchild=S；//作为双亲的右孩子插入returnT；｝3、二叉排序树的生成（1）算法思想从空的二叉树开始，每输入一个结点数据，生成一个新结点，就调用一次插入算法将它插入到当前生成的二又排序树中（2）算法描述BSTreeCreateBST(void){//从空树开始，建立一棵二叉排序树BSTreeT=NULL；//初始化T为空树KeyTypekey；BSTNode*S；scanf("％d"，&key)；//输入第一个关键字while(key)//假设key=0是输入结束{S=(BSTNode*)malloc(Sizeof(BSTNode))；S->key=key；//生成新结点S->1child=S->rchiId=NULL：T=InsertBST(T，S)；//将新结点*S插入二叉排序树Tscanf("％d"，&key)；//输入下一个关键字｝returnT；//返回建立的二叉排序树｝【例】已知某二叉排序树10个结点的值依次为1~10，其结构如图所示，试标出该二叉树各结点所对应的具体值。【分析】根据二叉排序树的的特点：对二叉排序树进行中序遍历，得到的是从小到大的序列。给题中给出的二叉树各结点填入字符，如图所示；再对该二叉树进行中序遍历得到序列：（D，J，I，G，B，A，E，H，C，F）；根据二叉排序树的的特点和题目要求，这个序列对应序列（1，2，3，4，5，6，7，8，9，10）；将二叉树中的字符改为对应得数字即可。【解答】二叉树各结点所对应的具体值如图所示。4、二叉排序树上的查找（1）算法思想若二叉排序树为空，则表明查找失败，应返回空指针。否则，若给定值key等于根结点的关键字，则表明查找成功，返回当前根结点指针；若给定值key小于根结点的关键字，则继续在根结点的左子树中查找，若给定值key大于根结点的关键字，则继续在根结点的右子树中查找。显然，这是一个递归的查找过程，（2）算法描述BSTNode*SearchBST(BSTreeT，KeyTypex){//在二叉排序树上查找关键字值为x的结点if(T==NULL||T->key==x)returnT；if(x<T->key)returnSearchBST(T->lchild，x)；elsereturnSearchBST(T->rchild，x)；}（3）算法分析二叉排序树上的查找长度与二叉排序树的形态有关，若二叉排序树是一棵理想的平衡树（是指树中任一结点的左右子树的高度差不能大于1），则进行查找的时间复杂度为O(log2n)；若退化为一棵单支树，则其查找的时间复杂度为O(n)。对于一般情况，其时间复杂度应为O(log2n)。【例】给定表（20，15，18，12，25，27，30，22，17，20，28），按数据元素在表中的次序构造一棵二叉排序树，求出其平均查找长度。【解答】按照构造二叉排序树方法，构造结果如图所示。平均查找长度为：（1+2×2+4×3+3×4+5×1）/11=34/115、二叉排序树上的删除从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为p，其父结点为f，如图（a）所示的BST树。具体删除情况分析如下：（1）若p是叶子结点：直接删除p，如图（b）所示。（2）若p只有一棵子树（左子树或右子树），直接用p的左子树（或右子树）取代p的位置而成为f的一棵子树。即原来p是f的左子树，则p的子树成为f的左子树；原来p是f的右子树，则p的子树成为f的右子树，如图（c）所示。（3）若p既有左子树又有右子树，处理方法有以下两种，可以任选其中一种。①用p的直接前驱结点（中序遍历）代替p，即从p的左子树中选择值最大的结点s放在p的位置（用结点s的内容替换结点p内容），然后删除结点s。s是p的左子树中最右边的结点且没有右子树，如图（d）所示。②用p的直接后继结点（中序遍历）代替p，即从p的右子树中选择值最小的结点s放在p的位置（用结点s的内容替换结点p的内容），然后删除结点s。s是p的右子树中的最左边的结点且没有左子树。例如，对图（a）所示的二叉