C#实现二叉排序树代码实例

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

• 若它的左子树不为空。则左子树上所有的结点的值均小于跟的结点值
• 若它的右子树部位空，则右子树的所有结点值均大于它的根结点的值
• 它的左右子树也分别是二叉排序树

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

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

namespace _2_1_3二叉排序树
{
  /// 

  /// 结点类
  /// 
  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二叉排序树
{
  /// 

  /// 二叉排序树
  /// 
  class BSTree
  {
    BSNode root = null;
    /// 

    /// 添加数据
    /// 
    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;
     }
   }
 }
      }
    }
    /// 

    /// 中序遍历二叉树
    /// 
    public void MiddleBianli()
    {
      MiddleBianli(root);
    }
    //递归方式中序遍历树
    private void MiddleBianli(BSNode node)
    {
      if (node == null) return;
      MiddleBianli(node.LeftChild);
      Console.Write(node.Data + " ");
      MiddleBianli(node.RightChild);
    }
    /// 

    ///查找方法-1
    /// 
    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);
 }
      }
    }
    /// 

    /// 查找方法-2
    /// 
    /// 
    /// 
    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二叉排序树
{
  /// 

  /// 测试类
  /// 
  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();
    }
  }
}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对考高分网的支持。如果你想了解更多相关内容请查看下面相关链接