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

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

2018-10-21 11:17

文档管理软件,文档管理系统,知识管理系统,档案管理系统的技术资料:
Heavenkiller(原创)
N叉树的每一节点度数都相同,为N
[code]
csharp
using System;
using System.Collections;

namespace DataStructure
{
///
/// NaryTree 的摘要说明。-----N叉树
///

public class NaryTree : Tree
{
// member variables
protected object key;
protected uint degree;
protected ArrayList treeList = new ArrayList();
//protected uint height=0;//暂时默认为0

//create an empty tree whose attribute of degree is _degree
public NaryTree(uint _degree)
{
//
// TODO: 在此处添加构造函数逻辑
//
this.key = null;
this.degree = _degree;
this.treeList = null;
}
//构造一棵叶子结点的N叉树
public NaryTree(uint _degree, object _key)
{
this.key = _key;
this.degree = _degree;
this.treeList = new ArrayList();
this.treeList.Capacity = (int)_degree;

for (int i = 0; i < this.treeList.Capacity; i++)
{
this.treeList.Add(this.GetEmptyInstance(_degree));
}
}
//-----------------------------------------------------------------
protected virtual object GetEmptyInstance(uint _degree)
{ return new NaryTree(_degree); }
//-------------------------------------------------------------------
//judge whether the tree is an empty tree
public override bool IsEmpty()
{ return this.key == null; }
//判定是否是叶子结点。如果即不是空树且每一棵子树均为空树,则为叶子结点
public override bool IsLeaf()
{
if (IsEmpty())
return false;
for (uint i = 0; i < this.degree; i++)
{
if (!(this[i].IsEmpty()))
return false;
}
return true;
}
//-----------------------------------Inherited Attributes---------------------------------
public override object Key
{
get
{
return this.key;
}
}
//索引器
public override Tree this[uint _index]
{
get
{
if (_index >= this.degree)
throw new Exception("My:out of index!");//如果出界,则抛出异常
if (this.IsEmpty())
return null;//如果是空树,则索引器返回一个 null
return (Tree)this.treeList[(int)_index];
}
set
{
this.treeList[(int)_index] = value;
}
}

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]