技术文章 > 数据结构与算法(C#实现)系列---二叉树

数据结构与算法(C#实现)系列---二叉树

2018-12-11 00:03

文档管理软件,文档管理系统,知识管理系统,档案管理系统的技术资料:

[code]
csharp
using System;
using System.Collections;
namespace DataStructure
{
/// <summary>
/// BinaryTree 的摘要说明。
/// </summary>
public class BinaryTree : NaryTree
{
//构造二叉空树
public BinaryTree()
: base(2)
{
//
// TODO: 在此处添加构造函数逻辑
//
}

public BinaryTree(object _obj)
: base(2, _obj)
{ }

//------------------------------------------------------------------
protected override object GetEmptyInstance(uint _degree)
{ return new BinaryTree(_degree); }
//------------------------------------------------------------------
//重写深度遍历
public override void DepthFirstTraversal(IPrePostVisitor _vis)
{
if (!IsEmpty())
{
_vis.PreVisit(this.Key);
this[0].DepthFirstTraversal(_vis);
_vis.Visit(this.Key);
this[1].DepthFirstTraversal(_vis);
_vis.PostVisit(this.Key);
}
}

//二叉树大小的比较
//先比较关键字,如果相等,再比较左子树,如果再相等,则比较右子树----如此递归
#region IComparable 成员
public override int CompareTo(object obj)
{
// TODO: 添加 BinaryTree.CompareTo 实现
//因为Comare()中已经进行了类型断定,故不会出现转型错误
BinaryTree tmpTree = (BinaryTree)obj;
if (this.IsEmpty())
return tmpTree.IsEmpty() ? 0 : -1;
if (tmpTree.IsEmpty())
return 1;
int result = Comparer.Default.Compare(this, tmpTree);
if (result == 0)
result = this[0].CompareTo(tmpTree[0]);
if (result == 0)
result = this[1].CompareTo(tmpTree[1]);
return result;
}
#endregion
}
}

public override uint Degree
{
get
{
return this.degree;
}
}

//-------------------------------------------------------------------------------------
//只用于空树结点
public virtual void AttachKey(object _obj)
{
if(!IsEmpty())
throw new Exception(“My:this node must be a empty tree node!“);
this.key=_obj;
this.treeList=new ArrayList();//产生一个degree长的数组,并将其初始化为空树
this.treeList.Capacity=(int)this.degree;
for(int i=0;i<this.degree;i++)
{
treeList.Add(new NaryTree(this.degree));
}
/*
foreach(object tmpObj in this.treeList)
{
tmpObj=new NaryTree(this.degree);
}
*/
}

//只用于叶子结点,将叶子结点变为一个空结点,并返回叶子结点关键字的引用
public virtual object DetachKey()
{
if(!IsLeaf())
throw new Exception(“My:this node must be a leaf node!“);
object result=this.key;//store this leaf node temporary
this.key=null;
this.treeList=null;
return result;
}

//将子树连接到指定树的第num个结点上,前提是这个结点必须是空结点,并且度数相同,否则抛出异常
public virtual void AttachSubtree(uint num,NaryTree _naryTree)
{
if(this.IsEmpty())
throw new Exception(“My:it can“t be a empty tree!“);
if(!(this[num-1].IsEmpty()) | this.degree!=_naryTree.degree )
throw new Exception(“My:this[i-1] must be empty and they should have the same degree!“);
this[num-1]=_naryTree;
}

//仅为非空树定义,从给定树中删去它的第i棵子树并连上一个空树,度数相同,并且返回删除的子树引用
public virtual NaryTree DetachSubtree(uint num)
{
if (IsEmpty())
throw new Exception(“My:it can“t be empty! “);
NaryTree tmpTree=this;
((NaryTree)this[num-1]).key=null;
((NaryTree)this[num-1]).treeList=null;
return this;
}

[/code]