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();
   }
 }
}

来源：https://blog.csdn.net/Czhenya/article/details/78887679