本篇纯属娱乐，源于整理代码，发现还曾实现过遍历二叉树。
虽然.NET/C#中的各种集合类已经实现了最优的排序设计，但了解基本的算法实现有助于软件开发中的各种权衡和选择。
比如，如果你实现过B+树排序和查找，并将树节点序列化至二进制文件块，则你应该已经了解了各种数据库索引的基本设计。
什么是二叉树？
http://en.wikipedia.org/wiki/Binary_tree
二叉树节点类定义
代码如下:
View Code
///
/// 二叉树节点
///
/// The item type
public class BinaryTreeNode
{
#region Constructors
///
/// 二叉树节点
///
public BinaryTreeNode()
{
}
///
/// 二叉树节点
///
/// 节点中的值
public BinaryTreeNode(T value)
{
this.Value = value;
}
///
/// 二叉树节点
///
/// 节点中的值
/// 节点的父节点
public BinaryTreeNode(T value, BinaryTreeNode parent)
{
this.Value = value;
this.Parent = parent;
}
///
/// 二叉树节点
///
/// 节点中的值
/// 节点的父节点
/// 节点的左节点
/// 节点的右节点
public BinaryTreeNode(T value,
BinaryTreeNode parent,
BinaryTreeNode left,
BinaryTreeNode right)
{
this.Value = value;
this.Right = right;
this.Left = left;
this.Parent = parent;
}
#endregion
#region Properties
///
/// 节点值
///
public T Value { get; set; }
///
/// 父节点
///
public BinaryTreeNode Parent { get; set; }
///
/// 左节点
///
public BinaryTreeNode Left { get; set; }
///
/// 右节点
///
public BinaryTreeNode Right { get; set; }
///
/// 是否为根节点
///
public bool IsRoot { get { return Parent == null; } }
///
/// 是否为叶子节点
///
public bool IsLeaf { get { return Left == null && Right == null; } }
///
/// 是否为可访问的
///
internal bool Visited { get; set; }
#endregion
#region Public Overridden Functions
///
/// Returns a that represents this instance.
///
///
/// A that represents this instance.
///
public override string ToString()
{
return Value.ToString();
}
#endregion
}
二叉树类实现
代码如下:
View Code
///
/// 二叉树
///
/// 二叉树中节点内容类型
[SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
public class BinaryTree : ICollection, IEnumerable where T : IComparable
{
#region Constructor
///
/// 二叉树
///
public BinaryTree()
{
NumberOfNodes = 0;
}
///
/// 二叉树
///
/// 二叉树根节点
public BinaryTree(BinaryTreeNode root)
: this()
{
this.Root = root;
}
#endregion
#region Properties
///
/// 树的根节点
///
public BinaryTreeNode Root { get; set; }
///
/// 树中节点的数量
///
protected int NumberOfNodes { get; set; }
///
/// 树是否为空
///
public bool IsEmpty { get { return Root == null; } }
///
/// 获取树中节点的最小值
///
public T MinValue
{
get
{
if (IsEmpty)
return default(T);
BinaryTreeNode minNode = Root;
while (minNode.Left != null)
minNode = minNode.Left;
return minNode.Value;
}
}
///
/// 获取树中节点的最大值
///
public T MaxValue
{
get
{
if (IsEmpty)
return default(T);
BinaryTreeNode maxNode = Root;
while (maxNode.Right != null)
maxNode = maxNode.Right;
return maxNode.Value;
}
}
#endregion
#region IEnumerable Members
///
/// Returns an enumerator that iterates through the collection.
///
///
/// A
/// that can be used to iterate through the collection.
///
public IEnumerator GetEnumerator()
{
foreach (BinaryTreeNode node in Traverse(Root))
{
yield return node.Value;
}
}
#endregion
#region IEnumerable Members
///
/// Returns an enumerator that iterates through a collection.
///
///
/// An
/// object that can be used to iterate through the collection.
///
IEnumerator IEnumerable.GetEnumerator()
{
foreach (BinaryTreeNode node in Traverse(Root))
{
yield return node.Value;
}
}
#endregion
#region ICollection Members
///
/// 新增节点
///
/// The object to add to the
/// .
/// The
///
/// is read-only.
public void Add(T item)
{
if (Root == null)
{
Root = new BinaryTreeNode(item);
++NumberOfNodes;
}
else
{
Insert(item);
}
}
///
/// 清除树
///
public void Clear()
{
Root = null;
}
///
/// 树中是否包含此节点
///
/// The object to locate in the
/// .
///
/// true if item is found in the
/// ; otherwise, false.
///
public bool Contains(T item)
{
if (IsEmpty)
return false;
BinaryTreeNode 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;
}
///
/// 将树中节点拷贝至目标数组
///
/// The array.
/// Index of the array.
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);
}
///
/// 树中节点的数量
///
public int Count
{
get { return NumberOfNodes; }
}
///
/// 树是否为只读
///
public bool IsReadOnly
{
get { return false; }
}
///
/// 移除节点
///
/// 节点值
/// 是否移除成功
public bool Remove(T item)
{
BinaryTreeNode node = Find(item);
if (node == null)
return false;
List values = new List();
foreach (BinaryTreeNode l in Traverse(node.Left))
{
values.Add(l.Value);
}
foreach (BinaryTreeNode 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
///
/// 查找指定值的节点
///
/// 指定值
///
/// 指定值的节点
///
protected BinaryTreeNode Find(T value)
{
foreach (BinaryTreeNode node in Traverse(Root))
if (node.Value.Equals(value))
return node;
return null;
}
///
/// 遍历树
///
/// 遍历搜索的起始节点
///
/// The individual items from the tree
///
[SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
protected IEnumerable Traverse(BinaryTreeNode node)
{
// 遍历左子树
if (node.Left != null)
{
foreach (BinaryTreeNode left in Traverse(node.Left))
yield return left;
}
// 中序遍历二叉树, 顺序是 左子树，根，右子树
yield return node;
// 遍历右子树
if (node.Right != null)
{
foreach (BinaryTreeNode right in Traverse(node.Right))
yield return right;
}
}
///
/// 插入节点
///
/// 插入的节点值
protected void Insert(T value)
{
// 从根节点开始比较
BinaryTreeNode currentNode = Root;
while (true)
{
if (currentNode == null)
throw new InvalidProgramException("The current tree node cannot be null.");
// 比较当前节点与新节点的值
int comparedValue = currentNode.Value.CompareTo(value);
if (comparedValue < 0)
{
// 当前节点值小于新节点值
if (currentNode.Left == null)
{
currentNode.Left = new BinaryTreeNode(value, currentNode);
++NumberOfNodes;
return;
}
else
{
currentNode = currentNode.Left;
}
}
else if (comparedValue > 0)
{
// 当前节点值大于新节点值
if (currentNode.Right == null)
{
currentNode.Right = new BinaryTreeNode(value, currentNode);
++NumberOfNodes;
return;
}
else
{
currentNode = currentNode.Right;
}
}
else
{
// 当前节点值等于新节点值
currentNode = currentNode.Right;
}
}
}
#endregion
}
使用举例
代码如下:
class Program
{
static void Main(string[] args)
{
Console.ForegroundColor = ConsoleColor.Green;
BinaryTree tree = new BinaryTree();
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();
}
}
中序遍历二叉树