二叉排序樹的C#實現

寒假回家的時候，看了一下C#語言描述版的數據結構。我只是單純的想，更加熟悉計算機語言，我希望能像是用母語一樣使用計算機語言和計算機交流。很奇怪之前學C語言版本的數據結構，那些算法我都不是非常理解，但在讀這本書的時候，卻有種豁然開朗的感覺。是書寫的好還是我能力有所提高亦或是兩者皆有？

進入正題。

二叉排序樹說起來其實並不是很難。二叉查找樹是一種把值比較小的節點存儲在左子節點內而值比較大的節點存儲在右子節點裡的樹。其基本操作有以下幾種：

插入

我們對這個二叉樹插入節點。如果二叉樹本身沒有任何節點，那麼插入的這個節點就成為根節點；否則，根據定義，你應該遍歷樹，找出某一個節點，如果帶插入節點的值大於這個節點，則成為帶插入節點的右節點，否則就是左節點。從這裡看來，根節點本身就是一個樹的節點。因此，我首先實現了一個TreeNode類型，如下：

   1: public class TreeNode<T>:IComparable,IComparable<TreeNode<T>> {

   2:  

   3:         #region .ctor 串聯構造函數

   4:  

   5:         public TreeNode():this(default(T),null,null,0){

   6:         }

   7:  

   8:         public TreeNode(T value):this(value,null,null,1) {

   9:         }

  10:  

  11:         public TreeNode(T value,TreeNode<T> leftNode,TreeNode<T> rightNode):this(value,leftNode,rightNode,1) {

  12:         }

  13:  

  14:         public TreeNode(T value, TreeNode<T> leftNode, TreeNode<T> rightNode, int deepness) {

  15:             Value = value;

  16:             LeftNode = leftNode;

  17:             RightNode = rightNode;

  18:             Deepness = deepness;

  19:             IsLeaf = true; 

  20:         }

  21:  

  22:         public override string ToString() {

  23:             return Value.ToString();

  24:         }

  25:  

  26:         #endregion 

  27:  

  28:         #region Interface Members

  29:  

  30:         int IComparable.CompareTo(Object item) {

  31:             TreeNode<T> node = item as TreeNode<T>;

  32:             if (node == null)

  33:                 throw new ArgumentException("Argument for comparing is not a object of TreeNode Type !!");

  34:             else {

  35:                 if (this == item)

  36:                     return 0;

  37:                 else {

  38:                     Comparer comparer = new Comparer(CultureInfo.CurrentCulture);

  39:                     return comparer.Compare(this.Value, node.Value);

  40:                 }

  41:             }

  42:         }