二叉搜索树

支持增、删、查。

namespace BinarySearchTree
{
    class Program
    {
        TreeNode rootNode;

        static void Main(string[] args)
        {
            var p = new Program();
            p.Add(new TreeNode(8));
            p.Add(new TreeNode(18));
            p.Add(new TreeNode(28));
            p.Add(new TreeNode(2));
            p.Add(new TreeNode(3));
            p.Add(new TreeNode(4));
            p.Add(new TreeNode(11));
            p.Add(new TreeNode(6));

            var node = p.Search(18);

            p.Delete();
            Console.ReadLine();

            Console.WriteLine("Hello World!");
        }

        public void Add(TreeNode node)
        {
            if (rootNode == null)
            {
                rootNode = node;
            }
            else
            {
                rootNode.Add(node);
            }
        }

        public TreeNode Search(int value)
        {
            return rootNode?.Search(value);
        }

        /// <summary>
        /// 删除根结点
        /// </summary>
        public void Delete()
        {
            if (rootNode.LeftNode == null && rootNode.RightNode == null)
            {
                rootNode = null;
                return;
            }

            if (rootNode.LeftNode != null && rootNode.RightNode != null)
            {
                // 将右结点挂接到左节点最大结点上
                var node = rootNode.LeftNode.GetConnectNode();
                node.RightNode = rootNode.RightNode;
                return;
            }

            if (rootNode.LeftNode == null)
            {
                rootNode = rootNode.RightNode;
                return;
            }

            if (rootNode.RightNode == null)
            {
                rootNode = rootNode.LeftNode;
                return;
            }
        }
    }

    public class TreeNode
    {
        public TreeNode(int data)
        {
            this.Data = data;
        }

        public int? Data;
        public TreeNode LeftNode;
        public TreeNode RightNode;

        public void Add(TreeNode node)
        {
            if (node == null)
                return;

            if (node.Data < this.Data)
            {
                if (this.LeftNode == null)
                    LeftNode = node;
                else
                    this.LeftNode.Add(node);
            }
            else
            {
                if (this.RightNode == null)
                    RightNode = node;
                else
                    this.RightNode.Add(node);
            }
        }

        public TreeNode Search(int value)
        {
            if (this.Data == value)
            {
                return this;
            }
            else if (value < this.Data)
            {
                return this.LeftNode?.Search(value);
            }
            else
            {
                return this.RightNode?.Search(value);
            }
        }

        public TreeNode GetConnectNode()
        {
            if (this.RightNode == null)
            {
                return this;
            }
            else
            {
                return this.RightNode.GetConnectNode();
            }
        }
    }
}