C#二叉搜索树算法实现步骤和实例代码_C#

二叉搜索树算法实现原理

二叉搜索树（binary search tree，简称bst）是一种节点有序排列的二叉树数据结构。它具有以下性质：

每个节点最多有两个子节点。
对于每个节点，其左子树的所有节点值都小于该节点值，其右子树的所有节点值都大于该节点值。

实现基本步骤和代码示例

步骤

定义节点类：包含节点值、左子节点和右子节点。
插入节点：递归或迭代地将新值插入到树中合适的位置。
搜索节点：根据节点值在树中查找特定值。
删除节点：从树中删除特定值的节点，并维护树的结构。
遍历树：包括前序遍历、中序遍历、后序遍历和层次遍历等。

完整代码示例

namespace hellodotnetguide.常见算法
{
    public class 二叉搜索树算法
    {
        public static void binarysearchtreerun()
        {
            var bst = new binarysearchtree();
            // 插入一些值到树中
            bst.insert(50);
            bst.insert(30);
            bst.insert(20);
            bst.insert(40);
            bst.insert(70);
            bst.insert(60);
            bst.insert(80);
            bst.insert(750);
            console.writeline("中序遍历（打印有序数组）：");
            bst.inordertraversal();
            console.writeline("\n");
            // 查找某些值
            console.writeline("search for 40: " + bst.search(40)); // 输出: true
            console.writeline("search for 25: " + bst.search(25)); // 输出: false
            console.writeline("\n");
            // 删除某个值
            bst.delete(50);
            console.writeline("删除50后：");
            bst.inordertraversal();
        }
    }
    /// <summary>
    /// 定义二叉搜索树的节点结构
    /// </summary>
    public class treenode
    {
        public int value;
        public treenode left;
        public treenode right;
        public treenode(int value)
        {
            value = value;
            left = null;
            right = null;
        }
    }
    /// <summary>
    /// 定义二叉搜索树类
    /// </summary>
    public class binarysearchtree
    {
        private treenode root;
        public binarysearchtree()
        {
            root = null;
        }
        #region 插入节点
        /// <summary>
        /// 插入新值到二叉搜索树中
        /// </summary>
        /// <param name="value">value</param>
        public void insert(int value)
        {
            if (root == null)
            {
                root = new treenode(value);
            }
            else
            {
                insertrec(root, value);
            }
        }
        private void insertrec(treenode node, int value)
        {
            if (value < node.value)
            {
                if (node.left == null)
                {
                    node.left = new treenode(value);
                }
                else
                {
                    insertrec(node.left, value);
                }
            }
            else if (value > node.value)
            {
                if (node.right == null)
                {
                    node.right = new treenode(value);
                }
                else
                {
                    insertrec(node.right, value);
                }
            }
            else
            {
                //值已经存在于树中，不再插入
                return;
            }
        }
        #endregion
        #region 查找节点
        /// <summary>
        /// 查找某个值是否存在于二叉搜索树中
        /// </summary>
        /// <param name="value">value</param>
        /// <returns></returns>
        public bool search(int value)
        {
            return searchrec(root, value);
        }
        private bool searchrec(treenode node, int value)
        {
            // 如果当前节点为空，表示未找到目标值
            if (node == null)
            {
                return false;
            }
            // 如果找到目标值，返回true
            if (node.value == value)
            {
                return true;
            }
            // 递归查找左子树或右子树
            if (value < node.value)
            {
                return searchrec(node.left, value);
            }
            else
            {
                return searchrec(node.right, value);
            }
        }
        #endregion
        #region 中序遍历
        /// <summary>
        /// 中序遍历（打印有序数组）
        /// </summary>
        public void inordertraversal()
        {
            inordertraversalrec(root);
        }
        private void inordertraversalrec(treenode root)
        {
            if (root != null)
            {
                inordertraversalrec(root.left);
                console.writeline(root.value);
                inordertraversalrec(root.right);
            }
        }
        #endregion
        #region 删除节点
        /// <summary>
        /// 删除某个值
        /// </summary>
        /// <param name="val">val</param>
        public void delete(int val)
        {
            root = deletenode(root, val);
        }
        private treenode deletenode(treenode node, int val)
        {
            if (node == null)
            {
                return null;
            }
            if (val < node.value)
            {
                node.left = deletenode(node.left, val);
            }
            else if (val > node.value)
            {
                node.right = deletenode(node.right, val);
            }
            else
            {
                // 节点有两个子节点
                if (node.left != null && node.right != null)
                {
                    // 使用右子树中的最小节点替换当前节点
                    treenode minnode = findmin(node.right);
                    node.value = minnode.value;
                    node.right = deletenode(node.right, minnode.value);
                }
                // 节点有一个子节点或没有子节点
                else
                {
                    treenode? temp = node.left != null ? node.left : node.right;
                    node = temp;
                }
            }
            return node;
        }
        /// <summary>
        /// 找到树中的最小节点
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private treenode findmin(treenode node)
        {
            while (node.left != null)
            {
                node = node.left;
            }
            return node;
        }
        #endregion
    }
}

输出结果：