主题：树类
lanjingquan
[专家分：510] 发布于 2002-11-16 10:11:00
//
// treeNode.h 树结点类定义，采用孩子兄弟法存储
// lanjingquan 2002.6.1
////////////////////////////////////////////////////
#ifndef _H_TREENODE
#define _H_TREENODE
#include<iostream.h>
////////////////////////////////////////////////////
//树节点抽象类
template<class TElem>
class TTreeNode0
{
public:
TElem info; //元素内容
virtual TElem& GetElem(); //取得节点元素
virtual TTreeNode0* SetElem(TElem* elem);
//设置节点内容
virtual TTreeNode0* SetSon(TTreeNode0* pSon)=0;
//设置子树
virtual TTreeNode0* GetSon(char sonNo)=0;//取子树
virtual TTreeNode0* GetFirstSon()=0; //取第一个儿子
virtual TTreeNode0* GetNextSon()=0; //取下一儿子
virtual TTreeNode0* GetFather()=0; //取父亲
virtual TTreeNode0* SetFather(TTreeNode0* f)=0;
//设置父亲
virtual bool IsLeaf()=0; //是否树叶
};
////////////////////////////////////////////////////
//函数体定义
////////////////////////////////////////////////////
//取得节点元素
template<class TElem>
TElem& TTreeNode0<TElem>::GetElem()
{
return info;
}
////////////////////////////////////////////////////
//设置节点内容
template<class TElem>
TTreeNode0<TElem>* TTreeNode0<TElem>::SetElem(TElem* elem)
{
info=*elem;
return this;
}
////////////////////////////////////////////////////
//节点存储结构
template<class TElem>
class TTreeNodeBinLink:public TTreeNode0<TElem>
{
public:
TTreeNodeBinLink* firstSon; //大儿子指针
TTreeNodeBinLink* nextBrother; //下一兄弟指针
TTreeNodeBinLink* father; //父亲指针
TTreeNodeBinLink(); //构造函数
virtual TTreeNode0<TElem>* SetSon(TTreeNode0<TElem>* pSon);
//设置子树
virtual TTreeNode0<TElem>* GetSon(char sonNo);
//取sonNo棵子树
virtual TTreeNode0<TElem>* GetFirstSon();//取第一个儿子
virtual TTreeNode0<TElem>* GetNextSon();//取下一儿子
virtual TTreeNode0<TElem>* SetFather(TTreeNode0<TElem>* father);
//设置父亲
virtual TTreeNode0<TElem>* GetFather(); //取父亲
TTreeNodeBinLink* SetNextBrother(TTreeNodeBinLink* brother);
//设置下一兄弟
TTreeNodeBinLink* GetNextBrother(); //取下一兄弟
virtual bool IsLeaf(); //是否树叶
private:
TTreeNodeBinLink* lastVisted;
};
///////////////////////////////////////////////////
//函数体定义
///////////////////////////////////////////////////
//构造函数
template<class TElem>
TTreeNodeBinLink<TElem>::TTreeNodeBinLink()
{
father=NULL; //初始化各
firstSon=NULL; //指针为空
nextBrother=NULL;
lastVisted=NULL;
}
///////////////////////////////////////////////////
//取儿子结点,如果 sonNo 大于实
//际子树数, 则返回最右一个儿子
template<class TElem>
TTreeNode0<TElem>* TTreeNodeBinLink<TElem>::GetSon(char sonNo)
{
char count=1;
TTreeNodeBinLink<TElem>* find=firstSon;
while(count!=sonNo && find->nextBrother)
{ //扫描兄弟链
find=find->nextBrother;
count++;
}
return find;
}
///////////////////////////////////////////////////
//设置儿子, 插入到最右的位置
template<class TElem>
TTreeNode0<TElem>* TTreeNodeBinLink<TElem>::SetSon(TTreeNode0<TElem>* pSon)
{
if(firstSon==NULL) //首儿子空, 则置为首儿子
return firstSon=(TTreeNodeBinLink<TElem>*)pSon;
TTreeNodeBinLink<TElem>* find=firstSon; //其它情况下置为最右儿子
while(find->nextBrother)
find=find->nextBrother;
return find->nextBrother=(TTreeNodeBinLink<TElem>*)pSon;
}
///////////////////////////////////////////////////
//取第一个儿子
template<class TElem>
TTreeNode0<TElem>* TTreeNodeBinLink<TElem>::GetFirstSon()
{
lastVisted=firstSon;
return firstSon;
}
///////////////////////////////////////////////////
//取下一儿子
template<class TElem>
TTreeNode0<TElem>* TTreeNodeBinLink<TElem>::GetNextSon()
{
if(lastVisted) //处理已有first的情况
return lastVisted=lastVisted->nextBrother;
else
return NULL;
}
///////////////////////////////////////////////////
//取父亲
template<class TElem>
TTreeNode0<TElem>* TTreeNodeBinLink<TElem>::GetFather()
{
return father;
}
///////////////////////////////////////////////////
//设置父亲
template<class TElem>
TTreeNode0<TElem>* TTreeNodeBinLink<TElem>::SetFather(TTreeNode0<TElem>* f)
{
return father=(TTreeNodeBinLink<TElem>*)f;
}
///////////////////////////////////////////////////
//是否树叶
template<class TElem>
bool TTreeNodeBinLink<TElem>::IsLeaf()
{
return firstSon==NULL;
}
///////////////////////////////////////////////////
//设置下一兄弟
template<class TElem>
TTreeNodeBinLink<TElem>* TTreeNodeBinLink<TElem>::SetNextBrother(TTreeNodeBinLink<TElem>* brother)
{
return nextBrother=brother;
}
///////////////////////////////////////////////////
//取下一兄弟
template<class TElem>
TTreeNodeBinLink<TElem>* TTreeNodeBinLink<TElem>::GetNextBrother()
{
return nextBrother;
}
#endif
沙发
lanjingquan [专家分：510] 发布于 2002-11-16 10:13:00
//
// tree.h 树类定义
// lanjingquan 2002.6.3
/////////////////////////////////////////////////
#ifndef _H_TREE
#define _H_TREE
#include"treeNode.h"
#include<iostream.h>
#include"afx.h" //just for using ASSERT when new
enum TTraverseMode{PreOrder,PostOrder,LevelOrder}; //遍历方式
template<class TElem>
class TTree
{
public:
TTree(); //构造函数
~TTree(); //析构函数
virtual TTreeNodeBinLink<TElem>* GetRoot(); //取树根
virtual bool SetRoot(TTreeNodeBinLink<TElem>* rt); //设置树根
virtual long GetLevel(TTreeNodeBinLink<TElem>* pNode);//取pNode的层号
virtual long GetHeight(TTreeNodeBinLink<TElem>* pNode);//取以pNode为根的树的高度
virtual long GetNumSubNodes(TTreeNodeBinLink<TElem>* pNode);
//取以pNode为根的树中的结点总数
virtual long GetNumLeaves(TTreeNodeBinLink<TElem>* pNode);
//取以pNode为根的树中的叶子总数
virtual long Cluster(TTreeNodeBinLink<TElem>* pNode,
TElem** e,
TTraverseMode tm); //串行聚集
virtual long Cluster(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm); //串行聚集
virtual long Cluster2(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm); //串行聚集的非递归算法
virtual long ClusterDescendants(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm=PreOrder,
int startLevel=1,
int endLevel=-1);
//串行聚集由startLevel到endLevel
virtual long ClusterAncestors(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe);
//聚集祖先
virtual long ClusterAncestors(TTreeNodeBinLink<TElem>* pNode,
TElem** e); //聚集祖先
virtual long ClusterAncestors(TElem& e,
TTreeNodeBinLink<TElem>** pe);
//聚集祖先
virtual long ClusterJuniors(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm=PreOrder,
int startLevel=1,
int endLevel=-1); //后辈聚集
virtual long ClusterSeniors(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm=PreOrder,
int startLevel=1,
int endLevel=-1); //聚集由startLevel到endLevel的前辈
virtual long DeleteSubTree(TTreeNodeBinLink<TElem>* pNode,
char sonNo); //删除子树
virtual long ReleaseSubs(TTreeNodeBinLink<TElem>* pNode);
//释放子树
virtual TTreeNodeBinLink<TElem>* Locate(TTreeNodeBinLink<TElem>* rt,
TElem& elem);
//按内容定位
virtual void Print(TTreeNodeBinLink<TElem>* rt,char mode);
//打印输出
private:
TTreeNodeBinLink<TElem>* root; //树根指针
//几个辅助子函数,目的在于分散难点，缩短程序行，包装cnt计数变量
long ClusterPreOrder(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe);
long ClusterPostOrder(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe);
long ClusterDescendantsPost(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
int startLevel,
int endLevel);
long ClusterDescendantsPre(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
int startLevel,
int endLevel);
long ClusterPre(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
long& cnt);
long ClusterPost(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
long& cnt);
long ClusterPre2(TTreeNodeBinLink<TElem>* pNode,
TElem** e,
long& cnt);
long ClusterPost2(TTreeNodeBinLink<TElem>* pNode,
TElem** e,
long& cnt);
};
/////////////////////////////////////////////////
//具体函数定
/////////////////////////////////////////////////
//构造函数
template<class TElem>
TTree<TElem>::TTree()
{
root=NULL;
}
/////////////////////////////////////////////////
//析构函数
template<class TElem>
TTree<TElem>::~TTree()
{
ReleaseSubs(root);
root=NULL;
}
/////////////////////////////////////////////////
//取树根
template<class TElem>
TTreeNodeBinLink<TElem>* TTree<TElem>::GetRoot()
{
return root;
}
/////////////////////////////////////////////////
//设置树根
template<class TElem>
bool TTree<TElem>::SetRoot(TTreeNodeBinLink<TElem>* rt)
{
root=rt;
return 1;
}
/////////////////////////////////////////////////
//取pNode的层号
template<class TElem>
long TTree<TElem>::GetLevel(TTreeNodeBinLink<TElem>* pNode)
{
if(pNode==NULL)
return 0;
else
return GetLevel((TTreeNodeBinLink<TElem>*) pNode->GetFather())+1;
}
/////////////////////////////////////////////////
//取以pNode为根的树的高度
template<class TElem>
long TTree<TElem>::GetHeight(TTreeNodeBinLink<TElem>* pNode)
{
long m1, m2;
TTreeNodeBinLink<TElem>* p;
if (pNode==NULL)
return 0; //递归结束条件
m1=GetHeight((TTreeNodeBinLink<TElem>*) pNode->GetFirstSon()); //处理首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
{ //处理其它儿子
m2=GetHeight(p);
m1=m1>m2?m1:m2;
}
return m1+1; //返回高度
}
/////////////////////////////////////////////////
//取以pNode为根的树中的结点总数
template<class TElem>
long TTree<TElem>::GetNumSubNodes(TTreeNodeBinLink<TElem>* pNode)
{
long sum;
TTreeNodeBinLink<TElem>* p;
if (pNode==NULL)
return 0; //递归结束条件
sum=GetNumSubNodes((TTreeNodeBinLink<TElem>*) pNode->GetFirstSon());
//处理首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
sum+=GetNumSubNodes(p); //处理其它儿子
return sum+1; //返回
}
/////////////////////////////////////////////////
//取以pNode为根的树中的叶子总数
template<class TElem>
long TTree<TElem>::GetNumLeaves(TTreeNodeBinLink<TElem>* pNode)
{
long sum;
TTreeNodeBinLink<TElem>* p;
if (pNode==NULL) //递归结束条件
return 0;
if (pNode->IsLeaf())
return 1;
sum=GetNumLeaves((TTreeNodeBinLink<TElem>*)pNode->GetFirstSon());
//处理首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
sum+=GetNumLeaves(p); //处理其它儿子
return sum; //返回
}
/////////////////////////////////////////////////
//串行聚集, e 存放串行聚集结果, tm 为串行化模式
template<class TElem>
long TTree<TElem>::Cluster(TTreeNodeBinLink<TElem>* pNode,
TElem** e,
TTraverseMode tm)
{
if(pNode==NULL) //空返回，结束递归
return 0;
long cnt=0;
switch(tm)
{
case PreOrder:
return ClusterPre2(pNode,e,cnt); //先根遍历
case PostOrder:
return ClusterPost2(pNode,e,cnt); //后根遍历
default:
return 0; //末定义处理
}
}
/////////////////////////////////////////////////
//串行聚集, e 存放串行聚集结果, tm 为串行化模式
template<class TElem>
long TTree<TElem>::ClusterPre2(TTreeNodeBinLink<TElem>* pNode,
TElem** e,
long& cnt)
{
if(pNode==NULL) //空返回，结束递归
return 0;
TTreeNodeBinLink<TElem>* p=(TTreeNodeBinLink<TElem>*) pNode->GetFirstSon();
e[cnt++]=&(pNode->GetElem()); //先根访问
ClusterPre2(p,e,cnt); //首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
ClusterPre2(p,e,cnt); //其它儿子
return cnt;
}
/////////////////////////////////////////////////
//串行聚集, e 存放串行聚集结果, tm 为串行化模式
template<class TElem>
long TTree<TElem>::ClusterPost2(TTreeNodeBinLink<TElem>* pNode,
TElem** e,
long& cnt)
{
if(pNode==NULL) //空返回，结束递归
return 0;
TTreeNodeBinLink<TElem>* p=(TTreeNodeBinLink<TElem>*) pNode->GetFirstSon();
ClusterPost2(p,e,cnt); //首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
ClusterPost2(p,e,cnt); //其它儿子
e[cnt++]=&(pNode->GetElem()); //后根访问
return cnt;
}
/////////////////////////////////////////////////
//串行聚集
template<class TElem>
long TTree<TElem>::Cluster(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm)
{
if(pNode==NULL) //空返回，结束递归
return 0;
long cnt=0;
switch(tm)
{
case PreOrder:
return ClusterPre(pNode,pe,cnt); //先根遍历
case PostOrder:
return ClusterPost(pNode,pe,cnt); //后根遍历
default:
return 0; //末定义处理
}
}
/////////////////////////////////////////////////
//串行聚集之先根遍历
template<class TElem>
long TTree<TElem>::ClusterPre(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
long& cnt)
{
if(pNode==NULL) //空返回，结束递归
return 0;
TTreeNodeBinLink<TElem>* p=(TTreeNodeBinLink<TElem>*) pNode->GetFirstSon();
pe[cnt++]=pNode; //先根访问
ClusterPre(p,pe,cnt); //首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
ClusterPre(p,pe,cnt); //其它儿子
return cnt;
}
/////////////////////////////////////////////////
//串行聚集之后根遍历
template<class TElem>
long TTree<TElem>::ClusterPost(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
long& cnt)
{
if(pNode==NULL) //空返回，结束递归
return 0;
TTreeNodeBinLink<TElem>* p=(TTreeNodeBinLink<TElem>*) pNode->GetFirstSon();
ClusterPost(p,pe,cnt); //首儿子
while(p=(TTreeNodeBinLink<TElem>*) pNode->GetNextSon())
ClusterPost(p,pe,cnt); //其它儿子
pe[cnt++]=pNode; //后根访问
return cnt;
}
/////////////////////////////////////////////////
//串行聚集的非递归算法
template<class TElem>
long TTree<TElem>::Cluster2(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm)
{
switch (tm)
{
case PreOrder: //先根遍历
return ClusterPreOrder(pNode,pe);
case PostOrder: //后根访问
return ClusterPostOrder(pNode,pe);
default: //末定义处理
break;
}
return 0;
}
/////////////////////////////////////////////////////////////////
//串行聚集的非递归算法之先根遍历
template<class TElem>
long TTree<TElem>::ClusterPreOrder(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe)
{
if(pNode==NULL) //空返回，不处理
return 0;
long cnt=0,
top=0,
nNodes=0;
if((nNodes=GetHeight(pNode))<=0)
return 0;
TTreeNodeBinLink<TElem>* p=pNode;
TTreeNodeBinLink<TElem>** stack; //记录栈
stack=new TTreeNodeBinLink<TElem>*[nNodes+1];
ASSERT(stack);
while(top||p)
{
if(p!=NULL)
{
pe[cnt++]=p; //访问
top++;
stack[top]=p; //压栈
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
} //先儿子
else
{
p=stack[top];
top--; //出栈
p=p->GetNextBrother(); //后兄弟
}
}
delete[] stack;
return cnt;
}
/////////////////////////////////////////////////////////////////
//串行聚集的非递归算法之后根遍历
template<class TElem>
long TTree<TElem>::ClusterPostOrder(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe)
{
if(pNode==NULL) //空返回，不处理
return 0;
long cnt=0,
top=0,
height=0;
struct TPostTraverseStackNode //记录栈
{
TTreeNodeBinLink<TElem>* pNode;
char isFirst;
};
if((height=GetNumSubNodes(pNode))<=0)
return 0;
TPostTraverseStackNode* stack; //记录栈
stack=new TPostTraverseStackNode[height+1];
TTreeNodeBinLink<TElem>* p=pNode;
while(top||p)
{
if(p!=NULL)
{
top++;
stack[top].pNode=p;
stack[top].isFirst=1; //压栈
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
} //先儿子
else
if(stack[top].isFirst)
{
stack[top].isFirst=0; //设访问记录
pe[cnt++]=stack[top].pNode; //访问
p=stack[top].pNode->GetNextBrother();//后兄弟
}
else
{
top--; //出栈
p=NULL; //置空
}
}
delete[] stack;
return cnt;
}
/////////////////////////////////////////////////
//串行聚集由startLevel到endLevel
template<class TElem>
long TTree<TElem>::ClusterDescendants(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm,
int startLevel,
int endLevel)
{
switch(tm)
{
case PreOrder: //先根遍历
return ClusterDescendantsPre(pNode,pe,startLevel,endLevel);
case PostOrder: //后根遍历
return ClusterDescendantsPost(pNode,pe,startLevel,endLevel);
default: //末定义处理
break;
}
return 0;
}
/////////////////////////////////////////////////
//串行聚集由startLevel到endLevel之先根
template<class TElem>
long TTree<TElem>::ClusterDescendantsPre(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
int startLevel,
int endLevel)
{
long cnt=0, //计数
levelNo=1, //当前层号
height=0, //高度
top=0;
TTreeNodeBinLink<TElem>* p=pNode;
//初始化遍历指针
if((height=GetHeight(pNode))<=0)
return 0;
startLevel=startLevel<0?height+startLevel+1:startLevel;
endLevel=endLevel<0?height+endLevel+1:endLevel; //正负层号处理
struct TTraverseStackNode
{
TTreeNodeBinLink<TElem> *pNode;
long levelNo;
char isFirst;
}; //记录结点
TTraverseStackNode* stack;
stack=new TTraverseStackNode[height+1]; //记录栈
ASSERT(stack);
while(top||p)
{
if(p!=NULL)
{
top++;
stack[top].pNode=p;
stack[top].levelNo=levelNo; //压栈
if(levelNo>=startLevel&&levelNo<=endLevel)
pe[cnt++]=p; //访问
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
if(p!=NULL) //先儿子
levelNo++; //层号自增
}
else
{
p=stack[top].pNode;
levelNo=stack[top].levelNo;
top--; //出栈
p=p->GetNextBrother(); //后兄弟
}
}
return cnt;
}
/////////////////////////////////////////////////
//串行聚集由startLevel到endLevel之后根
template<class TElem>
long TTree<TElem>::ClusterDescendantsPost(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
int startLevel,
int endLevel)
{
long cnt=0, //计数
levelNo=1, //当前层号
height=0, //
top=0;
TTreeNodeBinLink<TElem>* p=pNode;
//初始化遍历指针
if((height=GetHeight(pNode))<=0)
return 0;
startLevel=startLevel<0?height+startLevel+1:startLevel;
endLevel=endLevel<0?height+endLevel+1:endLevel; //正负层号处理
struct TTraverseStackNode
{
TTreeNodeBinLink<TElem> *pNode;
long levelNo;
char isFirst;
}; //记录结点
TTraverseStackNode* stack;
stack=new TTraverseStackNode[height+1]; //记录栈
while(top||p)
{
if(p!=NULL)
{
top++;
stack[top].pNode=p;
stack[top].levelNo=levelNo;
stack[top].isFirst=1; //设标记并进栈
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
if(p!=NULL) //先儿子
levelNo++; //层与自增
}
else
if(stack[top].isFirst)
{
stack[top].isFirst=0; //设访问记录
p=stack[top].pNode;
levelNo=stack[top].levelNo; //取栈顶层号
if(levelNo>=startLevel&&levelNo<=endLevel)
pe[cnt++]=p; //访问
p=p->GetNextBrother();
}
else
{
levelNo=stack[top].levelNo; //取层号
top--; //出栈
p=NULL; //强指空
}
}
return cnt;
}
/////////////////////////////////////////////////
//聚集祖先
template<class TElem>
long TTree<TElem>::ClusterAncestors(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe)
{
TTreeNodeBinLink<TElem>* p;
TTreeNodeBinLink<TElem>** stack; //记录栈
long top=0, //栈顶兼计数器
nodes=0;
if((nodes=GetNumSubNodes(root))<=0)
return 0;
stack=new TTreeNodeBinLink<TElem>*[nodes+1];
ASSERT(stack);
p=(TTreeNodeBinLink<TElem>*) GetRoot(); //取根结点指针
while(top||p)
{
if(p!=NULL)
{
top++;
stack[top]=p; //压栈
if(p==pNode) //找到跳出
break;
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
} //取首儿子
else
p=stack[top]->GetNextBrother(); //取下一兄弟
}
for(long i=1;i<=top;i++) //取串行化结果
pe[i-1]=stack[i];
delete[] stack;
return top-1;
}
/////////////////////////////////////////////////
//聚集祖先
template<class TElem>
long TTree<TElem>::ClusterAncestors(TTreeNodeBinLink<TElem>* pNode,
TElem** e)
{
TTreeNodeBinLink<TElem>* p;
TTreeNodeBinLink<TElem>** stack; //记录栈
long height,
top=0; //计数器
if((height=GetHeight(root))<=0)
return 0;
stack=new TTreeNodeBinLink<TElem>*[height+1];
ASSERT(stack);
p=(TTreeNodeBinLink<TElem>*) GetRoot(); //取根结点指针
while(top||p)
{
if(p!=NULL)
{
top++;
stack[top]=p; //压栈
if(p==pNode) //找到跳出
break;
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
} //取首儿子
else
p=stack[top]->GetNextBrother(); //取下一兄弟
}
for(long i=1;i<=top;i++) //取串行化结果
e[i-1]=&stack[i]->GetElem();
delete[] stack;
return top-1;
}
/////////////////////////////////////////////////
//聚集祖先
template<class TElem>
long TTree<TElem>::ClusterAncestors(TElem& e,
TTreeNodeBinLink<TElem>** pe)
{
TTreeNodeBinLink<TElem>* p;
TTreeNodeBinLink<TElem>** stack; //记录栈
long height=0,
top=0; //计数器
if((height=GetHeight(root))<=0)
return 0;
stack=new TTreeNodeBinLink<TElem>*[height+1];
p=(TTreeNodeBinLink<TElem>*) GetRoot(); //取根结点指针
while(top||p)
{
if(p!=NULL)
{
top++;
stack[top]=p; //压栈
if(p->GetElem()==e) //找到跳出
break;
p=(TTreeNodeBinLink<TElem>*) p->GetFirstSon();
} //取首儿子
else
p=stack[top]->GetNextBrother(); //取下一兄弟
}
for(long i=1;i<=top;i++) //取串行化结果
pe[i-1]=stack[i];
delete[] stack;
return top-1;
}
/////////////////////////////////////////////////
//后辈聚集
template<class TElem>
long TTree<TElem>::ClusterJuniors(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm,
int startLevel,
int endLevel)
{
long levelNo=1,
height=0;
TTreeNodeBinLink<TElem> *rt=(TTreeNodeBinLink<TElem>*) GetRoot();
//取根结点指针
if((height=GetHeight(rt))<=0)
return 0;
startLevel=startLevel<0?height+startLevel+1:startLevel;
endLevel=endLevel<0?height+endLevel+1:endLevel; //正负层号处理
if((levelNo=GetLevel(pNode))<=0) //取层号并判空
return 0;
startLevel=startLevel-levelNo+1;
endLevel=endLevel-levelNo+1; //层号转换
return ClusterDescendants(pNode,pe,tm,startLevel,endLevel);
//调用串行化函数
}
/////////////////////////////////////////////////
//聚集由startLevel到endLevel的前辈
template<class TElem>
long TTree<TElem>::ClusterSeniors(TTreeNodeBinLink<TElem>* pNode,
TTreeNodeBinLink<TElem>** pe,
TTraverseMode tm,
int startLevel,
int endLevel)
{
long levelNo=1,
height=0;
TTreeNodeBinLink<TElem> *rt=(TTreeNodeBinLink<TElem>*) GetRoot();
//取根结点指针
if((height=GetHeight(rt))<=0)
return 0;
startLevel=startLevel<0?height+startLevel+1:startLevel;
endLevel=endLevel<0?height+endLevel+1:endLevel; //正负层号处理
if((levelNo=GetLevel(pNode))<=0) //取层号并判空
return 0;
return ClusterDescendants(rt,pe,tm,startLevel,endLevel);
//调用串行化函数
}
//////////////////////////////////////////////////
//删除 pNode 的 sonNo 号子树
//并处理同其它子树的链接关系
template<class TElem>
long TTree<TElem>::DeleteSubTree(TTreeNodeBinLink<TElem>* pNode,
char sonNo)
{
TTreeNodeBinLink<TElem>* p=(TTreeNodeBinLink<TElem>*) pNode->GetSon(sonNo);
if(sonNo==1) //pNode为首儿子的处理
pNode->firstSon=p->nextBrother;
else
{
TTreeNodeBinLink<TElem>* tp=(TTreeNodeBinLink<TElem>*) pNode->GetSon(sonNo-1);
tp->nextBrother=(TTreeNodeBinLink<TElem>*) pNode->GetSon(sonNo+1);
}
//非首儿子则实现链接
return ReleaseSubs(p);
}
//////////////////////////////////////////////////
//释放以 pNode 为根的子树, 不处理
//pNode 同其它 brother 的链接关系
template<class TElem>
long TTree<TElem>::ReleaseSubs(TTreeNodeBinLink<TElem>* pNode)
{
long cnt=0; //初始化计数
TTreeNodeBinLink<TElem>* tp=NULL;
TTreeNodeBinLink<TElem>* p=(TTreeNodeBinLink<TElem>*) pNode->GetFirstSon();
if(p)
{
tp=p->GetNextBrother();
cnt=ReleaseSubs(p); //处理第一子树
}
while(p=tp)
{
tp=p->GetNextBrother();
cnt+=ReleaseSubs(p); //处理其它子树
}
if(pNode) delete pNode;
return cnt+1;
}
//////////////////////////////////////////////////
//按内容定位, 成功时返回结点指针, 否则返回 NULL
template<class TElem>
TTreeNodeBinLink<TElem>* TTree<TElem>::Locate(TTreeNodeBinLink<TElem>* rt,
TElem& elem)
{
TTreeNodeBinLink<TElem>* p;
//先处理根
if(rt==NULL) //空返回
return NULL;
if(rt->GetElem()==elem) //找到返回
return rt;
p=Locate((TTreeNodeBinLink<TElem>*)rt->GetFirstSon(),elem);
if(p!=NULL) //处理首儿子,找到返回
return p;
//处理其它儿子,找到返回
while(p=(TTreeNodeBinLink<TElem>*) rt->GetNextSon())
if(p=(TTreeNodeBinLink<TElem>*) Locate(p,elem))
return p;
return NULL;
}
///////////////////////////////////////////////////
//打印输出
template<class TElem>
void TTree<TElem>::Print(TTreeNodeBinLink<TElem>* rt,
char mode)
{
TTreeNodeBinLink<TElem>* p;
if(rt==NULL)
return;
switch(mode)
{
case 1:
cout<<" "<<rt->GetElem(); //先根访问
Print((TTreeNodeBinLink<TElem>*) rt->GetFirstSon(),mode);
while(p=(TTreeNodeBinLink<TElem>*) rt->GetNextSon())
Print(p,mode);
break;
case 2:
Print((TTreeNodeBinLink<TElem>*)rt->GetFirstSon(),mode);
while(p=(TTreeNodeBinLink<TElem>*) rt->GetNextSon())
Print(p,mode);
cout<<" "<<rt->GetElem(); //后根访问
break;
default:
cerr<<"无定义遍历!";
}
}
#endif
您所在位置：