虽然 .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个；
节点存储的数据依赖于你的实际需要。就像数组可以存储整型、字符串和其他类类型的实例一样，节点也应该如此。这里我们使用泛型来支持这样的功能。
二叉树类实现
BinaryTree 类的实例包含了根节点（Root Node）实例的引用，而根节点实例又分别指向它的左右孩子节点实例，以此类推。组成二叉树的不同的 Node 实例可以分散到 CLR 托管堆中任何位置，它们没有必要像数组元素那样连续的存放。
使用举例
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 }
中序遍历二叉树
参考资料