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();
      }
    }
  }								 
   1/2    1 2 下一页 尾页