你曾实现过二叉树吗

虽然 .NET/C# 中的各种集合类已经实现了最优的排序设计，但了解基本的算法实现有助于软件开发中的各种权衡和选择。

比如，如果你实现过 B+ 树排序和查找，并将树节点序列化至二进制文件块，则你应该已经了解了各种数据库索引的基本设计。

什么是二叉树？

所有的树都呈现了一些共有的特性：

只有一个根节点；
除了根节点，所有其他节点有且只有一个父节点；
无环产生。从任意一个节点开始，都没有回到该起始节点的路径。正是前两个特性保证了无环的成立。

二叉树（Binary Tree）是一种特殊的树类型，因为它的所有节点最多只能有两个子节点。对于二叉树中指定的节点，它的两个子节点分别称为左孩子（left child）和右孩子（right child）。

上图中，二叉树 (a) 包含 8 个节点，其中节点 1 为它的根节点。节点 1 的左孩子为节点 2，右孩子为节点 3。注意，节点并不要求同时具有左孩子和右孩子。例如，二叉树 (a) 中，节点 4 就只有一个右孩子 6。此外，节点也可以没有孩子节点。例如，二叉树 (b) 中，节点 4、5、6、7 都没有孩子节点。

没有孩子的节点称为叶节点（Leaf Node），有孩子的节点称为内节点（Internal Node）。如上图中，二叉树 (a) 中节点 6、8 为叶节点，节点 1、2、3、4、5、7 为内节点。

不幸的是，.NET 中并没有直接提供二叉树的实现，我们需要自己来实现 BinaryTree 类。

二叉树节点类定义

节点类 BinaryTreeNode 抽象地表示了树中的一个节点。二叉树中节点应包括两部分内容：

数据；
子节点：0个、1个、2个；

节点存储的数据依赖于你的实际需要。就像数组可以存储整型、字符串和其他类类型的实例一样，节点也应该如此。这里我们使用泛型来支持这样的功能。

View Code

  1   /// <summary>
  2   /// 二叉树节点
  3   /// </summary>
  4   /// <typeparam name="T">The item type</typeparam>
  5   public class BinaryTreeNode<T>
  6   {
  7     #region Constructors
  8 
  9     /// <summary>
 10     /// 二叉树节点
 11     /// </summary>
 12     public BinaryTreeNode()
 13     {
 14     }
 15 
 16     /// <summary>
 17     /// 二叉树节点
 18     /// </summary>
 19     /// <param name="value">节点中的值</param>
 20     public BinaryTreeNode(T value)
 21     {
 22       this.Value = value;
 23     }
 24 
 25     /// <summary>
 26     /// 二叉树节点
 27     /// </summary>
 28     /// <param name="value">节点中的值</param>
 29     /// <param name="parent">节点的父节点</param>
 30     public BinaryTreeNode(T value, BinaryTreeNode<T> parent)
 31     {
 32       this.Value = value;
 33       this.Parent = parent;
 34     }
 35 
 36     /// <summary>
 37     /// 二叉树节点
 38     /// </summary>
 39     /// <param name="value">节点中的值</param>
 40     /// <param name="parent">节点的父节点</param>
 41     /// <param name="left">节点的左节点</param>
 42     /// <param name="right">节点的右节点</param>
 43     public BinaryTreeNode(T value, 
 44       BinaryTreeNode<T> parent, 
 45       BinaryTreeNode<T> left, 
 46       BinaryTreeNode<T> right)
 47     {
 48       this.Value = value;
 49       this.Right = right;
 50       this.Left = left;
 51       this.Parent = parent;
 52     }
 53 
 54     #endregion
 55 
 56     #region Properties
 57 
 58     /// <summary>
 59     /// 节点值
 60     /// </summary>
 61     public T Value { get; set; }
 62 
 63     /// <summary>
 64     /// 父节点
 65     /// </summary>
 66     public BinaryTreeNode<T> Parent { get; set; }
 67 
 68     /// <summary>
 69     /// 左节点
 70     /// </summary>
 71     public BinaryTreeNode<T> Left { get; set; }
 72 
 73     /// <summary>
 74     /// 右节点
 75     /// </summary>
 76     public BinaryTreeNode<T> Right { get; set; }
 77 
 78     /// <summary>
 79     /// 是否为根节点
 80     /// </summary>
 81     public bool IsRoot { get { return Parent == null; } }
 82 
 83     /// <summary>
 84     /// 是否为叶子节点
 85     /// </summary>
 86     public bool IsLeaf { get { return Left == null && Right == null; } }
 87 
 88     /// <summary>
 89     /// 是否为可访问的
 90     /// </summary>
 91     internal bool Visited { get; set; }
 92 
 93     #endregion
 94 
 95     #region Public Overridden Functions
 96 
 97     /// <summary>
 98     /// Returns a <see cref="System.String"/> that represents this instance.
 99     /// </summary>
100     /// <returns>
101     /// A <see cref="System.String"/> that represents this instance.
102     /// </returns>
103     public override string ToString()
104     {
105       return Value.ToString();
106     }
107 
108     #endregion
109   }

