关于c#二叉树的实现
更新时间:2020年6月25日 11:42 点击:2212
本篇纯属娱乐,源于整理代码,发现还曾实现过遍历二叉树。
虽然.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#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25