快捷導(dǎo)航

關(guān)于c#二叉樹(shù)的實(shí)現(xiàn)

更新時(shí)間：2013年04月24日 09:34:51 作者：

本篇文章小編為大家介紹，關(guān)于c#二叉樹(shù)的實(shí)現(xiàn)。需要的朋友參考下

本篇純屬娛樂(lè)，源于整理代碼，發(fā)現(xiàn)還曾實(shí)現(xiàn)過(guò)遍歷二叉樹(shù)。

雖然.NET/C#中的各種集合類已經(jīng)實(shí)現(xiàn)了最優(yōu)的排序設(shè)計(jì)，但了解基本的算法實(shí)現(xiàn)有助于軟件開(kāi)發(fā)中的各種權(quán)衡和選擇。
比如，如果你實(shí)現(xiàn)過(guò)B+樹(shù)排序和查找，并將樹(shù)節(jié)點(diǎn)序列化至二進(jìn)制文件塊，則你應(yīng)該已經(jīng)了解了各種數(shù)據(jù)庫(kù)索引的基本設(shè)計(jì)。

什么是二叉樹(shù)？
http://en.wikipedia.org/wiki/Binary_tree

二叉樹(shù)節(jié)點(diǎn)類定義

復(fù)制代碼代碼如下:

View Code 
   /// <summary>
   /// 二叉樹(shù)節(jié)點(diǎn)
   /// </summary>
   /// <typeparam name="T">The item type</typeparam>
   public class BinaryTreeNode<T>
   {
     #region Constructors

     /// <summary>
     /// 二叉樹(shù)節(jié)點(diǎn)
     /// </summary>
     public BinaryTreeNode()
     {
     }

     /// <summary>
     /// 二叉樹(shù)節(jié)點(diǎn)
     /// </summary>
     /// <param name="value">節(jié)點(diǎn)中的值</param>
     public BinaryTreeNode(T value)
     {
       this.Value = value;
     }

     /// <summary>
     /// 二叉樹(shù)節(jié)點(diǎn)
     /// </summary>
     /// <param name="value">節(jié)點(diǎn)中的值</param>
     /// <param name="parent">節(jié)點(diǎn)的父節(jié)點(diǎn)</param>
     public BinaryTreeNode(T value, BinaryTreeNode<T> parent)
     {
       this.Value = value;
       this.Parent = parent;
     }

     /// <summary>
     /// 二叉樹(shù)節(jié)點(diǎn)
     /// </summary>
     /// <param name="value">節(jié)點(diǎn)中的值</param>
     /// <param name="parent">節(jié)點(diǎn)的父節(jié)點(diǎn)</param>
     /// <param name="left">節(jié)點(diǎn)的左節(jié)點(diǎn)</param>
     /// <param name="right">節(jié)點(diǎn)的右節(jié)點(diǎn)</param>
     public BinaryTreeNode(T value, 
       BinaryTreeNode<T> parent, 
       BinaryTreeNode<T> left, 
       BinaryTreeNode<T> right)
     {
       this.Value = value;
       this.Right = right;
       this.Left = left;
       this.Parent = parent;
     }

     #endregion

     #region Properties

     /// <summary>
     /// 節(jié)點(diǎn)值
     /// </summary>
     public T Value { get; set; }

     /// <summary>
     /// 父節(jié)點(diǎn)
     /// </summary>
     public BinaryTreeNode<T> Parent { get; set; }

     /// <summary>
     /// 左節(jié)點(diǎn)
     /// </summary>
     public BinaryTreeNode<T> Left { get; set; }

     /// <summary>
     /// 右節(jié)點(diǎn)
     /// </summary>
     public BinaryTreeNode<T> Right { get; set; }

     /// <summary>
     /// 是否為根節(jié)點(diǎn)
     /// </summary>
     public bool IsRoot { get { return Parent == null; } }

     /// <summary>
     /// 是否為葉子節(jié)點(diǎn)
     /// </summary>
     public bool IsLeaf { get { return Left == null && Right == null; } }

     /// <summary>
     /// 是否為可訪問(wèn)的
     /// </summary>
     internal bool Visited { get; set; }

     #endregion

     #region Public Overridden Functions

     /// <summary>
     /// Returns a <see cref="System.String"/> that represents this instance.
     /// </summary>
     /// <returns>
     /// A <see cref="System.String"/> that represents this instance.
     /// </returns>
     public override string ToString()
     {
       return Value.ToString();
     }

     #endregion
   }

二叉樹(shù)類實(shí)現(xiàn)

復(fù)制代碼代碼如下:

