本篇文章小编为大家介绍,关于c#二叉树的实现。需要的朋友参考下
本篇纯属娱乐,源于整理代码,发现还曾实现过遍历二叉树。
虽然.NET/C#中的各种集合类已经实现了最优的排序设计,但了解基本的算法实现有助于软件开发中的各种权衡和选择。
比如,如果你实现过B+树排序和查找,并将树节点序列化至二进制文件块,则你应该已经了解了各种数据库索引的基本设计。
什么是二叉树?
http://en.wikipedia.org/wiki/Binary_tree
二叉树节点类定义
复制代码 代码如下:
View Code
///
/// 二叉树节点
///
///
public class BinaryTreeNode
{
#region Constructors
///
/// 二叉树节点
///
public BinaryTreeNode()
{
}
///
/// 二叉树节点
///
/// 节点中的值
public BinaryTreeNode(T value)
{
this.Value = value;
}
///
/// 二叉树节点
///
/// 节点中的值
/// 节点的父节点
public BinaryTreeNode(T value, BinaryTreeNode
{
this.Value = value;
this.Parent = parent;
}
///
/// 二叉树节点
///
/// 节点中的值
/// 节点的父节点
/// 节点的左节点
/// 节点的右节点
public BinaryTreeNode(T value,
BinaryTreeNode
BinaryTreeNode
BinaryTreeNode
{
this.Value = value;
this.Right = right;
this.Left = left;
this.Parent = parent;
}
#endregion
#region Properties
///
/// 节点值
///
public T Value { get; set; }
///
/// 父节点
///
public BinaryTreeNode
///
/// 左节点
///
public BinaryTreeNode
///
/// 右节点
///
public BinaryTreeNode
///
/// 是否为根节点
///
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
///
///
/// A
///
public override string ToString()
{
return Value.ToString();
}
#endregion
}
二叉树类实现
复制代码 代码如下:
View Code
///
/// 二叉树
///
///
[SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
public class BinaryTree
{
#region Constructor
///
/// 二叉树
///
public BinaryTree()
{
NumberOfNodes = 0;
}
///
/// 二叉树
///
/// 二叉树根节点
public BinaryTree(BinaryTreeNode
: this()
{
this.Root = root;
}
#endregion
#region Properties
///
/// 树的根节点
///
public BinaryTreeNode
///
/// 树中节点的数量
///
protected int NumberOfNodes { get; set; }
///
/// 树是否为空
///
public bool IsEmpty { get { return Root == null; } }
///
/// 获取树中节点的最小值
///
public T MinValue
{
get
{
if (IsEmpty)
return default(T);
BinaryTreeNode
while (minNode.Left != null)
minNode = minNode.Left;
return minNode.Value;
}
}
///
/// 获取树中节点的最大值
///
public T MaxValue
{
get
{
if (IsEmpty)
return default(T);
BinaryTreeNode
while (maxNode.Right != null)
maxNode = maxNode.Right;
return maxNode.Value;
}
}
#endregion
#region IEnumerable
///
/// Returns an enumerator that iterates through the collection.
///
///
/// A
/// that can be used to iterate through the collection.
///
public IEnumerator
{
foreach (BinaryTreeNode
{
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
{
yield return node.Value;
}
}
#endregion
#region ICollection
///
/// 新增节点
///
/// The object to add to the
///
///
///
/// is read-only.
public void Add(T item)
{
if (Root == null)
{
Root = new BinaryTreeNode
++NumberOfNodes;
}
else
{
Insert(item);
}
}
///
/// 清除树
///
public void Clear()
{
Root = null;
}
///
/// 树中是否包含此节点
///
/// The object to locate in the
///
///
/// true if item is found in the
///
///
public bool Contains(T item)
{
if (IsEmpty)
return false;
BinaryTreeNode
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
if (node == null)
return false;
List
foreach (BinaryTreeNode
{
values.Add(l.Value);
}
foreach (BinaryTreeNode
{
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
{
foreach (BinaryTreeNode
if (node.Value.Equals(value))
return node;
return null;
}
///
/// 遍历树
///
/// 遍历搜索的起始节点
///
/// The individual items from the tree
///
[SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
protected IEnumerable
{
// 遍历左子树
if (node.Left != null)
{
foreach (BinaryTreeNode
yield return left;
}
// 中序遍历二叉树, 顺序是 左子树,根,右子树
yield return node;
// 遍历右子树
if (node.Right != null)
{
foreach (BinaryTreeNode
yield return right;
}
}
///
/// 插入节点
///
/// 插入的节点值
protected void Insert(T value)
{
// 从根节点开始比较
BinaryTreeNode
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
++NumberOfNodes;
return;
}
else
{
currentNode = currentNode.Left;
}
}
else if (comparedValue > 0)
{
// 当前节点值大于新节点值
if (currentNode.Right == null)
{
currentNode.Right = new BinaryTreeNode
++NumberOfNodes;
return;
}
else
{
currentNode = currentNode.Right;
}
}
else
{
// 当前节点值等于新节点值
currentNode = currentNode.Right;
}
}
}
#endregion
}
使用举例
复制代码 代码如下:
class Program
{
static void Main(string[] args)
{
Console.ForegroundColor = ConsoleColor.Green;
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();
}
}
中序遍历二叉树
以上就是关于c#二叉树的实现的详细内容,更多请关注0133技术站其它相关文章!