一、什么是二叉搜索树？

二叉搜索树（BST，Binary Search Tree）， 也称二叉排序树或二叉查找树

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值
2. 非空右子树的所有键值大于其根结点的键值
3. 左、右子树都是二叉搜索树

---

二、为什么要使用二叉搜索树

解决查找问题,方便查找与动态修改。

---

三、二叉搜索树操作函数

查找：Position Find( ElementType X, BinTree BST )：从二叉搜索树BST 中查找元素X，返回其所在结点的地址

找最小： Position FindMin( BinTree BST )：从二叉搜索树BST中查找并返回 最小元素所在结点的地址

找最大： Position FindMax( BinTree BST ) ：从二叉搜索树BST中查找并返回 最大元素所在结点的地址

插入值： BinTree Insert( ElementType X, BinTree BST ) ：插到对应的位置，返回整个树的根节点

删除值：BinTree Delete( ElementType X, BinTree BST ) ：删除对应的元素并调整连接

---

四、二叉搜索树操作的代码实现

0.创建

利用插入操作实现创建搜索树

//利用插入操作实现创建搜索树
public static TreeNode<int> CreatBinSerachTree(int[] listData)
    {
        TreeNode<int> BST = null;
        for (int i = 0; i < listData.Length; i++)
        {
            BST = BinSerachTree.Insert(listData[i], BST);
        }
        return BST;
    }

---

1、查找 Find

非递归：

//非递归
    public static TreeNode<int> IterFind(int data, TreeNode<int> BST)
    {
        while (BST != null)
        {
            if (data > BST.Data)
            {
                BST = BST.Right;
            }
            else if (data < BST.Data)
            {
                BST = BST.Left;
            }
            else
            {
                return BST;
            }           
                 
        }
        return null;
    }

递归式：

//递归式
public static TreeNode<int> Find(int data, TreeNode<int> BST)
    {
        if (BST == null) return null;
        if (data > BST.Data)
        {
            return Find(data, BST.Right);//尾递归
        }
        else if (data < BST.Data)
        {
            return Find(data, BST.Left);
        }
        else
        {
            return BST;
        }
    }

---

2、找最小（最小值在左子树的最左端）

非递归：

//非递归
public static TreeNode<int> IterFindMin(TreeNode<int> BST)
    {
        if (BST != null)
        {
            while (BST.Left != null)
            {
                BST = BST.Left;
            }
        }
        return BST;
    }

递归式：

//递归式
public static TreeNode<int> FindMin(TreeNode<int> BST)
    {
        if (BST == null)
        {
            return null;
        }
        else if (BST.Left == null)
        {
            return BST;
        }
        else
        {
            return FindMin(BST.Left);
        }
    }

---

3.找最大（最大值在右子树的最右端）

非递归：

//非递归
 public static TreeNode<int> IterFindMax(TreeNode<int> BST)
    {

        if (BST != null)
        {
            while (BST.Right != null)
            {
                BST = BST.Right;
            }
        }
        return BST;
    }

递归式：

//递归式
    public static TreeNode<int> FindMax(TreeNode<int> BST)
    {
        if (BST == null)
        {
            return null;
        }
        else if (BST.Right == null)
        {
            return BST;
        }
        else
        {
            return FindMax(BST.Right);
        }
    }

---

4.插入值

递归式：

//递归式

    public static TreeNode<int> Insert(int data, TreeNode<int> BST)
    {
        if (BST == null)
        {
            BST = new TreeNode<int>(data);
        }
        else
        {
            if (data < BST.Data)
            {
                BST.Left = Insert(data, BST.Left);
            }
            else if (data > BST.Data)
            {
                BST.Right = Insert(data, BST.Right);
            }
        }
        return BST;
    }

---

5.删除值

递归式：

//递归式
public static TreeNode<int> Delete(int data, TreeNode<int> BST)
    {
        if (BST == null)
        {
            Debug.Log("未找到要删除的元素！");
        }
        else if (data < BST.Data)
        {
            BST.Left = Delete(data, BST.Left); //左子树递归删除
        }
        else if (data > BST.Data)
        {
            BST.Right = Delete(data, BST.Right); //右子树递归删除
        }
        else //找到删除的节点
        {
            if (BST.Left != null && BST.Right != null) //被删除的节点，有左右两个儿子
            {
                BST.Data = FindMin(BST.Right).Data; //在右子树中找最小的元素填充删除结点
                BST.Right = Delete(BST.Data, BST.Right);
            }
            else //被删节点有一个或无节点孩子
            {
                if(BST.Left==null) //有右孩子或无子结点
                {
                    BST = BST.Right;
                }
                else if(BST.Right==null) //有左孩子或无子结点
                {
                    BST = BST.Left;
                }                
            }
        }
        return BST;
    }

二叉搜索树的删除：分三种情况

1、要删除的是叶结点：直接删除，并再修改其父结点指针---置为NULL

2、要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点

3、要删除的结点有左、右两棵子树： 用另一结点替代被删除结点：右子树的最小元素或者 左子树的最大元素

---

注：

1、二叉搜索树的查找搜索效率取决于树的高度

2、不同的构造会让树的高度过于高，这样不利于减少搜索的次数

3、由于上述原因，我们将学习到如何来构造平衡二叉树,减小树的高度，缩小平均搜索长度（ASL）