15.2 二叉搜索树的封装

 二叉搜索树的封装：

二叉搜索树常见操作：
代码实现：

遍历二叉搜索树

• 二叉树的遍历常见的有三种方式：

1. 先序遍历
2. 中序遍历
3. 后序遍历
   1.先序遍历：
6. 
   实现代码：

2 .中序遍历

3. 
   实现代码：

3.后序遍历

3. 
   实现代码：

最大值 & 最小值

搜索特定的值

二叉搜索树的删除

• 
  查找子节点代码实现：

情况一：没有子节点

• 
• 代码实现：

情况二：一个子节点

• 
  图解过程：
• 

情况三：两个子节点

• 
  寻找规律
• 总结那个节点最接近current，那个就可以用来替换current的位置。
• 前驱&后继
• 
  获取后继的方法

二叉搜索树的缺陷

• 二叉搜索树作为数据存储的结构重要的优势：
• 插入和删除数据项
• 但是，二叉搜索树有一个很麻烦的问题：
• 有序的数据
• 非平衡树：
• 树的平衡性
• 至少大部分是平衡的，那么时间复杂度也是接近O(logN)的。
• 常见的平衡树有哪些