二叉搜索树

目录

1 二叉搜索树概念

2 二叉搜索树操作

---

1 二叉搜索树概念

• 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
  • 注意：也可以是左子树上所有节点的值大于根节点的值，右子树上所有节点的值小于根节点的值
• 

2 二叉搜索树操作

• 1. 二叉搜索树的查找

  • 

• 2. 二叉搜索树的插入
  • a. 树为空，则直接插入
  • b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

    • 

• 3. 二叉搜索树的删除
  • 根节点为空，直接返回false
  • 找待删除节点在二叉搜索树中的位置，并保存其双亲

    • 

  • 通过分析，发现删除时，待删除节点需要根据孩子节点分情况:
    • 1.待删除节点是叶子节点
    • 2.待删除节点只有左孩子
    • 3.待删除节点只有右孩子
    • 4.待删除节点左右孩子均存在
  • 进一步分析:可以将情况1和情况2合并，或者将情况1和情况3合并：
    • 

    • 

    • 

    • 

  • 

  •