一、什么是二叉搜索树？

二叉搜索树（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）