首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

C#二叉搜索树算法

编程知识
2024年08月21日 06:58

二叉搜索树算法实现原理

二叉搜索树(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
    }
}

输出结果:

数组与搜索树的效率对比

二叉搜索树的各项操作的时间复杂度都是对数阶,具有稳定且高效的性能。只有在高频添加、低频查找删除数据的场景下,数组比二叉搜索树的效率更高。

二叉搜索树常见应用

  • 用作系统中的多级索引,实现高效的查找、插入、删除操作。
  • 作为某些搜索算法的底层数据结构。
  • 用于存储数据流,以保持其有序状态。

C#数据结构与算法实战入门指南

参考文章

From:https://www.cnblogs.com/Can-daydayup/p/18370820
本文地址: http://www.shuzixingkong.net/article/1288
0评论
提交 加载更多评论
其他文章 [rCore学习笔记 025]分时多任务系统与抢占式调度
写在前面 本随笔是非常菜的菜鸡写的。如有问题请及时提出。 可以联系:1160712160@qq.com GitHhub:https://github.com/WindDevil (目前啥也没有 本节重点 本章最开始的时候讲解了有类似于多道程序与协作式调度的区别. 回想上一节,我们提到的,如果我们仍然
[rCore学习笔记 025]分时多任务系统与抢占式调度
变分信息瓶颈 (Variational Information Bottleneck) 公式推导
互信息 互信息用于表示两个随机变量相互依赖的程度。随机变量 \(X\) 和 \(Y\) 的互信息定义为 \[\begin{aligned} I(X, Y) &amp; = \mathrm{KL}[p(\boldsymbol{x}, \boldsymbol{y}) \parallel p(\bolds
变分信息瓶颈 (Variational Information Bottleneck) 公式推导
BST 二叉搜索树 BinarySearchTree C++实现(递归/非递归)
目录二叉搜索树基本概念常用结论用途二叉搜索树的性能分析二叉搜索树的操作查找插入删除代码实现BSTree.hpptest.cc 二叉搜索树 基本概念 二叉搜索树(BST,Binary Search Tree) 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空
BST 二叉搜索树 BinarySearchTree C++实现(递归/非递归) BST 二叉搜索树 BinarySearchTree C++实现(递归/非递归) BST 二叉搜索树 BinarySearchTree C++实现(递归/非递归)
Volatile关键字
背景 volatile关键字是并发编程中的一个比较重要的关键字。它能保证变量/对象在内存中的可见性,同时禁止指令重排序,避免了CPU或者编译器优化带来的可见性问题。 在并发编程中,volatile可以去修饰一个变量,或者是一个对象(比如单例模式中就使用了volatile去修饰单例对象) 举例说明 v
为何AI更懂你:向量搜索,了解一下!
现在,你有没有发现自己越来越多地依赖推荐系统,有时候自己搜到的结果好像还没有AI推荐的精准。 那估计有人好奇了,推荐系统怎么这么“聪明”的呢?答案就是:“向量搜索”。今天,我们来聊聊这个技术,看看它是怎么改变了我们获取信息的方式的。 1、向量搜索是什么鬼? 首先,向量搜索到底是什么呢?简单来说,它是
为何AI更懂你:向量搜索,了解一下!
sign_and_send_pubkey: signing failed: agent refused operation
报错描述 ssh连接远程主机时,出现 sign_and_send_pubkey: signing failed: agent refused operation 错误,并且还是需要输入密码 实验环境 Master [root@kvm-master ~]# ssh-copy-id -i .ssh/id
sign_and_send_pubkey: signing failed: agent refused operation sign_and_send_pubkey: signing failed: agent refused operation sign_and_send_pubkey: signing failed: agent refused operation
智能客服的演变:从传统到向量数据库的新时代
向量数据库的崛起,为传统数据库提供了强有力的补充。它的优势在于处理复杂数据和高维数据时的高效性,尤其是在大规模数据分析、实时检索和智能推荐等领域表现突出。传统数据库在结构化数据和事务管理方面表现优异,但在非结构化数据处理、语义搜索和机器学习任务中的局限性逐渐显现。向量数据库的出现,不仅推动了数据存储
智能客服的演变:从传统到向量数据库的新时代 智能客服的演变:从传统到向量数据库的新时代 智能客服的演变:从传统到向量数据库的新时代
SearXNG与LLM强强联合:打造用户隐私保护的智能搜索解答流程,隐私无忧,搜索无忧
SearXNG与LLM强强联合:打造用户隐私保护的智能搜索解答流程,隐私无忧,搜索无忧 SearXNG 是一个免费的互联网元搜索引擎,整合了各种搜索服务的结果。用户不会被跟踪,也不会被分析。 github地址:https://github.com/searxng/searxng 项目地址:https
SearXNG与LLM强强联合:打造用户隐私保护的智能搜索解答流程,隐私无忧,搜索无忧 SearXNG与LLM强强联合:打造用户隐私保护的智能搜索解答流程,隐私无忧,搜索无忧 SearXNG与LLM强强联合:打造用户隐私保护的智能搜索解答流程,隐私无忧,搜索无忧