文档介绍：二叉排序树二叉排序树 (BinarySortTree)或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于根结点的值;若右子树不空,则右子树上所有结点的值均大于根结点的值。(2)左右子树也都是二叉排序树,如图6-2所示。 ,二叉排序树的查找过程为: (1)若查找树为空,查找失败。(2)查找树非空,将给定值key与查找树的根结点关键码比较。(3)若相等,查找成功,结束查找过程,否则: ①当给值key小于根结点关键码,查找将在以左孩子为根的子树上继续进行,转(1)。②当给值key大于根结点关键码,查找将在以右孩子为根的子树上继续进行,转(1)。 :设待插入结点的关键码为key,为将其插入,先要在二叉排序树中进行查找,若查找成功,按二叉排序树定义,该插入结点已存在,不用插入;查找不成功时,则插入之。因此,新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。对于关键码序列为:{63,90,70,55,67,42,98,83,10,45,58},则构造一棵二叉排序树的过程如图6-3所示。 ,要求其仍能保持二叉排序树的特性。设待删结点为*p(p为指向待删结点的指针),其双亲结点为*f,删除可以分三种情况,如图6-4所示。(1)*p结点为叶结点,由于删去叶结点后不影响整棵树的特性,所以,只需将被删结点的双亲结点相应指针域改为空指针,如图6-4(a)所示。(2)*p结点只有右子树或只有左子树,此时,只需将或替换*f结点的*p子树即可,如图6-4(b)、(c)所示。(3)*p结点既有左子树又有右子树,可按中序遍历保持有序地进行调整,如图6-4(d)、(e)所示。设删除*p结点前,中序遍历序列为: ①P为F的左子女时有:…,Pi子树,P,Pj,S子树,Pk,Sk子树,…,P2,S2子树,P1,S1子树,F,…。②P为F的右子女时有:…,F,Pi子树,P,Pj,S子树,Pk,Sk子树,…,P2,S2子树,P1,S1子树,…。则删除*p结点后,中序遍历序列应为: ①P为F的左子女时有:…,Pi子树,Pj,S子树,Pk,Sk子树,…,P2,S2子树,P1,S1子树,F,…。②P为F的右子女时有:…,F,Pi子树,Pj,S子树,Pk,Sk子树,…,P2,S2子树,P1,S1子树,…。有两种调整方法: ①直接令Pi为*f相应的子树,以Pr为Pi中序遍历的最后一个结点Pk的右子树。②令*p结点的直接前驱Pr或直接后继(对Pi子树中序遍历的最后一个结点Pk)替换*p结点,再按(2)的方法删去Pr或Pk。【算法分析】对给定序列建立二叉排序树,若左右子树均匀分布,则其查找过程类似于有序表的折半查找。但若给定序列原本有序,则建立的二叉排序树就蜕化为单链表,其查找效率和顺序查找一样。因此,对均匀的二叉排序树进行插入或删除结点后,应进行调整,使其依然保持均匀。、查找、插入和删除操作。在以下的知识点中,二叉排序树的删除相对于其他知识点要复杂一些,但只要掌握了规则,题目还是很容易解决的。下面我们先分别给出各部分的介绍及算法实现,再对一些典型题目进行解析。(1)二叉排序树二叉排序树是一种常用的动态查找表,下面首先给出它的非递归形式。二叉排序树是一棵二叉树,它或者为空,或者具有如下性质:①任一非终端结点若有左孩子,则该结点的关键字值大于其左孩子结点的关键字值。②任一非终端结点若有右孩子,则该结点的关键字值小于其右孩子结点的关键字值。二叉排序树也可以用递归的形式定义,即二叉排序树是一棵树,它或者为空,或者具有如下性质:①若它的左子树非空,则其左子树所有结点的关键字值均小于其根结点的关键字值。②若它的右子树非空,则其右子树所有结点的关键字值均大于其根结点的关键字值。③它的左右子树都是二叉排序树。例如,由关键字值序列(62,15,68,46,65,12,57,79,35)构成的一棵二叉排序树如图3-38所示。如果对上述二叉排序树进行中序遍历可以得到一个关键字有序序列(12,15,35,46,57,62,65,68,79),这是二叉排序树的一个重要特征,也正是由此将其称为"二叉排序树"。(2)二叉排序树的查找二叉排序树的结构定义中可看到:一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值,而小于其右子树上所有结点的关键字值。因此在二叉排序树中查找一个关键字值为k的结点的基本思想是:用给定值k与根结点关键字值比较,如果k小于根结点的值,则要找的结点只可能