// 定义树节点类

namespace 搜索二叉树
{
    public class TreeNode
    {
        public int Value { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
    
        public TreeNode(int value)
        {
            Value = value;
            Left = null;
            Right = null;
        }
    }
    
    // 定义二叉搜索树类
    public class BinarySearchTree
    {
        //定义的根节点
        private TreeNode _root;
    
        // 公开的插入方法入口
        
        //当我们执行了插入子方法时 会去主动调用InsertRecursive方法
        public void Insert(int value)
        {
            _root = InsertRecursive(_root, value);
        }
    
        // 递归插入实现
        /// <summary>
        /// 
        /// </summary>
        /// <param name="node">想插入的树节点</param>
        /// <param name="value">插入的值</param>
        /// <returns></returns>
        private TreeNode InsertRecursive(TreeNode node, int value)
        {
            // 创建新节点并且结束递归
            if (node == null)
            {
                return new TreeNode(value);
            }
    
            // 递归查找插入位置
            if (value < node.Value)
            {
                node.Left = InsertRecursive(node.Left, value);
            }
            else if (value > node.Value)
            {
                node.Right = InsertRecursive(node.Right, value);
            }
    
            return node; // 返回当前节点（处理重复值时直接返回）
        }
    
        // 示例：中序遍历验证树结构
        public void InOrderTraversal()
        {
            InOrderRecursive(_root);
            Console.WriteLine();
        }
    
        private void InOrderRecursive(TreeNode node)
        {
            if (node != null)
            {
                InOrderRecursive(node.Left);
                Console.Write(node.Value + " ");
                InOrderRecursive(node.Right);
            }
        }
    }
    
    // 使用示例
    class Program
    {
        static void Main()
        {
            var bst = new BinarySearchTree();
            int[] values = { 5, 3, 7, 2, 4 };
    
            // 插入数据
            foreach (var val in values)
            {
                bst.Insert(val);
            }
    
            // 验证中序遍历结果（应为升序）
            Console.Write("In-order traversal: ");
            bst.InOrderTraversal();  // 输出: 2 3 4 5 7
        }
    }
}