定义:
空树或满足下列性质的二叉树:
1)若它的左子树不空,则左子树所有的关键字的值均小于根关键字的值
2)若它的右子树不空,则右子树所有的关键字的值均大于根关键字的值
3) 左右子树又各是一颗二叉排序树
中序遍历结果是一个增序序列
比较难搞的是BST删除节点
分析如下:
1)首先找到那个节点获取节点的指针位置和父节点指针位置
2)通过这两个指针进行判断获取删除的方案
设目标节点为P
(1)P无子树=>P是叶子节点
如果父节点是空节点那么这个棵树只有一个节点直接root为空
如果父节点不是空节点那么判断出P在父节点的位置并将这个位置设为 空即可
(2)P有单子树
将P的子树代替父节点的子树即可
(3)P有双子树