数据结构之二叉搜索树（Binary Search Tree）

二叉树搜索树

每个节点最多含有两个子树的树称为二叉树；二叉树搜索树对于任意一个节点均满足：

• 1. 所有位于左子树的节点值均比该节点值小
• 2. 所有位于右子树的节点值均大于等于该节点值
• 3. 所有左子树和右子树也必须是BST

二叉树搜索树的查找比较简单，最左边的叶节点就是最小值，最右边的叶节点就是最大值，主要讲下遍历与删除。

遍历

有三种遍历二叉树的方法：前序（preorder）、中序（inorder）、后序（postorder）

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后在打印它的左子树，最后打印它的右子树。

  
  前序遍历
  

  中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后打印它自己，最后打印它的右子树。
  这个会使所有节点按关键字值升序被访问到。

  
  中序遍历

后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后打印它的右子树，最后打印它自己。

后序遍历

删除节点

删除节点是二叉树常用的一般操作中最复杂的，需要考虑三种情况：

• 1.该节点是叶节点
• 2.该节点有一个子节点
• 3.该节点有两个子节点
  第一种与第二种比较简单，第三种比较复杂。

删除没有子节点的节点，只需要改变该节点的父节点的对应子字段的值，由指向该节点改为null就可以。

删除有一个子节点的节点，只要把该节点的子节点连接到该节点的父节点上就可以。

删除有两个子节点的节点，对于二叉搜索树，对每一个节点来说，比该节点的关键字值次高的节点是它的中序后继，可以简称为该节点的后继。那么该节点的后继不会有左子节点，最多有个右子节点。

优点

二叉树搜索树相比于其他数据结构的优势在于查找、插入的时间复杂度较低

缺点

如果树中插入的随机数据，则执行效果很好。但是，如果插入的是有序的数据或者逆序的数据，速度就会变得特别慢。因为当插入的数值有序时，二叉树就是非平衡树。而对于非平衡树，它的快速查找（插入、删除）指定数据项的能力就丧失了。为了解决这个问题，就有了红-黑树。