关于c#二叉树的实现
2023-06-13 09:14:50 时间
本篇纯属娱乐，源于整理代码，发现还曾实现过遍历二叉树。
虽然.NET/C#中的各种集合类已经实现了最优的排序设计，但了解基本的算法实现有助于软件开发中的各种权衡和选择。
比如，如果你实现过B+树排序和查找，并将树节点序列化至二进制文件块，则你应该已经了解了各种数据库索引的基本设计。
http://en.wikipedia.org/wiki/Binary_tree
二叉树节点类定义
ViewCode
///<summary>
///二叉树节点
///</summary>
///<typeparamname="T">Theitemtype</typeparam>
publicclassBinaryTreeNode<T>
{
#regionConstructors
///<summary>
///二叉树节点
///</summary>
publicBinaryTreeNode()
{
}
///<summary>
///二叉树节点
///</summary>
///<paramname="value">节点中的值</param>
publicBinaryTreeNode(Tvalue)
{
this.Value=value;
}
///<summary>
///二叉树节点
///</summary>
///<paramname="value">节点中的值</param>
///<paramname="parent">节点的父节点</param>
publicBinaryTreeNode(Tvalue,BinaryTreeNode<T>parent)
{
this.Value=value;
this.Parent=parent;
}
///<summary>
///二叉树节点
///</summary>
///<paramname="value">节点中的值</param>
///<paramname="parent">节点的父节点</param>
///<paramname="left">节点的左节点</param>
///<paramname="right">节点的右节点</param>
publicBinaryTreeNode(Tvalue,
BinaryTreeNode<T>parent,
BinaryTreeNode<T>left,
BinaryTreeNode<T>right)
{
this.Value=value;
this.Right=right;
this.Left=left;
this.Parent=parent;
}
#endregion
#regionProperties
///<summary>
///节点值
///</summary>
publicTValue{get;set;}
///<summary>
///父节点
///</summary>
publicBinaryTreeNode<T>Parent{get;set;}
///<summary>
///左节点
///</summary>
publicBinaryTreeNode<T>Left{get;set;}
///<summary>
///右节点
///</summary>
publicBinaryTreeNode<T>Right{get;set;}
///<summary>
///是否为根节点
///</summary>
publicboolIsRoot{get{returnParent==null;}}
///<summary>
///是否为叶子节点
///</summary>
publicboolIsLeaf{get{returnLeft==null&&Right==null;}}
///<summary>
///是否为可访问的
///</summary>
internalboolVisited{get;set;}
#endregion
#regionPublicOverriddenFunctions
///<summary>
///Returnsa<seecref="System.String"/>thatrepresentsthisinstance.
///</summary>
///<returns>
///A<seecref="System.String"/>thatrepresentsthisinstance.
///</returns>
publicoverridestringToString()
{
returnValue.ToString();
}
#endregion
}
二叉树类实现
ViewCode
///<summary>
///二叉树
///</summary>
///<typeparamname="T">二叉树中节点内容类型</typeparam>
[SuppressMessage("Microsoft.Naming","CA1710:IdentifiersShouldHaveCorrectSuffix")]
publicclassBinaryTree<T>:ICollection<T>,IEnumerable<T>whereT:IComparable<T>
{
#regionConstructor
///<summary>
///二叉树
///</summary>
publicBinaryTree()
{
NumberOfNodes=0;
}
///<summary>
///二叉树
///</summary>
///<paramname="root">二叉树根节点</param>
publicBinaryTree(BinaryTreeNode<T>root)
:this()
{
this.Root=root;
}
#endregion
#regionProperties
///<summary>
///树的根节点
///</summary>
publicBinaryTreeNode<T>Root{get;set;}
///<summary>
///树中节点的数量
///</summary>
protectedintNumberOfNodes{get;set;}
///<summary>
///树是否为空
///</summary>
publicboolIsEmpty{get{returnRoot==null;}}
///<summary>
///获取树中节点的最小值
///</summary>
publicTMinValue
{
get
{
if(IsEmpty)
returndefault(T);
BinaryTreeNode<T>minNode=Root;
while(minNode.Left!=null)
minNode=minNode.Left;
returnminNode.Value;
}
}
///<summary>
///获取树中节点的最大值
///</summary>
publicTMaxValue
{
get
{
if(IsEmpty)
returndefault(T);
BinaryTreeNode<T>maxNode=Root;
while(maxNode.Right!=null)
maxNode=maxNode.Right;
returnmaxNode.Value;
}
}
#endregion
#regionIEnumerable<T>Members
///<summary>
///Returnsanenumeratorthatiteratesthroughthecollection.
///</summary>
///<returns>
///A<seecref="T:System.Collections.Generic.IEnumerator`1"></see>
///thatcanbeusedtoiteratethroughthecollection.
///</returns>
publicIEnumerator<T>GetEnumerator()
{
foreach(BinaryTreeNode<T>nodeinTraverse(Root))
{
yieldreturnnode.Value;
}
}
#endregion
#regionIEnumerableMembers
///<summary>
///Returnsanenumeratorthatiteratesthroughacollection.
///</summary>
///<returns>
///An<seecref="T:System.Collections.IEnumerator"/>
///objectthatcanbeusedtoiteratethroughthecollection.
///</returns>
IEnumeratorIEnumerable.GetEnumerator()
{
foreach(BinaryTreeNode<T>nodeinTraverse(Root))
{
yieldreturnnode.Value;
}
}
#endregion
#regionICollection<T>Members
///<summary>
///新增节点
///</summary>
///<paramname="item">Theobjecttoaddtothe
///<seecref="T:System.Collections.Generic.ICollection`1"></see>.</param>
///<exceptioncref="T:System.NotSupportedException">The
///<seecref="T:System.Collections.Generic.ICollection`1"></see>
///isread-only.</exception>
publicvoidAdd(Titem)
{
if(Root==null)
{
Root=newBinaryTreeNode<T>(item);
++NumberOfNodes;
}
else
{
Insert(item);
}
}
///<summary>
///清除树
///</summary>
publicvoidClear()
{
Root=null;
}
///<summary>
///树中是否包含此节点
///</summary>
///<paramname="item">Theobjecttolocateinthe
///<seecref="T:System.Collections.Generic.ICollection`1"></see>.</param>
///<returns>
///trueifitemisfoundinthe
///<seecref="T:System.Collections.Generic.ICollection`1"></see>;otherwise,false.
///</returns>
publicboolContains(Titem)
{
if(IsEmpty)
returnfalse;
BinaryTreeNode<T>currentNode=Root;
while(currentNode!=null)
{
intcomparedValue=currentNode.Value.CompareTo(item);
if(comparedValue==0)
returntrue;
elseif(comparedValue<0)
currentNode=currentNode.Left;
else
currentNode=currentNode.Right;
}
returnfalse;
}
///<summary>
///将树中节点拷贝至目标数组
///</summary>
///<paramname="array">Thearray.</param>
///<paramname="arrayIndex">Indexofthearray.</param>
publicvoidCopyTo(T[]array,intarrayIndex)
{
T[]tempArray=newT[NumberOfNodes];
intcounter=0;
foreach(Tvalueinthis)
{
tempArray[counter]=value;
++counter;
}
Array.Copy(tempArray,0,array,arrayIndex,Count);
}
///<summary>
///树中节点的数量
///</summary>
publicintCount
{
get{returnNumberOfNodes;}
}
///<summary>
///树是否为只读
///</summary>
publicboolIsReadOnly
{
get{returnfalse;}
}
///<summary>
///移除节点
///</summary>
///<paramname="item">节点值</param>
///<returns>是否移除成功</returns>
publicboolRemove(Titem)
{
BinaryTreeNode<T>node=Find(item);
if(node==null)
returnfalse;
List<T>values=newList<T>();
foreach(BinaryTreeNode<T>linTraverse(node.Left))
{
values.Add(l.Value);
}
foreach(BinaryTreeNode<T>rinTraverse(node.Right))
{
values.Add(r.Value);
}
if(node.Parent.Left==node)
{
node.Parent.Left=null;
}
else
{
node.Parent.Right=null;
}
node.Parent=null;
foreach(Tvinvalues)
{
this.Add(v);
}
returntrue;
}
#endregion
#regionPrivateFunctions
///<summary>
///查找指定值的节点
///</summary>
///<paramname="value">指定值</param>
///<returns>
///指定值的节点
///</returns>
protectedBinaryTreeNode<T>Find(Tvalue)
{
foreach(BinaryTreeNode<T>nodeinTraverse(Root))
if(node.Value.Equals(value))
returnnode;
returnnull;
}
///<summary>
///遍历树
///</summary>
///<paramname="node">遍历搜索的起始节点</param>
///<returns>
///Theindividualitemsfromthetree
///</returns>
[SuppressMessage("Microsoft.Design","CA1006:DoNotNestGenericTypesInMemberSignatures")]
protectedIEnumerable<BinaryTreeNode<T>>Traverse(BinaryTreeNode<T>node)
{
//遍历左子树
if(node.Left!=null)
{
foreach(BinaryTreeNode<T>leftinTraverse(node.Left))
yieldreturnleft;
}
//中序遍历二叉树,顺序是左子树，根，右子树
yieldreturnnode;
//遍历右子树
if(node.Right!=null)
{
foreach(BinaryTreeNode<T>rightinTraverse(node.Right))
yieldreturnright;
}
}
///<summary>
///插入节点
///</summary>
///<paramname="value">插入的节点值</param>
protectedvoidInsert(Tvalue)
{
//从根节点开始比较
BinaryTreeNode<T>currentNode=Root;
while(true)
{
if(currentNode==null)
thrownewInvalidProgramException("Thecurrenttreenodecannotbenull.");
//比较当前节点与新节点的值
intcomparedValue=currentNode.Value.CompareTo(value);
if(comparedValue<0)
{
//当前节点值小于新节点值
if(currentNode.Left==null)
{
currentNode.Left=newBinaryTreeNode<T>(value,currentNode);
++NumberOfNodes;
return;
}
else
{
currentNode=currentNode.Left;
}
}
elseif(comparedValue>0)
{
//当前节点值大于新节点值
if(currentNode.Right==null)
{
currentNode.Right=newBinaryTreeNode<T>(value,currentNode);
++NumberOfNodes;
return;
}
else
{
currentNode=currentNode.Right;
}
}
else
{
//当前节点值等于新节点值
currentNode=currentNode.Right;
}
}
}
#endregion
}
使用举例
classProgram
{
staticvoidMain(string[]args)
{
Console.ForegroundColor=ConsoleColor.Green;
BinaryTree<string>tree=newBinaryTree<string>();
tree.Add("Dennis");
tree.Add("Gao");
tree.Add("Is");
tree.Add("A");
tree.Add("C#");
tree.Add("Programmer");
Console.WriteLine("RootNodeIs:"+tree.Root.ToString());
Console.WriteLine();
foreach(varnodeintree)
{
Console.WriteLine(node);
}
Console.ReadKey();
}
}
相关文章
- c# 连接ACCESS 数据库 OleDbCommand OleDbDataReader
- 算法 – 堆排序（C#）
- c# MD5加密
- C#使用#ziplib压缩和解压缩文件
- url protocol启动本地exe，C#和Java都可以
- 详解C# WinForm如何实现自动更新程序的案例分享
- C# WPF开源控件库：MahApps.Metro
- C#使用NPOI进行word的读写
- Python表白C#？文末有彩蛋！
- c#面试题抽象类和接口的区别-金三银四面试：C#程序员经常遇到的30道基础面试题，想你所想
- C#-DevExpress改变表格行颜色
- C#正则实现Ubb解析类的代码
- C#拼接SQL语句用ROW_NUMBER实现的高效分页排序
- C#访问应用程序配置文件的方法
- C#TreeView无限级别分类实现方法
- .netC#生成缩略图实现思路分解
- c#删除代码中的单行注释行示例
- C#中StringBuilder类的使用总结
- c#索引器详解示例
- C#采用递归实现阶乘的方法