C#如何实现二叉排序树

这篇文章主要介绍了C#如何实现二叉排序树，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

二叉排序树，又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：

• 若它的左子树不为空。则左子树上所有的结点的值均小于跟的结点值

• 若它的右子树部位空，则右子树的所有结点值均大于它的根结点的值

• 它的左右子树也分别是二叉排序树

1，排序方便
2，查找方便
3，便于插入和删除

C#链式存储二叉排序树，实现简单的排序，以及查找，具体代码如下：

namespace _2_1_3二叉排序树
{
  /// <summary>
  /// 结点类
  /// </summary>
  class BSNode
  {
    //结点
    public BSNode LeftChild { get; set; }
    public BSNode RightChild { get; set; }
    public BSNode Parent { get; set; }
    public int Data { get; set; }
    // 构造方法
    public BSNode(){}
    public BSNode(int item)
    {
      this.Data = item;
    }
  }
}
using System;
namespace _2_1_3二叉排序树
{
  /// <summary>
  /// 二叉排序树
  /// </summary>
  class BSTree
  {
    BSNode root = null;
    /// <summary>
    /// 添加数据
    /// </summary>
    public void Add(int item)
    {
      //创建新结点
      BSNode newNode = new BSNode(item);
      if (root == null)     //若为空，则创建为根结点
      {
        root = newNode;
      }
      else
      {
        BSNode temp = root;
        while (true)
        {
          if (item >= temp.Data) //放在temp结点的右边
          {
            if (temp.RightChild == null)
            {
              temp.RightChild = newNode;
              newNode.Parent = temp;
              break;
            }
            else
            {
              temp = temp.RightChild;
            }
          }
          else          //放在temp结点的左边
          {
            if (temp.LeftChild == null)
            {
              temp.LeftChild = newNode;
              newNode.Parent = temp;
              break;
            }
            else
            {
              temp = temp.LeftChild;
            }
          }
        }
      }
    }
    /// <summary>
    /// 中序遍历二叉树
    /// </summary>
    public void MiddleBianli()
    {
      MiddleBianli(root);
    }
    //递归方式中序遍历树
    private void MiddleBianli(BSNode node)
    {
      if (node == null) return;
      MiddleBianli(node.LeftChild);
      Console.Write(node.Data + " ");
      MiddleBianli(node.RightChild);
    }
    /// <summary>
    ///查找方法-1
    /// </summary>
    public bool Find1(int item)
    {
      return Find(item, root);
    }
    private bool Find(int item, BSNode node)
    {
      if (node == null) { return false; }
      if (node.Data == item)
      {
        return true;
      }
      else
      {
        //利用二叉排序树的便利
        if (item > node.Data)
        {
          return Find(item, node.RightChild);
        }
        else
        {
          return Find(item, node.LeftChild);
        }
      }
    }
    /// <summary>
    /// 查找方法-2
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public bool Find2(int item)
    {
      BSNode temp = root;
      while (true)
      {
        if (temp == null) return false;
        if (temp.Data == item) return true;
        if (item > temp.Data)
        {
          temp = temp.RightChild;
        }
        else
        {
          temp = temp.LeftChild;
        }
      }
    }
    public bool Delete(int item)
    {
      BSNode temp = root;
      while (true)
      {
        if (temp == null) return false;
        if (temp.Data == item)
        {
          Delete(temp);
          return true;
        }
        if (item > temp.Data)
        {
          temp = temp.RightChild;
        }
        else
        {
          temp = temp.LeftChild;
        }
      }
    }
    public void Delete(BSNode node)
    {
      //叶子结点，即无子树情况
      if (node.LeftChild == null && node.RightChild == null)
      {
        if (node.Parent == null)
        {
          root = null;
        }
        else if (node.Parent.LeftChild == node)
        {
          node.Parent.LeftChild = null;
        }
        else if (node.Parent.RightChild == node)
        {
          node.Parent.RightChild = null;
        }
        return;
      }
      //只有右子树的情况
      if (node.LeftChild == null && node.RightChild != null)
      {
        node.Data = node.RightChild.Data;
        node.RightChild = null;
        return;
      }
      //只有左子树的情况
      if (node.LeftChild != null && node.RightChild == null)
      {
        node.Data = node.LeftChild.Data;
        node.LeftChild = null;
        return;
      }
      //删除的结点有左，右子树
      BSNode temp = node.RightChild;
      while (true)
      {
        if (temp.LeftChild != null)
        {
          temp = temp.LeftChild;
        }
        else
        {
          break;
        }
      }
      node.Data = temp.Data;
      Delete(temp);
    }
  }
}
using System;
namespace _2_1_3二叉排序树
{
  /// <summary>
  /// 测试类
  /// </summary>
  class Program
  {
    static void Main(string[] args)
    {
      BSTree tree = new BSTree();
      int[] data = {62,58,28,47,73,99,35,51,93,37 };

      foreach (int item in data)
      {
        tree.Add(item);
      }
      Console.Write("中序遍历的结果：");
      tree.MiddleBianli();
      Console.WriteLine();
      Console.WriteLine("Find-1方法查找62是否存在：" + tree.Find1(62));
      Console.WriteLine("Find-2方法查找62是否存在：" + tree.Find2(62));
      Console.WriteLine("Find-1方法查找63是否存在：" + tree.Find1(63)); 
      Console.WriteLine("Find-2方法查找63是否存在：" + tree.Find2(63));
      Console.WriteLine("删除根结点后的结果：");
      tree.Delete(62);
      tree.MiddleBianli();
      Console.ReadKey();
    }
  }
}

C#是什么

C#是一个简单、通用、面向对象的编程语言，它由微软Microsoft开发，继承了C和C++强大功能，并且去掉了一些它们的复杂特性，C#综合了VB简单的可视化操作和C++的高运行效率，以其强大的操作能力、优雅的语法风格、创新的语言特性和便捷的面向组件编程从而成为.NET开发的首选语言，但它不适用于编写时间急迫或性能非常高的代码，因为C#缺乏性能极高的应用程序所需要的关键功能。

感谢你能够认真阅读完这篇文章，希望小编分享的“C#如何实现二叉排序树”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!