熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> .NET編程 >> 正文

二叉排序樹的C#實現

2013-11-13 10:07:43  來源: .NET編程 

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

  插入

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

  : public class TreeNode<T>:IComparableIComparable<TreeNode<T>> {

  :

  :         #region ctor 串聯構造函數

  :

  :         public TreeNode():this(default(T)nullnull){

  :         }

  :

  :         public TreeNode(T value):this(valuenullnull) {

  :         }

  :

  :         public TreeNode(T valueTreeNode<T> leftNodeTreeNode<T> rightNode):this(valueleftNoderightNode) {

  :         }

  :

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

  :             Value = value;

  :             LeftNode = leftNode;

  :             RightNode = rightNode;

  :             Deepness = deepness;

  :             IsLeaf = true;

  :         }

  :

  :         public override string ToString() {

  :             return ValueToString();

  :         }

  :

  :         #endregion

  :

  :         #region Interface Members

  :

  :         int IComparableCompareTo(Object item) {

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

  :             if (node == null)

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

  :             else {

  :                 if (this == item)

  :                     return ;

  :                 else {

  :                     Comparer comparer = new Comparer(CultureInfoCurrentCulture);

  :                     return comparerCompare(thisValue nodeValue);

  :                 }

  :             }

  :         }

  :

  :         int IComparable<TreeNode<T>>CompareTo(TreeNode<T> item) {

  :             if (item == null) {

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

  :             } else {

  :                 if (this == item)

  :                     return ;

  :                 else {

  :                     Comparer comparer = new Comparer(CultureInfoCurrentCulture);

  :                     return comparerCompare(thisValue itemValue);

  :                 }

  :             }

  :         }

  :         #endregion

  :

  :         #region Properties

  :

  :         public TreeNode<T> LeftNode {

  :             get;

  :             set;

  :         }

  :

  :         public TreeNode<T> RightNode {

  :             get;

  :             set;

  :         }

  :

  :         public TreeNode<T> FatherNode {

  :             get;

  :             set;

  :         }

  :

  :         //這個屬性是指數的層數也就是深度根的深度為

  :         public int Deepness {

  :             get;

  :             set;

  :         }

  :

  :         //這個屬性指示這個節點是不是葉子節點

  :         public bool IsLeaf {

  :             get;

  :             set;

  :         }

  :

  :         //這個屬性返回或者設置該節點的值

  :         public T Value {

  :             get;

  :             set;

  :         }

  :

  :         #endregion

  :     }

  接下來我們就能實現插入的功能了通常我覺得好的代碼是自描述的也就是一段好的代碼應該能自己描述自己的用途的

  : public void Add(T itemValue) {

  :             if (Root == null) {

  :                 TreeNode<T> root = new TreeNode<T>(itemValue);

  :                 thisRoot = root;

  :                 thisCount++;

  :             } else {

  :                 TreeNode<T> _iterator = thisRoot;

  :                 bool okFlag = true;;

  :                 int deepness = ;

  :                 int result = _comparerCompare(itemValue _iteratorValue); ;

  :

  :                 while (okFlag) {

  :                     DebugWriteLine(Comaper Result is : + resultToString());

  :                     DebugWriteLine();

  :                     if (result > ) {

  :                         if (_iteratorRightNode != null) {

  :                             _iterator = _iteratorRightNode;

  :                             result = _comparerCompare(itemValue _iteratorValue);

  :                             deepness++;

  :                         } else {

  :                             //在添加節點的時候就設置該節點的深度而在計算整棵樹的深度的時候其實只要對所有葉節點的深度的值進行排序就可以得到了

  :                             _iteratorRightNode = new TreeNode<T>(itemValuenullnulldeepness);

  :                             _iteratorIsLeaf = false;

  :                             _iteratorRightNodeFatherNode = _iterator;

  :                             Count++;

  :                             okFlag = false;

  :                         }

  :                     } else if (result < ) {

  :                         if (_iteratorLeftNode != null) {

  :                             _iterator = _iteratorLeftNode;

  :                             result = _comparerCompare(itemValue _iteratorValue);

  :                             deepness++;

  :                         } else {

  :                             _iteratorLeftNode = new TreeNode<T>(itemValue null null deepness);

  :                             _iteratorIsLeaf = false;

  :                             _iteratorLeftNodeFatherNode = _iterator;

  :                             Count++;

  :                             okFlag = false;

  :                         }

  :                     } else

  :                         okFlag = false;

  :                 }

  :             }

  :         }

  這裡在比較的時候我是在全局設置了一個與本地文化相關的Comparer類型的私有成員_comparer這個類型用於對象判等關鍵是你要判斷的對象必須實現IComparable 接口我編寫的TreeNode類型就實現了這個接口了

  查找

  根據二叉搜索樹的特點如果你要搜索的節點的值比當前節點值小那麼就再搜索該節點的左子樹否則搜索右子樹這個過程是遞歸過程

  如果找到匹配的節點返回ture;否則當前節點為Null然後又不等於你要搜索的節點的值那麼就直接返回false我的實現如下

  : public bool IsExit(T keyout TreeNode<T> node) {

  :             node = null;

  :             TreeNode<T> _iterator = Root;

  :             int result = _comparerCompare(key _iteratorValue);

  :             bool okFlag = true;

  :             while (okFlag) {

  :                 if (result == ) {

  :                     okFlag = false;

  :                     node = _iterator;//如果找到這個葉子結點那麼得到葉子節點的指針

  :                     return true;

  :                 } else if (result > ) {

  :                     _iterator = _iteratorRightNode;

  :                     if (_iterator != null)

  :                         result = _comparerCompare(key _iteratorValue);

  :                     else {

  :                         okFlag = false;

  :                         return false;

  :                     }

  :                 } else {

  :                     _iterator = _iteratorLeftNode;

  :                     if (_iterator != null)

  :                         result = _comparerCompare(key _iteratorValue);

  :                     else {

  :                         okFlag = false;

  :                         return false;

  :                     }

  :                 }

  :             }

  :             return false;

  :         }

  遍歷

  這個分三種情況的遍歷分別是前根遍歷中根遍歷後根遍歷其實很簡單就是按照訪問節點的順序來劃分的如果先訪問左子節點然後訪問父節點最後在訪問右節點這個情況就是前序遍歷其他的情況以此類推這裡我實現的時候是用遞歸的方式

  : /// <summary>

  : /// 中根遍歷樹

  : /// </summary>

  : /// <param name=root></param>

  : public void InOrder(TreeNode<T> root) {

  :     if (root != null) {

  :         InOrder(rootLeftNode);

  :         ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

  :         InOrder(rootRightNode);

  :     }

  : }

  :

  : /// <summary>

  : /// 先根遍歷樹

  : /// </summary>

  : /// <param name=root></param>

  : public void PreOrder(TreeNode<T> root) {

  :     if (root != null) {

  :         ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

  :         PreOrder(rootLeftNode);

  :         PreOrder(rootRightNode);

  :     }

  : }

  :

  : /// <summary>

  : /// 後根遍歷樹

  : /// </summary>

  : /// <param name=root></param>

  : public void PostOrder(TreeNode<T> root) {

  :     if (root != null) {

  :         PostOrder(rootLeftNode);

  :         PostOrder(rootRightNode);

  :         stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString());

  :     }

  : }

  刪除節點

  作為這個樹的實現裡面最有難度的地方要考慮三種情況

  要刪除的節點時葉子結點這個情況很好解決直接刪掉就好了

  要刪除的節點只有一個子節點這個情況也很好解決子節點替換一下父節點問題解決

  要刪除的節點有兩個節點這個就比較復雜了一些但我們仔細分析就會發現要刪除這個節點只要利用中根遍歷得到直接前驅或者直接後繼結點代替該節點就可以了同時你還要刪除前驅或者後繼這個節點而這兩個節點一定符合前面的兩種情況之一

  : public void Remove(T key) {

  :     TreeNode<T> node;

  :     bool isExit = IsExit(key out node);

  :     if (!isExit) {

  :         return;

  :     } else {

  :         if (IsLeafNode(node)) {

  :             if (nodeFatherNodeLeftNode == node)

  :                 nodeFatherNodeLeftNode = null;

  :             else

  :                 nodeFatherNodeRightNode = null;

  :             if (node != null) node = null;

  :         } else {

  :             if (!HasTwoLeafNodes(node)) {

  :                 TreeNode<T> child = GetUniqueChild(node);

  :                 if (nodeFatherNodeLeftNode == node) {

  :                     nodeFatherNodeLeftNode = child;

  :                 } else {

  :                     if (nodeLeftNode != null)

  :                         nodeFatherNodeRightNode = child;

  :                 }

  :                 if (node != null) node = null;

  :             } else {

  :                 //首先找到後繼結點

  :                 TreeNode<T> successor = GetSuccessor(node);

  :                 //調整節點值這個時候有一個值得注意的地方比如你的樹是這樣的情況

  :                 /*                         或者              

  :                  *             \                                    /

  :                  *                                              

  :                  *             / \                                /  \

  :                  *            /   \                                

  :                  *                                         /  \   /

  :                  *         /  \    / \                           

  :                  *            

  :                  *                  \

  :                  *                  

  :                 */

  :                 //樹A中節點相應的後繼結點應該是那麼的左子節點應調整成就要調整成

  :                 nodeValue = successorValue;

  :                 Remove(successor);

  :             }

  :         }

  :         thisCount;

  :     }

  : }

  以下是完整的代碼盡管是泛型但其實我僅僅使用int類型編寫 過測試如果其他的類型我想只要是實現了IComparable接口應該就能正常工作

  : using System;

  : using SystemCollections;

  : using SystemCollectionsGeneric;

  : using SystemGlobalization;

  : using SystemDiagnostics;

  : using SystemText;

  :

  : namespace Ultis {

  :     public class BinaryTree<T> {

  :         #region ctor

  :

  :         static BinaryTree() {

  :             _comparer = new Comparer(CultureInfoCurrentCulture);

  :         }

  :

  :         public BinaryTree() {

  :             thisRoot = null;

  :             thisCount = ;

  :             this_deepness = ;

  :         }

  :

  :         public BinaryTree(TreeNode<T> root) {

  :             if (root == null) {

  :                 throw new ArgumentException(Root can not be null !!);

  :             }

  :             thisRoot = root;

  :             thisCount++;

  :             this_deepness = ;

  :         }

  :         #endregion

  :

  :         #region Public Members

  :

  :         /// <summary>

  :         ///

  :         /// </summary>

  :         /// <param name=itemValue></param>

  :         public void Add(T itemValue) {

  :             if (Root == null) {

  :                 TreeNode<T> root = new TreeNode<T>(itemValue);

  :                 thisRoot = root;

  :                 thisCount++;

  :             } else {

  :                 TreeNode<T> _iterator = thisRoot;

  :                 bool okFlag = true;;

  :                 int deepness = ;

  :                 int result = _comparerCompare(itemValue _iteratorValue); ;

  :

  :                 while (okFlag) {

  :                     DebugWriteLine(Comaper Result is : + resultToString());

  :                     DebugWriteLine();

  :                     if (result > ) {

  :                         if (_iteratorRightNode != null) {

  :                             _iterator = _iteratorRightNode;

  :                             result = _comparerCompare(itemValue _iteratorValue);

  :                             deepness++;

  :                         } else {

  :                             //在添加節點的時候就設置該節點的深度而在計算整棵樹的深度的時候其實只要對所有葉節點的深度的值進行排序就可以得到了

  :                             _iteratorRightNode = new TreeNode<T>(itemValuenullnulldeepness);

  :                             _iteratorIsLeaf = false;

  :                             _iteratorRightNodeFatherNode = _iterator;

  :                             Count++;

  :                             okFlag = false;

  :                         }

  :                     } else if (result < ) {

  :                         if (_iteratorLeftNode != null) {

  :                             _iterator = _iteratorLeftNode;

  :                             result = _comparerCompare(itemValue _iteratorValue);

  :                             deepness++;

  :                         } else {

  :                             _iteratorLeftNode = new TreeNode<T>(itemValue null null deepness);

  :                             _iteratorIsLeaf = false;

  :                             _iteratorLeftNodeFatherNode = _iterator;

  :                             Count++;

  :                             okFlag = false;

  :                         }

  :                     } else

  :                         okFlag = false;

  :                 }

  :             }

  :         }

  :

  :         /// <summary>

  :         /// 從樹中移出一個節點要考慮很多情況比如要刪除的節點沒有子節點有一個子節點有兩個子節點

  :         /// PS:這個方法應進行測試

  :         /// </summary>

  :           /**

  :           * 刪除指定的節點實現

  :           *

  :           * 算法思想

  :           *

  :           * 若待刪除的節點p是葉子節點則直接刪除該節點

  :           *

  :           * 若待刪除的節點p只有一個子節點則將p的子節點與p的父節點直接連接然後刪除節點p

  :           * 為什麼只有一個子節點時可以直接接到刪除節點的父節點下面呢?因為只有一個子節點直接接上

  :           * 去不會影響排序子節點本身的排序當然更不會影響另外一個子樹(因為另一子樹跟本不存在!)

  :           *

  :           * 若待刪除節點p有兩個子節點時應該使用中序遍歷方式得到的直接前置節點S或直接後繼節點s

  :           * 的值來代替點s的值然後刪除節點s(注節點s肯定屬於上述情況之一)而不是直接刪除

  :           * p這樣可以將該刪除問題轉換成上面問題

  :           */

  :         public void Remove(T key) {

  :             TreeNode<T> node;

  :             bool isExit = IsExit(key out node);

  :             if (!isExit) {

  :                 return;

  :             } else {

  :                 if (IsLeafNode(node)) {

  :                     if (nodeFatherNodeLeftNode == node)

  :                         nodeFatherNodeLeftNode = null;

  :                     else

  :                         nodeFatherNodeRightNode = null;

  :                     if (node != null) node = null;

  :                 } else {

  :                     if (!HasTwoLeafNodes(node)) {

  :                         TreeNode<T> child = GetUniqueChild(node);

  :                         if (nodeFatherNodeLeftNode == node) {

  :                             nodeFatherNodeLeftNode = child;

  :                         } else {

  :                             if (nodeLeftNode != null)

  :                                 nodeFatherNodeRightNode = child;

  :                         }

  :                         if (node != null) node = null;

  :                     } else {

  :                         //首先找到後繼結點

  :                         TreeNode<T> successor = GetSuccessor(node);

  :                         //調整節點值這個時候有一個值得注意的地方比如你的樹是這樣的情況

  :                         /*                         或者              

  :                          *             \                                    /

  :                          *                                              

  :                          *             / \                                /  \

  :                          *            /   \                                

  :                          *                                         /  \   /

  :                          *         /  \    / \                           

  :                          *            

  :                          *                  \

  :                          *                  

  :                         */

  :                         //樹A中節點相應的後繼結點應該是那麼的左子節點應調整成就要調整成

  :                         nodeValue = successorValue;

  :                         Remove(successor);

  :                     }

  :                 }

  :                 thisCount;

  :             }

  :         }

  :

  :

  :         /**

  :          * 刪除指定的節點實現

  :          *

  :          * 算法思想

  :          *

  :          * 若待刪除的節點p是葉子節點則直接刪除該節點

  :          *

  :          * 若待刪除的節點p只有一個子節點則將p的子節點與p的父節點直接連接然後刪除節點p

  :          * 為什麼只有一個子節點時可以直接接到刪除節點的父節點下面呢?因為只有一個子節點直接接上

  :          * 去不會影響排序子節點本身的排序當然更不會影響另外一個子樹(因為另一子樹跟本不存在!)

  :          *

  :          * 若待刪除節點p有兩個子節點時應該使用中序遍歷方式得到的直接前置節點S或直接後繼節點s

  :          * 的值來代替點s的值然後刪除節點s(注節點s肯定屬於上述情況之一)而不是直接刪除

  :          * p這樣可以將該刪除問題轉換成上面問題

  :          */

  :         public void Remove(TreeNode<T> node) {

  :             if (IsLeafNode(node)) {

  :                 if (nodeFatherNodeLeftNode == node)

  :                     nodeFatherNodeLeftNode = null;

  :                 else

  :                     nodeFatherNodeRightNode = null;

  :                 if (node != null) node = null;

  :             } else {

  :                 if (!HasTwoLeafNodes(node)) {

  :                     TreeNode<T> child = GetUniqueChild(node);

  :                     if (nodeFatherNodeLeftNode == node) {

  :                         nodeFatherNodeLeftNode = child;

  :                     } else {

  :                         nodeFatherNodeRightNode = child;

  :                     }

  :                     if(node != null) node = null;

  :                 } else {

  :                     //要刪除的節點有兩個子節點

  :                     TreeNode<T> successor = GetSuccessor(node);

  :                     nodeValue = successorValue;

  :                     Remove(successor); //刪除相應的後繼結點

  :                     if (successor != null) successor = null;

  :                 }

  :             }

  :             thisCount;

  :         }

  :

  :         /// <summary>

  :         /// 返回某一節點唯一的一個節點

  :         /// </summary>

  :         /// <param name=node></param>

  :         /// <returns></returns>

  :         private TreeNode<T> GetUniqueChild(TreeNode<T> node) {

  :             TreeNode<T> child;

  :             if (nodeLeftNode != null)

  :                 child = nodeLeftNode;

  :             else

  :                 child = nodeRightNode;

  :             return child;

  :         }

  :

  :         /// <summary>

  :         /// 根據中根遍歷來得到相應的後繼結點仍然還有BUG存在!

  :         /// </summary>

  :         /// <param name=value></param>

  :         /// <returns></returns>

  :         public TreeNode<T> GetSuccessor(T value) {

  :             throw new NotImplementedException(This function is not complete yet !);

  :             IComparable icomparable = Root as IComparable;

  :             TreeNode<T> wanted = new TreeNode<T>(value);

  :             if (icomparableCompareTo(wanted) == ) {

  :                 return Root;

  :             } else {

  :                 TreeNode<T> node;

  :                 if (IsExit(value out node)) {

  :                     if (IsLeafNode(node)) {  //如果是葉子節點那麼應該做麼做才能返回正確的後繼節點?

  :                         return null;

  :                     }else

  :                         return GetSuccessor(node);  //如果是非葉子節點則調用相應的方法返回非葉子節點的後繼結點

  :                 } else

  :                     return null;

  :             }

  :         }

  :

  :         /// <summary>

  :         /// 中根遍歷樹

  :         /// </summary>

  :         /// <param name=root></param>

  :         public void InOrder(TreeNode<T> root) {

  :             if (root != null) {

  :                 InOrder(rootLeftNode);

  :                 ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

  :                 InOrder(rootRightNode);

  :             }

  :         }

  :

  :         /// <summary>

  :         /// 先根遍歷樹

  :         /// </summary>

  :         /// <param name=root></param>

  :         public void PreOrder(TreeNode<T> root) {

  :             if (root != null) {

  :                 ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

  :                 PreOrder(rootLeftNode);

  :                 PreOrder(rootRightNode);

  :             }

  :         }

  :

  :         /// <summary>

  :         /// 後根遍歷樹

  :         /// </summary>

  :         /// <param name=root></param>

  :         public void PostOrder(TreeNode<T> root) {

  :             if (root != null) {

  :                 PostOrder(rootLeftNode);

  :                 PostOrder(rootRightNode);

  :                 stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString());

  :             }

  :         }

  :

  :         /// <summary>

  :         /// 返回具有最大節點值的樹節點

  :         /// </summary>

  :         /// <returns></returns>

  :         public TreeNode<T> GetMaxNode() {

  :             TreeNode<T> _iterator = Root;

  :             while (_iteratorRightNode != null) {

  :                 _iterator = _iteratorRightNode;

  :             }

  :             return _iterator;

  :         }

  :

  :         /// <summary>

  :         /// 返回最大的值

  :         /// </summary>

  :         /// <returns></returns>

  :         public T GetMaxValue() {

  :             return GetMaxNode()Value;

  :         }

  :

  :         /// <summary>

  :         /// 返回具有最小節點值得節點

  :         /// </summary>

  :         /// <returns></returns>

  :         public TreeNode<T> GetMinNode() {

  :             TreeNode<T> _iterator = Root;

  :             while (_iteratorLeftNode != null) {

  :                 _iterator = _iteratorLeftNode;

  :             }

  :             return _iterator;

  :         }

  :

  :         /// <summary>

  :         /// 返回最小值

  :         /// </summary>

  :         /// <returns></returns>

  :         public T GetMinValue() {

  :             return GetMinNode()Value;

  :         }

  :

  :         public bool IsExit(T keyout TreeNode<T> node) {

  :             node = null;

  :             TreeNode<T> _iterator = Root;

  :             int result = _comparerCompare(key _iteratorValue);

  :             bool okFlag = true;

  :             while (okFlag) {

  :                 if (result == ) {

  :                     okFlag = false;

  :                     node = _iterator;//如果找到這個葉子結點那麼得到葉子節點的指針

  :                     return true;

  :                 } else if (result > ) {

  :                     _iterator = _iteratorRightNode;

  :                     if (_iterator != null)

  :                         result = _comparerCompare(key _iteratorValue);

  :                     else {

  :                         okFlag = false;

  :                         return false;

  :                     }

  :                 } else {

  :                     _iterator = _iteratorLeftNode;

  :                     if (_iterator != null)

  :                         result = _comparerCompare(key _iteratorValue);

  :                     else {

  :                         okFlag = false;

  :                         return false;

  :                     }

  :                 }

  :             }

  :             return false;

  :         }

  :

  :         public override string ToString() {

  :             string rtnString = stringFormat(This is a  kind of binary tree that impleted by Master and it has {} nodes CountToString());

  :             return rtnString;

  :         }

  :

  :         public TreeNode<T> Root {

  :             get;

  :             set;

  :         }

  :

  :         public int Count {

  :             get;

  :             private set;

  :         }

  :

  :         //返回樹的深度

  :         public int Deepness {

  :             get {

  :                 if (Count == )

  :                     return ;

  :                 else {

  :                     int[] _deepnessSortArray = new int[Count];

  :                     int pointer = Count ;

  :                     for (int i = ; i < Count; i++) _deepnessSortArray[i] = ;

  :                     InOrder(Root ref pointer ref _deepnessSortArray);

  :                     ArraySort<int>(_deepnessSortArray); //對_deepnessSortArray進行排序得出其中最大的數值就是該樹的深度

  :                     return _deepnessSortArray[Count ];

  :                 }

  :             }

  :         }

  :

  :         #endregion

  :

  :         #region Private Members

  :

  :         private static Comparer _comparer;

  :

  :         private int _deepness;

  :

  :         /// <summary>

  :         /// 遍歷樹節點然後給深度數組_deepnessSortArray[i]賦值之後對這個數組進行排序得到的最大值就是該樹的深度

  :         /// </summary>

  :         /// <param name=root></param>

  :         /// <param name=pointer></param>

  :         /// <param name=deepnessSortArray></param>

  :         private void InOrder(TreeNode<T> rootref int pointerref int[] deepnessSortArray) {

  :             if (root != null) {

  :                 InOrder(rootLeftNoderef pointerref deepnessSortArray);

  :                 deepnessSortArray[pointer] = rootDeepness;

  :                 pointer;

  :                 InOrder(rootRightNoderef pointer ref deepnessSortArray);

  :             }

  :         }

  :

  :         /// <summary>

  :         /// 基於中根遍歷的算法來得到某一個非葉子節點的後繼結點

  :         /// </summary>

  :         /// <param name=wannaDelNode></param>

  :         private TreeNode<T> GetSuccessor(TreeNode<T> wannaDelNode) {

  :             TreeNode<T> _iterator = wannaDelNodeRightNode;

  :             TreeNode<T> successorFather = null;

  :             TreeNode<T> successor = null;

  :

  :             //DebugWriteLine(stringFormat(_iterators value is {} _iteratorValueToString()));

  :             //DebugWriteLine(stringFormat(successors value is {} successorValueToString()));

  :             //首先應該要判斷是不是葉子節點如果是葉子節點情況就完全不一樣了

  :             while (_iterator != null) {

  :                 successorFather = _iteratorFatherNode;

  :                 successor = _iterator;

  :                 _iterator = _iteratorLeftNode;

  :             }

  :             return successor;

  :         }

  :

  :         private bool IsLeafNode(TreeNode<T> node) {

  :             return (nodeLeftNode == null && nodeRightNode == null) ? true : false;

  :         }

  :

  :         private bool HasTwoLeafNodes(TreeNode<T> node) {

  :             return (nodeLeftNode != null && nodeRightNode != null) ? true : false;

  :         }

  :

  :         #endregion

  :     }

  : }


From:http://tw.wingwit.com/Article/program/net/201311/12641.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.