数据结构与算法 (C# 实现 ) 系列 ---N 叉树 ( 一 )
Heavenkiller( 原创 )
N 叉树的每一节点度数都相同，为 N
using System;
using System.Collections;
namespace DataStructure
{
///
1<summary>
2
3/// NaryTree 的摘要说明。 \-----N 叉树
4
5/// </summary>
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 ;
}
}