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