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

核心提示：数据结构与算法(C#实现)系列---N叉树(一)Heavenkiller(原创)N叉树的每一节点度数都相同，为Nusing System;using System.Collections;namespace DataStructure{ /// <summary> /// NaryTree 的摘要说明，数据

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

Heavenkiller(原创)

N叉树的每一节点度数都相同，为N
using System;
using System.Collections;
namespace DataStructure

{

/// <summary>

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

/// </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;

　　　　  }

　　 }