欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2024年08月21日 08:58:28   作者:追逐時光者  
二叉搜索樹(Binary?Search?Tree,簡稱BST)是一種節(jié)點有序排列的二叉樹數(shù)據(jù)結(jié)構(gòu),這篇文章主要介紹了C#二叉搜索樹算法實現(xiàn)步驟和實例代碼,需要的朋友可以參考下

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

二叉搜索樹(Binary Search Tree,簡稱BST)是一種節(jié)點有序排列的二叉樹數(shù)據(jù)結(jié)構(gòu)。它具有以下性質(zhì):

  • 每個節(jié)點最多有兩個子節(jié)點。
  • 對于每個節(jié)點,其左子樹的所有節(jié)點值都小于該節(jié)點值,其右子樹的所有節(jié)點值都大于該節(jié)點值。

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

步驟

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

完整代碼示例

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("中序遍歷(打印有序數(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");
            // 刪除某個值
            bst.Delete(50);
            Console.WriteLine("刪除50后:");
            bst.InorderTraversal();
        }
    }
    /// <summary>
    /// 定義二叉搜索樹的節(jié)點結(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>
    /// 定義二叉搜索樹類
    /// </summary>
    public class BinarySearchTree
    {
        private TreeNode root;
        public BinarySearchTree()
        {
            root = null;
        }
        #region 插入節(jié)點
        /// <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
            {
                //值已經(jīng)存在于樹中,不再插入
                return;
            }
        }
        #endregion
        #region 查找節(jié)點
        /// <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)
        {
            // 如果當(dāng)前節(jié)點為空,表示未找到目標(biāo)值
            if (node == null)
            {
                return false;
            }
            // 如果找到目標(biāo)值,返回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>
        /// 中序遍歷(打印有序數(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é)點
        /// <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
            {
                // 節(jié)點有兩個子節(jié)點
                if (node.Left != null && node.Right != null)
                {
                    // 使用右子樹中的最小節(jié)點替換當(dāng)前節(jié)點
                    TreeNode minNode = FindMin(node.Right);
                    node.Value = minNode.Value;
                    node.Right = DeleteNode(node.Right, minNode.Value);
                }
                // 節(jié)點有一個子節(jié)點或沒有子節(jié)點
                else
                {
                    TreeNode? temp = node.Left != null ? node.Left : node.Right;
                    node = temp;
                }
            }
            return node;
        }
        /// <summary>
        /// 找到樹中的最小節(jié)點
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private TreeNode FindMin(TreeNode node)
        {
            while (node.Left != null)
            {
                node = node.Left;
            }
            return node;
        }
        #endregion
    }
}

輸出結(jié)果:

數(shù)組與搜索樹的效率對比

二叉搜索樹的各項操作的時間復(fù)雜度都是對數(shù)階,具有穩(wěn)定且高效的性能。只有在高頻添加、低頻查找刪除數(shù)據(jù)的場景下,數(shù)組比二叉搜索樹的效率更高。

二叉搜索樹常見應(yīng)用

  • 用作系統(tǒng)中的多級索引,實現(xiàn)高效的查找、插入、刪除操作。
  • 作為某些搜索算法的底層數(shù)據(jù)結(jié)構(gòu)。
  • 用于存儲數(shù)據(jù)流,以保持其有序狀態(tài)。

C#數(shù)據(jù)結(jié)構(gòu)與算法實戰(zhàn)入門指南

參考文章

到此這篇關(guān)于C#二叉搜索樹算法的文章就介紹到這了,更多相關(guān)C#二叉搜索樹算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 詳解C#中的session用法

    詳解C#中的session用法

    這篇文章主要介紹了C#中的session用法 ,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-04-04
  • 深入理解C#的數(shù)組

    深入理解C#的數(shù)組

    本篇文章主要介紹了C#的數(shù)組,數(shù)組是一種數(shù)據(jù)結(jié)構(gòu),詳細的介紹了數(shù)組的聲明和訪問等,有興趣的可以了解一下。
    2016-11-11
  • C#實現(xiàn)拼圖游戲

    C#實現(xiàn)拼圖游戲

    這篇文章主要為大家詳細介紹了C#實現(xiàn)拼圖游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-07-07
  • 詳解MongoDB for C#基礎(chǔ)入門

    詳解MongoDB for C#基礎(chǔ)入門

    本篇文章主要介紹了MongoDB for C#基礎(chǔ)入門,具體介紹了c#中關(guān)于對MongoDB的連接,插入,查詢等,有需要的可以了解一下。
    2016-12-12
  • Unity實現(xiàn)卡片循環(huán)滾動效果的示例詳解

    Unity實現(xiàn)卡片循環(huán)滾動效果的示例詳解

    這篇文章主要為大家詳細介紹了如何利用Unity實現(xiàn)卡片循環(huán)滾動的效果,文中的實現(xiàn)步驟講解詳細,具有一定的借鑒價值,需要的可以參考一下
    2022-12-12
  • C#連接Excel驅(qū)動與示例代碼分享

    C#連接Excel驅(qū)動與示例代碼分享

    這篇文章主要介紹了C#連接Excel驅(qū)動與示例代碼,需要的朋友可以參考下
    2014-02-02
  • C#使用DateTime.Now靜態(tài)屬性動態(tài)獲得系統(tǒng)當(dāng)前日期和時間

    C#使用DateTime.Now靜態(tài)屬性動態(tài)獲得系統(tǒng)當(dāng)前日期和時間

    本文主要介紹了C#使用DateTime.Now靜態(tài)屬性動態(tài)獲得系統(tǒng)當(dāng)前日期和時間,DateTime結(jié)構(gòu)的Now靜態(tài)屬性只是得到一個系統(tǒng)時間對象,該時間對象不會隨著系統(tǒng)時間的變化而變化,如果要動態(tài)顯示系統(tǒng)時間,可以使用計時器間隔地獲取系統(tǒng)時間對象并顯示,感興趣的可以了解一下
    2024-01-01
  • 簡介Winform中創(chuàng)建用戶控件

    簡介Winform中創(chuàng)建用戶控件

    用戶控件可以讓開發(fā)人員對VS控件進行組裝。下面我們來創(chuàng)建一個按鈕的用戶控件我們可以給它添加屬性,并且添加相應(yīng)鼠標(biāo)移入、移出事件。
    2013-03-03
  • C#中事件的定義和使用

    C#中事件的定義和使用

    在使用事件時,通常要定義兩個方法,一個是和事件定義的委托簽名一致的方法。下面讓我們看看使用事件的具體步驟。
    2016-06-06
  • C#實現(xiàn)一鍵清空控件值的示例代碼

    C#實現(xiàn)一鍵清空控件值的示例代碼

    這篇文章主要為大家詳細介紹了如何利用C#語言實現(xiàn)一鍵清空控件值的功能,文中的示例代碼講解詳細,對我們學(xué)習(xí)C#有一定幫助,需要的可以參考一下
    2022-09-09

最新評論