二叉树类实现

BinaryTree 类的实例包含了根节点（Root Node）实例的引用，而根节点实例又分别指向它的左右孩子节点实例，以此类推。组成二叉树的不同的 Node 实例可以分散到 CLR 托管堆中任何位置，它们没有必要像数组元素那样连续的存放。

View Code

  1   /// <summary>
  2   /// 二叉树
  3   /// </summary>
  4   /// <typeparam name="T">二叉树中节点内容类型</typeparam>
  5   [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
  6   public class BinaryTree<T> : ICollection<T>, IEnumerable<T> where T : IComparable<T>
  7   {
  8     #region Constructor
  9 
 10     /// <summary>
 11     /// 二叉树
 12     /// </summary>
 13     public BinaryTree()
 14     {
 15       NumberOfNodes = 0;
 16     }
 17 
 18     /// <summary>
 19     /// 二叉树
 20     /// </summary>
 21     /// <param name="root">二叉树根节点</param>
 22     public BinaryTree(BinaryTreeNode<T> root)
 23       : this()
 24     {
 25       this.Root = root;
 26     }
 27 
 28     #endregion
 29 
 30     #region Properties
 31 
 32     /// <summary>
 33     /// 树的根节点
 34     /// </summary>
 35     public BinaryTreeNode<T> Root { get; set; }
 36 
 37     /// <summary>
 38     /// 树中节点的数量
 39     /// </summary>
 40     protected int NumberOfNodes { get; set; }
 41 
 42     /// <summary>
 43     /// 树是否为空
 44     /// </summary>
 45     public bool IsEmpty { get { return Root == null; } }
 46 
 47     /// <summary>
 48     /// 获取树中节点的最小值
 49     /// </summary>
 50     public T MinValue
 51     {
 52       get
 53       {
 54         if (IsEmpty)
 55           return default(T);
 56 
 57         BinaryTreeNode<T> minNode = Root;
 58         while (minNode.Left != null)
 59           minNode = minNode.Left;
 60 
 61         return minNode.Value;
 62       }
 63     }
 64 
 65     /// <summary>
 66     /// 获取树中节点的最大值
 67     /// </summary>
 68     public T MaxValue
 69     {
 70       get
 71       {
 72         if (IsEmpty)
 73           return default(T);
 74 
 75         BinaryTreeNode<T> maxNode = Root;
 76         while (maxNode.Right != null)
 77           maxNode = maxNode.Right;
 78 
 79         return maxNode.Value;
 80       }
 81     }
 82 
 83     #endregion
 84 
 85     #region IEnumerable<T> Members
 86 
 87     /// <summary>
 88     /// Returns an enumerator that iterates through the collection.
 89     /// </summary>
 90     /// <returns>
 91     /// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see> 
 92     /// that can be used to iterate through the collection.
 93     /// </returns>
 94     public IEnumerator<T> GetEnumerator()
 95     {
 96       foreach (BinaryTreeNode<T> node in Traverse(Root))
 97       {
 98         yield return node.Value;
 99       }
100     }
101 
102     #endregion
103 
104     #region IEnumerable Members
105 
106     /// <summary>
107     /// Returns an enumerator that iterates through a collection.
108     /// </summary>
109     /// <returns>
110     /// An <see cref="T:System.Collections.IEnumerator"/> 
111     /// object that can be used to iterate through the collection.
112     /// </returns>
113     IEnumerator IEnumerable.GetEnumerator()
114     {
115       foreach (BinaryTreeNode<T> node in Traverse(Root))
116       {
117         yield return node.Value;
118       }
119     }
120 
121     #endregion
122 
123     #region ICollection<T> Members
124 
125     /// <summary>
126     /// 新增节点
127     /// </summary>
128     /// <param name="item">The object to add to the 
129     /// <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
130     /// <exception cref="T:System.NotSupportedException">The 
131     /// <see cref="T:System.Collections.Generic.ICollection`1"></see> 
132     /// is read-only.</exception>
133     public void Add(T item)
134     {
135       if (Root == null)
136       {
137         Root = new BinaryTreeNode<T>(item);
138         ++NumberOfNodes;
139       }
140       else
141       {
142         Insert(item);
143       }
144     }
145 
146     /// <summary>
147     /// 清除树
148     /// </summary>
149     public void Clear()
150     {
151       Root = null;
152     }
153 
154     /// <summary>
155     /// 树中是否包含此节点
156     /// </summary>
157     /// <param name="item">The object to locate in the 
158     /// <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
159     /// <returns>
160     /// true if item is found in the 
161     /// <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false.
162     /// </returns>
163     public bool Contains(T item)
164     {
165       if (IsEmpty)
166         return false;
167 
168       BinaryTreeNode<T> currentNode = Root;
169       while (currentNode != null)
170       {
171         int comparedValue = currentNode.Value.CompareTo(item);
172         if (comparedValue == 0)
173           return true;
174         else if (comparedValue < 0)
175           currentNode = currentNode.Left;
176         else
177           currentNode = currentNode.Right;
178       }
179 
180       return false;
181     }
182 
183     /// <summary>
184     /// 将树中节点拷贝至目标数组
185     /// </summary>
186     /// <param name="array">The array.</param>
187     /// <param name="arrayIndex">Index of the array.</param>
188     public void CopyTo(T[] array, int arrayIndex)
189     {
190       T[] tempArray = new T[NumberOfNodes];
191       int counter = 0;
192       foreach (T value in this)
193       {
194         tempArray[counter] = value;
195         ++counter;
196       }
197       Array.Copy(tempArray, 0, array, arrayIndex, Count);
198     }
199 
200     /// <summary>
201     /// 树中节点的数量
202     /// </summary>
203     public int Count
204     {
205       get { return NumberOfNodes; }
206     }
207 
208     /// <summary>
209     /// 树是否为只读
210     /// </summary>
211     public bool IsReadOnly
212     {
213       get { return false; }
214     }
215 
216     /// <summary>
217     /// 移除节点
218     /// </summary>
219     /// <param name="item">节点值</param>
220     /// <returns>是否移除成功</returns>
221     public bool Remove(T item)
222     {
223       BinaryTreeNode<T> node = Find(item);
224       if (node == null)
225         return false;
226 
227       List<T> values = new List<T>();
228       foreach (BinaryTreeNode<T> l in Traverse(node.Left))
229       {
230         values.Add(l.Value);
231       }
232       foreach (BinaryTreeNode<T> r in Traverse(node.Right))
233       {
234         values.Add(r.Value);
235       }
236 
237       if (node.Parent.Left == node)
238       {
239         node.Parent.Left = null;
240       }
241       else
242       {
243         node.Parent.Right = null;
244       }
245 
246       node.Parent = null;
247 
248       foreach (T v in values)
249       {
250         this.Add(v);
251       }
252 
253       return true;
254     }
255 
256     #endregion
257 
258     #region Private Functions
259 
260     /// <summary>
261     /// 查找指定值的节点
262     /// </summary>
263     /// <param name="value">指定值</param>
264     /// <returns>
265     /// 指定值的节点
266     /// </returns>
267     protected BinaryTreeNode<T> Find(T value)
268     {
269       foreach (BinaryTreeNode<T> node in Traverse(Root))
270         if (node.Value.Equals(value))
271           return node;
272       return null;
273     }
274 
275     /// <summary>
276     /// 遍历树
277     /// </summary>
278     /// <param name="node">遍历搜索的起始节点</param>
279     /// <returns>
280     /// The individual items from the tree
281     /// </returns>
282     [SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
283     protected IEnumerable<BinaryTreeNode<T>> Traverse(BinaryTreeNode<T> node)
284     {
285       // 遍历左子树
286       if (node.Left != null)
287       {
288         foreach (BinaryTreeNode<T> left in Traverse(node.Left))
289           yield return left;
290       }
291 
292       // 中序遍历二叉树, 顺序是 左子树，根，右子树
293       yield return node;
294 
295       // 遍历右子树
296       if (node.Right != null)
297       {
298         foreach (BinaryTreeNode<T> right in Traverse(node.Right))
299           yield return right;
300       }
301     }
302 
303     /// <summary>
304     /// 插入节点
305     /// </summary>
306     /// <param name="value">插入的节点值</param>
307     protected void Insert(T value)
308     {
309       // 从根节点开始比较
310       BinaryTreeNode<T> currentNode = Root;
311       
312       while (true)
313       {
314         if (currentNode == null)
315           throw new InvalidProgramException("The current tree node cannot be null.");
316 
317         // 比较当前节点与新节点的值
318         int comparedValue = currentNode.Value.CompareTo(value);
319         if (comparedValue < 0)
320         {
321           // 当前节点值小于新节点值
322           if (currentNode.Left == null)
323           {
324             currentNode.Left = new BinaryTreeNode<T>(value, currentNode);
325             ++NumberOfNodes;
326             return;
327           }
328           else
329           {
330             currentNode = currentNode.Left;
331           }
332         }
333         else if (comparedValue > 0)
334         {
335           // 当前节点值大于新节点值
336           if (currentNode.Right == null)
337           {
338             currentNode.Right = new BinaryTreeNode<T>(value, currentNode);
339             ++NumberOfNodes;
340             return;
341           }
342           else
343           {
344             currentNode = currentNode.Right;
345           }
346         }
347         else
348         {
349           // 当前节点值等于新节点值
350           currentNode = currentNode.Right;
351         }
352       }
353     }
354 
355     #endregion
356   }

使用举例

 1   class Program
 2   {
 3     static void Main(string[] args)
 4     {
 5       Console.ForegroundColor = ConsoleColor.Green;
 6 
 7       BinaryTree<string> tree = new BinaryTree<string>();
 8       tree.Add("Dennis");
 9       tree.Add("Gao");
10       tree.Add("Is");
11       tree.Add("A");
12       tree.Add("C#");
13       tree.Add("Programmer");
14 
15       Console.WriteLine("Root Node Is : " + tree.Root.ToString());
16       Console.WriteLine();
17 
18       foreach (var node in tree)
19       {
20         Console.WriteLine(node);
21       }
22 
23       Console.ReadKey();
24     }
25   }

中序遍历二叉树

参考资料

An Extensive Examination of Data Structures Using C# 2.0 : Part 3: Binary Trees and BSTs

本文《你曾实现过二叉树吗》由 Dennis Gao 发表自博客园博客，任何未经作者本人允许的人为或爬虫转载均为耍流氓。