C# 二叉排序树

2021-01-07 10:10发布

二叉排序树,又称为二叉查找树。它或者是一颗空树,或者是具有下列性质的二叉树:

  • 若它的左子树不为空。则左子树上所有的结点的值均小于跟的结点值

  • 若它的右子树部位空,则右子树的所有结点值均大于它的根结点的值

  • 它的左右子树也分别是二叉排序树

1,排序方便
2,查找方便
3,便于插入和删除

C#链式存储二叉排序树,实现简单的排序,以及查找,,具体代码如下:

namespace _2_1_3二叉排序树

{

    /// <summary>

    /// 结点类

    /// </summary>

    class BSNode

    {

        //结点

        public BSNode LeftChild { get; set; }

        public BSNode RightChild { get; set; }

        public BSNode Parent { get; set; }


        public int Data { get; set; }

       

        // 构造方法

        public BSNode(){}

        public BSNode(int item)

        {

            this.Data = item;

        }



    }

}

using System;


namespace _2_1_3二叉排序树

{

    /// <summary>

    /// 二叉排序树

    /// </summary>

    class BSTree

    {

        BSNode root = null;


        /// <summary>

        /// 添加数据

        /// </summary>

        public void Add(int item)

        {

            //创建新结点

            BSNode newNode = new BSNode(item);


            if (root == null)         //若为空,则创建为根结点

            {

                root = newNode;

            }

            else

            {

                BSNode temp = root;

                while (true)

                {

                    if (item >= temp.Data)  //放在temp结点的右边

                    {

                        if (temp.RightChild == null)

                        {

                            temp.RightChild = newNode;

                            newNode.Parent = temp;

                            break;

                        }

                        else

                        {

                            temp = temp.RightChild;

                        }

                    }

                    else                   //放在temp结点的左边

                    {

                        if (temp.LeftChild == null)

                        {

                            temp.LeftChild = newNode;

                            newNode.Parent = temp;

                            break;

                        }

                        else

                        {

                            temp = temp.LeftChild;

                        }

                    }

                }

            }

        }


        /// <summary>

        /// 中序遍历二叉树

        /// </summary>

        public void MiddleBianli()

        {

            MiddleBianli(root);

        }

        //递归方式中序遍历树

        private void MiddleBianli(BSNode node)

        {

            if (node == null) return;


            MiddleBianli(node.LeftChild);

            Console.Write(node.Data + " ");

            MiddleBianli(node.RightChild);

        }


        /// <summary>

        ///查找方法-1

        /// </summary>

        public bool Find1(int item)

        {

            return Find(item, root);

        }

        private bool Find(int item, BSNode node)

        {

            if (node == null) { return false; }

            if (node.Data == item)

            {

                return true;

            }

            else

            {

                //利用二叉排序树的便利

                if (item > node.Data)

                {

                    return Find(item, node.RightChild);

                }

                else

                {

                    return Find(item, node.LeftChild);

                }

            }

        }


        /// <summary>

        /// 查找方法-2

        /// </summary>

        /// <param name="item"></param>

        /// <returns></returns>

        public bool Find2(int item)

        {

            BSNode temp = root;

            while (true)

            {

                if (temp == null) return false;

                if (temp.Data == item) return true;

                if (item > temp.Data)

                {

                    temp = temp.RightChild;

                }

                else

                {

                    temp = temp.LeftChild;

                }

            }

        }


        public bool Delete(int item)

        {

            BSNode temp = root;

            while (true)

            {

                if (temp == null) return false;

                if (temp.Data == item)

                {

                    Delete(temp);

                    return true;

                }

                if (item > temp.Data)

                {

                    temp = temp.RightChild;

                }

                else

                {

                    temp = temp.LeftChild;

                }

            }

        }


        public void Delete(BSNode node)

        {

            //叶子结点,即无子树情况

            if (node.LeftChild == null && node.RightChild == null)

            {

                if (node.Parent == null)

                {

                    root = null;

                }

                else if (node.Parent.LeftChild == node)

                {

                    node.Parent.LeftChild = null;

                }

                else if (node.Parent.RightChild == node)

                {

                    node.Parent.RightChild = null;

                }

                return;

            }


            //只有右子树的情况

            if (node.LeftChild == null && node.RightChild != null)

            {

                node.Data = node.RightChild.Data;

                node.RightChild = null;

                return;

            }

            //只有左子树的情况

            if (node.LeftChild != null && node.RightChild == null)

            {

                node.Data = node.LeftChild.Data;

                node.LeftChild = null;

                return;

            }


            //删除的结点有左,右子树

            BSNode temp = node.RightChild;

            while (true)

            {

                if (temp.LeftChild != null)

                {

                    temp = temp.LeftChild;

                }

                else

                {

                    break;

                }

            }

            node.Data = temp.Data;

            Delete(temp);

        }

    }

}


using System;


namespace _2_1_3二叉排序树

{

    /// <summary>

    /// 测试类

    /// </summary>

    class Program

    {

        static void Main(string[] args)

        {

            BSTree tree = new BSTree();

            int[] data = {62,58,28,47,73,99,35,51,93,37 };


            foreach (int item in data)

            {

                tree.Add(item);

            }

            Console.Write("中序遍历的结果:");

            tree.MiddleBianli();


            Console.WriteLine();

            Console.WriteLine("Find-1方法查找62是否存在:" + tree.Find1(62));

            Console.WriteLine("Find-2方法查找62是否存在:" + tree.Find2(62));

            Console.WriteLine("Find-1方法查找63是否存在:" + tree.Find1(63));  

            Console.WriteLine("Find-2方法查找63是否存在:" + tree.Find2(63));


            Console.WriteLine("删除根结点后的结果:");

            tree.Delete(62);

            tree.MiddleBianli();


            Console.ReadKey();

        }

    }

}





作者:Czhenya

链接:https://czhenya.blog.csdn.net/article/details/78887679

来源:CSDN
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。