一、什么是二叉搜索树？

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