LeetCode二叉排序树(BST)的总结

一,定义

二叉排序树(简称BST)的定义为:二叉排序或者是空树,或者是满足如下性质的二叉树:
若他的左子树非空,则左子树上所有记录的值均小于根记录的值
若他的右子树非空,则右子树上所有记录的值均大于根记录的值
左,右子树本身又各是一棵二叉排序树

二,性质

• 1, 二叉排序树按中序遍历该树所得到的中序序列是一个递增有序序列

• 2,二叉排序树最大节点是根节点的最右下节点,最小节点是根节点的最左下节点

三,二叉排序树的查找

若二叉排序树非空,将给定关键字与根节点比较,若相等,则查找成功.
若不等,则当根节点关键字值大于给定关键字值时,到根节点的左子树中查找;否则到根节点的右子树中查找.

四,二叉树的插入和构建

若原二叉排序树为空,则直接插入节点;
否则,若关键字k小于根节点的值,则插入到左子树
若关键字k大于根节点,则插入到右子树

例如LeetCode 108. Convert Sorted Array to Binary Search Tree
** 值得注意的是: 在二叉排序树中插入的节点都是作为叶子节点插入的 **

五,二叉排序的删除

BST删除一个节点后,仍要保持BST的特性. 删除一个节点本质上说,就是使用这个节点的中序遍历的直接前驱或者直接后继来代替他
删除一个节点分为四种情况

• 1)待删除节点p是个叶子节点,那么直接删除他即可
• 2)待删除节点p只有右子树而无左子树,此时只需p的右子树根节点代替p即可
• 3)待删除节点p只有左子树而无右子树,此时只需p的左子树根节点代替p即可
• 4)待删除节点p左右子树都不为空.可以有两种方法处理
  A,用p的左子树的最右边节点代替
  B,用p的右子树的最左边节点代替
  例如LeetCode 450. Delete Node in a BST