namespace _2_1_3二叉排序樹{  /// <summary>  /// 結(jié)點類  /// </summary>  class BSNode  {    //結(jié)點    public BSNode LeftChild { get; set; }    public BSNode RightChild { get; set; }    public BSNode Parent { get; set; }    public int Data { get; set; }    // 構(gòu)造方法    public BSNode(){}    public BSNode(int item)    {      this.Data = item;    }  }}using System;namespace _2_1_3二叉排序樹{  /// <summary>  /// 二叉排序樹  /// </summary>  class BSTree  {    BSNode root = null;    /// <summary>    /// 添加數(shù)據(jù)    /// </summary>    public void Add(int item)    {      //創(chuàng)建新結(jié)點      BSNode newNode = new BSNode(item);      if (root == null)     //若為空，則創(chuàng)建為根結(jié)點      {        root = newNode;      }      else      {        BSNode temp = root;        while (true)        {          if (item >= temp.Data) //放在temp結(jié)點的右邊          {            if (temp.RightChild == null)            {              temp.RightChild = newNode;              newNode.Parent = temp;              break;            }            else            {              temp = temp.RightChild;            }          }          else          //放在temp結(jié)點的左邊          {            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)    {      //葉子結(jié)點，即無子樹情況      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;      }      //刪除的結(jié)點有左，右子樹      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("中序遍歷的結(jié)果：");      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("刪除根結(jié)點后的結(jié)果：");      tree.Delete(62);      tree.MiddleBianli();      Console.ReadKey();    }  }}