二叉排序树

定义

二叉排序树或是一棵空树，或是具有如下性质的二叉树

l  左子树若非空，则左子树所有结点的关键字必然小于根节点关键字

l  右子树若非空，则右子树所有结点的关键字必然大于根节点关键字

l  左子树和右子树均为二叉排序树

示例

二叉排序树的查找

l  若二叉排序树为空，则查找失败

l  比较结点关键字的值与给定值，若给定值更大，则查找结点的右子树

l  比较结点关键字的值与给定值，若给定值更小，则查找结点的左子树

二叉排序树的删除

这里指删除二叉排序树的某一个结点

l  若结点为叶节点，则直接删除

l  若结点的度为1，也即只有一棵子树，则用其左孩子或右孩子代替（关键字交换），再删除这个孩子

l  若结点有两个孩子，则用中序的直接前驱或直接后继将其代替（关键字交换），再删除这个这个直接前驱（左孩子的最右结点）或直接后继（右孩子的最左结点）

二叉排序树的插入

这里是指将将一个新节点插入到二叉排序树中

l  若二叉排序树为空，则直接将新节点插入

l  若新节点关键字大于当前节点的关键字，则插入右子树

l  若新节点关键字小于当前节点的关键字，则插入左子树

题目整理

001、在二叉排序树中，新插入的关键字总是处于最底层（王道模拟四-T07-Ⅲ）吗？

002、含有4个元素值均不相同的二叉排序树有_____种。答：14

003、含16个结点的平衡二叉树最大深度是___。(斐波那契：a1=1, a2=2, an=an-1+an-2+1)

答案整理

001、答：不是的，依据二叉排序树的插入规则，只有当二叉排序树为空时，新的结点才能直接插入，否则总是会通过比较转而向其某一子树插入，若从查找的角度考虑，在二叉排序树中查找新节点键值，则最后查找失败的结点即为最终新节点的位置（此时将空指针视为空结点），于是新插入的结点总是作为新二叉排序树的叶子节点，而“最底层“，反映的是二叉树中有关”层“的概念，一般根节点为第一层，第n结点的孩子均处于第n+1层。由此可见，叶节点不一定在最底层，因此新插入的关键字并不总是在最底层。