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