快捷導(dǎo)航

C#二叉搜索樹(shù)算法實(shí)現(xiàn)步驟和實(shí)例代碼

更新時(shí)間：2024年08月21日 08:58:28 作者：追逐時(shí)光者

二叉搜索樹(shù)（Binary?Search?Tree,簡(jiǎn)稱(chēng)BST）是一種節(jié)點(diǎn)有序排列的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu),這篇文章主要介紹了C#二叉搜索樹(shù)算法實(shí)現(xiàn)步驟和實(shí)例代碼,需要的朋友可以參考下

二叉搜索樹(shù)算法實(shí)現(xiàn)原理

二叉搜索樹(shù)（Binary Search Tree，簡(jiǎn)稱(chēng)BST）是一種節(jié)點(diǎn)有序排列的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)。它具有以下性質(zhì)：

每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。
對(duì)于每個(gè)節(jié)點(diǎn)，其左子樹(shù)的所有節(jié)點(diǎn)值都小于該節(jié)點(diǎn)值，其右子樹(shù)的所有節(jié)點(diǎn)值都大于該節(jié)點(diǎn)值。

實(shí)現(xiàn)基本步驟和代碼示例

步驟

定義節(jié)點(diǎn)類(lèi)：包含節(jié)點(diǎn)值、左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
插入節(jié)點(diǎn)：遞歸或迭代地將新值插入到樹(shù)中合適的位置。
搜索節(jié)點(diǎn)：根據(jù)節(jié)點(diǎn)值在樹(shù)中查找特定值。
刪除節(jié)點(diǎn)：從樹(shù)中刪除特定值的節(jié)點(diǎn)，并維護(hù)樹(shù)的結(jié)構(gòu)。
遍歷樹(shù)：包括前序遍歷、中序遍歷、后序遍歷和層次遍歷等。

完整代碼示例

namespace HelloDotNetGuide.常見(jiàn)算法
{
    public class 二叉搜索樹(shù)算法
    {
        public static void BinarySearchTreeRun()
        {
            var bst = new BinarySearchTree();
            // 插入一些值到樹(shù)中
            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("中序遍歷（打印有序數(shù)組）：");
            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");
            // 刪除某個(gè)值
            bst.Delete(50);
            Console.WriteLine("刪除50后：");
            bst.InorderTraversal();
        }
    }
    /// <summary>
    /// 定義二叉搜索樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)
    /// </summary>
    public class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;
        public TreeNode(int value)
        {
            Value = value;
            Left = null;
            Right = null;
        }
    }
    /// <summary>
    /// 定義二叉搜索樹(shù)類(lèi)
    /// </summary>
    public class BinarySearchTree
    {
        private TreeNode root;
        public BinarySearchTree()
        {
            root = null;
        }
        #region 插入節(jié)點(diǎn)
        /// <summary>
        /// 插入新值到二叉搜索樹(shù)中
        /// </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
            {
                //值已經(jīng)存在于樹(shù)中，不再插入
                return;
            }
        }
        #endregion
        #region 查找節(jié)點(diǎn)
        /// <summary>
        /// 查找某個(gè)值是否存在于二叉搜索樹(shù)中
        /// </summary>
        /// <param name="value">value</param>
        /// <returns></returns>
        public bool Search(int value)
        {
            return SearchRec(root, value);
        }
        private bool SearchRec(TreeNode node, int value)
        {
            // 如果當(dāng)前節(jié)點(diǎn)為空，表示未找到目標(biāo)值
            if (node == null)
            {
                return false;
            }
            // 如果找到目標(biāo)值，返回true
            if (node.Value == value)
            {
                return true;
            }
            // 遞歸查找左子樹(shù)或右子樹(shù)
            if (value < node.Value)
            {
                return SearchRec(node.Left, value);
            }
            else
            {
                return SearchRec(node.Right, value);
            }
        }
        #endregion
        #region 中序遍歷
        /// <summary>
        /// 中序遍歷（打印有序數(shù)組）
        /// </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 刪除節(jié)點(diǎn)
        /// <summary>
        /// 刪除某個(gè)值
        /// </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
            {
                // 節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
                if (node.Left != null && node.Right != null)
                {
                    // 使用右子樹(shù)中的最小節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn)
                    TreeNode minNode = FindMin(node.Right);
                    node.Value = minNode.Value;
                    node.Right = DeleteNode(node.Right, minNode.Value);
                }
                // 節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)或沒(méi)有子節(jié)點(diǎn)
                else
                {
                    TreeNode? temp = node.Left != null ? node.Left : node.Right;
                    node = temp;
                }
            }
            return node;
        }
        /// <summary>
        /// 找到樹(shù)中的最小節(jié)點(diǎn)
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private TreeNode FindMin(TreeNode node)
        {
            while (node.Left != null)
            {
                node = node.Left;
            }
            return node;
        }
        #endregion
    }
}

輸出結(jié)果：