使用二叉链表建立二叉排序树

using System;
//二叉数的结点结构
class BinaryTreeNode<T>
{
    private T m_Data;
    private BinaryTreeNode<T> m_Lchild;//指向左孩子
    private BinaryTreeNode<T> m_Rchild;//指向右孩子
    private BinaryTreeNode<T> m_Parent;//指向父结点
    //构造函数
    public BinaryTreeNode(T nData, BinaryTreeNode<T> nParent,
        BinaryTreeNode<T> nLchild, BinaryTreeNode<T> nRchild)
    {
        m_Data = nData;
        m_Parent = nParent;
        m_Lchild = nLchild;
        m_Rchild = nRchild;
    }
    //属性域
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }
    public BinaryTreeNode<T> Lchild
    {
        get { return m_Lchild; }
        set { m_Lchild = value; }
    }
    public BinaryTreeNode<T> Rchild
    {
        get { return m_Rchild; }
        set { m_Rchild = value; }
    }
    public BinaryTreeNode<T> Parent
    {
        get { return m_Parent; }
        set { m_Parent = value; }
    }
}
//二叉排序树类
class BinarySortTree
{
    private BinaryTreeNode<int> m_Head;
    //构造函数
    public BinarySortTree()
    {
        m_Head = null;
    }
    //查找和nItem值相等的结点
    //找到 则返回该结点
    //没找到  则返回null
    public BinaryTreeNode<int> Search(int nItm)
    {
        if (null == m_Head)
        {
            return null;
        }
        BinaryTreeNode<int> tmp = m_Head;
        while (null != tmp)
        {
            if (tmp.Data > nItm)
            {
                tmp = tmp.Lchild;
            }
            else if (tmp.Data < nItm)
            {
                tmp = tmp.Rchild;
            }
            else
            {
                return tmp;
            }
        }
        return null;
    }
    //插入nItem值
    //树中已有该值  则不插入  否则进行插入
    //插入成功  则返回true
    //没有插入到树中 则返回false
    public bool Insert(int nItem)
    {
        //如果在树中没有该值  则进行插入操作
        if (null != this.Search(nItem))
        {
            return false;//插入失败
        }
        //插入操作  则要找到插入点
        BinaryTreeNode<int> tmp = m_Head;
        if (null == m_Head)
        {
            m_Head = new BinaryTreeNode<int>(nItem, null, null, null);
            return true;
        }
        while (null != tmp)
        {
            if (tmp.Data > nItem)
            {
                if (null == tmp.Lchild)
                {
                    tmp.Lchild = new BinaryTreeNode<int>(nItem, tmp, null, null);
                    return true;
                }
                tmp = tmp.Lchild;
            }
            else if (tmp.Data < nItem)
            {
                if (null == tmp.Rchild)
                {
                    tmp.Rchild = new BinaryTreeNode<int>(nItem, tmp, null, null);
                    return true;
                }
                tmp = tmp.Rchild;
            }
        }
        return false;
    }
    //删除nItem值
    //成功删除  则返回true
    //  否则返回false
    public bool Delete(int nItem)
    {
        BinaryTreeNode<int> tmp = this.Search(nItem);
        BinaryTreeNode<int> ftmp;
        if (null == tmp)
        {
            return false;
        }
        ftmp = tmp.Parent;
        if (null == tmp.Rchild && null == tmp.Lchild)
        {//左右孩子都为空 则直接删除该结点
            if (null != ftmp)
            {
                if (ftmp.Lchild == tmp)
                {
                    ftmp.Lchild = null;
                }
                else
                {
                    ftmp.Rchild = null;
                }
            }
            else
            {
                m_Head = null;
            }
        }
        else if (null == tmp.Lchild && null != tmp.Rchild)
        {//只有左孩子为空 把右孩子代替该结点的位置
            if (null != ftmp)
            {
                if (ftmp.Lchild == tmp)
                {
                    ftmp.Lchild = tmp.Rchild;
                }
                else
                {
                    ftmp.Rchild = tmp.Rchild;
                }
            }
            tmp.Rchild.Parent = ftmp;
        }
        else if (null != tmp.Lchild && null == tmp.Rchild)
        {//只有右孩子为空  把左孩子代替该结点的位置
            if (null != ftmp)
            {
                if (ftmp.Lchild == tmp)
                {
                    ftmp.Lchild = tmp.Lchild;
                }
                else
                {
                    ftmp.Rchild = tmp.Lchild;
                }
            }
            tmp.Lchild.Parent = ftmp;
        }
        else if (null != tmp.Lchild && null != tmp.Rchild)
        {//左右孩子都不为空  则找到右孩子
            BinaryTreeNode<int> s = tmp.Rchild;
            //若右孩子的左孩子为空  则用右孩子直接代替
            if (null == s.Lchild)
            {
                if (null != ftmp)
                {
                    if (ftmp.Lchild == tmp)
                    {
                        ftmp.Lchild = s;
                    }
                    else
                    {
                        ftmp.Rchild = s;
                    }
                }
                s.Parent = ftmp;
                s.Lchild = tmp.Lchild;
                s.Lchild.Parent = s;
            }
            else
            {//若右孩子的左孩子不为空， 则一直找到右孩子的左孩子直到为空
                while (s.Lchild != null)
                {
                    s = s.Lchild;
                }
                //如果 s的右孩子不为空 则用s的右孩子替换s的位置
                //然后 s代替删除结点的位置
                BinaryTreeNode<int> sftmp = s.Parent;
                if (null != s.Rchild)
                {
                    s.Rchild.Parent = sftmp;
                    sftmp.Lchild = s.Rchild;
                }
                else
                {
                    sftmp.Lchild = null;
                }
                s.Parent = ftmp;
                if (null != ftmp)
                {
                    if (ftmp.Lchild == tmp)
                    {
                        ftmp.Lchild = s;
                    }
                    else
                    {
                        ftmp.Rchild = s;
                    }
                }
                tmp.Rchild.Parent = s;
                tmp.Lchild.Parent = s;
                s.Rchild = tmp.Rchild;
                s.Lchild = tmp.Lchild;
            }
        }
        return true;
    }
}
class App
{
    static BinarySortTree BSTree = new BinarySortTree();
    static void Main(string[] args)
    {
        while (true)
        {
            if (4 == Run())
            {
                break;
            }
        }
    }
    static int Run()
    {
        int Num;
        Console.WriteLine("\t根据提示信息进行处理");
        Console.WriteLine("插入操作按 \'1\'");
        Console.WriteLine("查找操作按 \'2\'");
        Console.WriteLine("删除操作按 \'3\'");
        Console.WriteLine("推出按 \'4\'");
        Num = int.Parse(Console.ReadLine());
        switch (Num)
        {
            case 1:
                Console.Write("输入要插入的数据:");
                Num = int.Parse(Console.ReadLine());
                if (!BSTree.Insert(Num))
                {
                    Console.WriteLine("\t插入失败...");
                }
                break;
            case 2:
                Console.Write("输入要查找的数据:");
                Num = int.Parse(Console.ReadLine());
                if (null == BSTree.Search(Num))
                {
                    Console.WriteLine("\t查找失败...");
                }
                break;
            case 3:
                Console.Write("输入要删除的数据:");
                Num = int.Parse(Console.ReadLine());
                if (!BSTree.Delete(Num))
                {
                    Console.WriteLine("\t删除失败...");
                }
                break;
            case 4:
                break;
            default:
                break;
        }
        return Num;
    }
}