View Code 
   /// <summary>
   /// 二叉樹(shù)
   /// </summary>
   /// <typeparam name="T">二叉樹(shù)中節(jié)點(diǎn)內(nèi)容類型</typeparam>
   [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
   public class BinaryTree<T> : ICollection<T>, IEnumerable<T> where T : IComparable<T>
   {
     #region Constructor

     /// <summary>
     /// 二叉樹(shù)
     /// </summary>
     public BinaryTree()
     {
       NumberOfNodes = 0;
     }

     /// <summary>
     /// 二叉樹(shù)
     /// </summary>
     /// <param name="root">二叉樹(shù)根節(jié)點(diǎn)</param>
     public BinaryTree(BinaryTreeNode<T> root)
       : this()
     {
       this.Root = root;
     }

     #endregion

     #region Properties

     /// <summary>
     /// 樹(shù)的根節(jié)點(diǎn)
     /// </summary>
     public BinaryTreeNode<T> Root { get; set; }

     /// <summary>
     /// 樹(shù)中節(jié)點(diǎn)的數(shù)量
     /// </summary>
     protected int NumberOfNodes { get; set; }

     /// <summary>
     /// 樹(shù)是否為空
     /// </summary>
     public bool IsEmpty { get { return Root == null; } }

     /// <summary>
     /// 獲取樹(shù)中節(jié)點(diǎn)的最小值
     /// </summary>
     public T MinValue
     {
       get
       {
         if (IsEmpty)
           return default(T);

         BinaryTreeNode<T> minNode = Root;
         while (minNode.Left != null)
           minNode = minNode.Left;

         return minNode.Value;
       }
     }

     /// <summary>
     /// 獲取樹(shù)中節(jié)點(diǎn)的最大值
     /// </summary>
     public T MaxValue
     {
       get
       {
         if (IsEmpty)
           return default(T);

         BinaryTreeNode<T> maxNode = Root;
         while (maxNode.Right != null)
           maxNode = maxNode.Right;

         return maxNode.Value;
       }
     }

     #endregion

     #region IEnumerable<T> Members

     /// <summary>
     /// Returns an enumerator that iterates through the collection.
     /// </summary>
     /// <returns>
     /// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see> 
     /// that can be used to iterate through the collection.
     /// </returns>
     public IEnumerator<T> GetEnumerator()
     {
       foreach (BinaryTreeNode<T> node in Traverse(Root))
       {
         yield return node.Value;
       }
     }

     #endregion

     #region IEnumerable Members

     /// <summary>
     /// Returns an enumerator that iterates through a collection.
     /// </summary>
     /// <returns>
     /// An <see cref="T:System.Collections.IEnumerator"/> 
     /// object that can be used to iterate through the collection.
     /// </returns>
     IEnumerator IEnumerable.GetEnumerator()
     {
       foreach (BinaryTreeNode<T> node in Traverse(Root))
       {
         yield return node.Value;
       }
     }

     #endregion

     #region ICollection<T> Members

     /// <summary>
     /// 新增節(jié)點(diǎn)
     /// </summary>
     /// <param name="item">The object to add to the 
     /// <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
     /// <exception cref="T:System.NotSupportedException">The 
     /// <see cref="T:System.Collections.Generic.ICollection`1"></see> 
     /// is read-only.</exception>
     public void Add(T item)
     {
       if (Root == null)
       {
         Root = new BinaryTreeNode<T>(item);
         ++NumberOfNodes;
       }
       else
       {
         Insert(item);
       }
     }

     /// <summary>
     /// 清除樹(shù)
     /// </summary>
     public void Clear()
     {
       Root = null;
     }

     /// <summary>
     /// 樹(shù)中是否包含此節(jié)點(diǎn)
     /// </summary>
     /// <param name="item">The object to locate in the 
     /// <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
     /// <returns>
     /// true if item is found in the 
     /// <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false.
     /// </returns>
     public bool Contains(T item)
     {
       if (IsEmpty)
         return false;

       BinaryTreeNode<T> currentNode = Root;
       while (currentNode != null)
       {
         int comparedValue = currentNode.Value.CompareTo(item);
         if (comparedValue == 0)
           return true;
         else if (comparedValue < 0)
           currentNode = currentNode.Left;
         else
           currentNode = currentNode.Right;
       }

       return false;
     }

     /// <summary>
     /// 將樹(shù)中節(jié)點(diǎn)拷貝至目標(biāo)數(shù)組
     /// </summary>
     /// <param name="array">The array.</param>
     /// <param name="arrayIndex">Index of the array.</param>
     public void CopyTo(T[] array, int arrayIndex)
     {
       T[] tempArray = new T[NumberOfNodes];
       int counter = 0;
       foreach (T value in this)
       {
         tempArray[counter] = value;
         ++counter;
       }
       Array.Copy(tempArray, 0, array, arrayIndex, Count);
     }

     /// <summary>
     /// 樹(shù)中節(jié)點(diǎn)的數(shù)量
     /// </summary>
     public int Count
     {
       get { return NumberOfNodes; }
     }

     /// <summary>
     /// 樹(shù)是否為只讀
     /// </summary>
     public bool IsReadOnly
     {
       get { return false; }
     }

     /// <summary>
     /// 移除節(jié)點(diǎn)
     /// </summary>
     /// <param name="item">節(jié)點(diǎn)值</param>
     /// <returns>是否移除成功</returns>
     public bool Remove(T item)
     {
       BinaryTreeNode<T> node = Find(item);
       if (node == null)
         return false;

       List<T> values = new List<T>();
       foreach (BinaryTreeNode<T> l in Traverse(node.Left))
       {
         values.Add(l.Value);
       }
       foreach (BinaryTreeNode<T> r in Traverse(node.Right))
       {
         values.Add(r.Value);
       }

       if (node.Parent.Left == node)
       {
         node.Parent.Left = null;
       }
       else
       {
         node.Parent.Right = null;
       }

       node.Parent = null;

       foreach (T v in values)
       {
         this.Add(v);
       }

       return true;
     }

     #endregion

     #region Private Functions

     /// <summary>
     /// 查找指定值的節(jié)點(diǎn)
     /// </summary>
     /// <param name="value">指定值</param>
     /// <returns>
     /// 指定值的節(jié)點(diǎn)
     /// </returns>
     protected BinaryTreeNode<T> Find(T value)
     {
       foreach (BinaryTreeNode<T> node in Traverse(Root))
         if (node.Value.Equals(value))
           return node;
       return null;
     }

     /// <summary>
     /// 遍歷樹(shù)
     /// </summary>
     /// <param name="node">遍歷搜索的起始節(jié)點(diǎn)</param>
     /// <returns>
     /// The individual items from the tree
     /// </returns>
     [SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
     protected IEnumerable<BinaryTreeNode<T>> Traverse(BinaryTreeNode<T> node)
     {
       // 遍歷左子樹(shù)
       if (node.Left != null)
       {
         foreach (BinaryTreeNode<T> left in Traverse(node.Left))
           yield return left;
       }

       // 中序遍歷二叉樹(shù), 順序是 左子樹(shù)，根，右子樹(shù)
       yield return node;

       // 遍歷右子樹(shù)
       if (node.Right != null)
       {
         foreach (BinaryTreeNode<T> right in Traverse(node.Right))
           yield return right;
       }
     }

     /// <summary>
     /// 插入節(jié)點(diǎn)
     /// </summary>
     /// <param name="value">插入的節(jié)點(diǎn)值</param>
     protected void Insert(T value)
     {
       // 從根節(jié)點(diǎn)開(kāi)始比較
       BinaryTreeNode<T> currentNode = Root;

       while (true)
       {
         if (currentNode == null)
           throw new InvalidProgramException("The current tree node cannot be null.");

         // 比較當(dāng)前節(jié)點(diǎn)與新節(jié)點(diǎn)的值
         int comparedValue = currentNode.Value.CompareTo(value);
         if (comparedValue < 0)
         {
           // 當(dāng)前節(jié)點(diǎn)值小于新節(jié)點(diǎn)值
           if (currentNode.Left == null)
           {
             currentNode.Left = new BinaryTreeNode<T>(value, currentNode);
             ++NumberOfNodes;
             return;
           }
           else
           {
             currentNode = currentNode.Left;
           }
         }
         else if (comparedValue > 0)
         {
           // 當(dāng)前節(jié)點(diǎn)值大于新節(jié)點(diǎn)值
           if (currentNode.Right == null)
           {
             currentNode.Right = new BinaryTreeNode<T>(value, currentNode);
             ++NumberOfNodes;
             return;
           }
           else
           {
             currentNode = currentNode.Right;
           }
         }
         else
         {
           // 當(dāng)前節(jié)點(diǎn)值等于新節(jié)點(diǎn)值
           currentNode = currentNode.Right;
         }
       }
     }

     #endregion
   }

使用舉例

復(fù)制代碼代碼如下:

class Program
   {
     static void Main(string[] args)
     {
       Console.ForegroundColor = ConsoleColor.Green;

       BinaryTree<string> tree = new BinaryTree<string>();
       tree.Add("Dennis");
       tree.Add("Gao");
       tree.Add("Is");
       tree.Add("A");
       tree.Add("C#");
       tree.Add("Programmer");

       Console.WriteLine("Root Node Is : " + tree.Root.ToString());
       Console.WriteLine();

       foreach (var node in tree)
       {
         Console.WriteLine(node);
       }

       Console.ReadKey();
     }
   }