|
最近学习数据结构，查找了很多资料，没有找到关于该非递归算法的题解。自己写了一个，如有谬误或者不足还请批评指正
该算法的关键是用队列存储每一层的结点，在存储下一层时要把上一层的全部出队，难度在于，如何判断上一层全部出队。
先上代码
Status GetDepth(CSTree T){
if(!T) return ERROR;
if(!T->firstchild) return 1;
int Depth=0;
CSTree p=T;
LinkQueue Q; InitQueue(Q);int i=0,j=1;
EnQueue(Q,p);
while(!EmptyQueue(Q)){
for(i=0;j>0;j--){//j记录该层的结点个数i,将该层所有的结点都出队，j层所有结点的下一层都入队。
DeQueue(Q,p);
if(p->firstchild) {p=p->firstchild;EnQueue(Q,p);i++;
while(p->nextsibling){
p=p->nextsibling;
EnQueue(Q,p);
i++;
}
}
}Depth++;j=i;
}
return Depth;
}
算法的关键是在while(!EmptyQueue)中使用了一个for循环,i是每一层的结点个数，将i赋值给j 。每进行一次while 都将i初始化为0，然后通过j的自减将每一个结点的孩子存放到队列里，并将该层所有结点出队。每完成一层操作，depth+1。 下面是完整代码：
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define TRUE 1
#define FLASE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char ElemType;
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
typedef struct{
CSTree *base;
CSTree *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S){
S.base=(CSTree *)malloc(sizeof(CSNode));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,CSTree &e){
if(S.top-S.base>=S.stacksize){
S.base=(CSTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(CSTree));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,CSTree &e){
if(S.base==S.top) return ERROR;
e=*--S.top;
return OK;
}
Status StackEmpty(SqStack S){
if(S.base==S.top) return OK;
else
return ERROR;
}
typedef struct QNode{
CSTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
Status EnQueue (LinkQueue &Q,CSTree e){
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeQueue (LinkQueue &Q,CSTree &e){
QueuePtr p;
if(Q.front == Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear == p) Q.rear=Q.front;
free(p);
return OK;
}
Status EmptyQueue(LinkQueue Q){
if(Q.front == Q.rear) return 1;
else
return 0;
}
Status CreateCSTree(CSTree &T,SqStack &S){
ElemType ch;
T=(CSNode *)malloc(sizeof(CSNode));
if(!T) exit(OVERFLOW);
scanf("%c",&ch);
T->data=ch;
Push(S,T);
while(!StackEmpty(S)){
scanf("%c",&ch);
if(ch!='#'){
T->firstchild=(CSNode *)malloc(sizeof(CSNode));
T->firstchild->data=ch;
Push(S,T->firstchild);
}
else
T->firstchild=NULL;
scanf("%c",&ch);
if(ch!='#'){
T->nextsibling=(CSNode *)malloc(sizeof(CSNode));
T->nextsibling->data=ch;
Push(S,T->nextsibling);
}
else
T->nextsibling=NULL;
Pop(S,T);
}
return OK;
}
Status GetDepth(CSTree T){
if(!T) return ERROR;
if(!T->firstchild) return 1;
int Depth=0;
CSTree p=T;
LinkQueue Q; InitQueue(Q);int i=0,j=1;
EnQueue(Q,p);
while(!EmptyQueue(Q)){
for(i=0;j>0;j--){//j记录该层的结点个数i,将该层所有的结点都出队，j层所有结点的下一层都入队。
DeQueue(Q,p);
if(p->firstchild) {p=p->firstchild;EnQueue(Q,p);i++;
while(p->nextsibling){
p=p->nextsibling;
EnQueue(Q,p);
i++;
}
}
}Depth++;j=i;
}
return Depth;
}
int main(){
CSTree T;
SqStack S;
InitStack(S);
printf("Create a Tree :\n");
CreateCSTree(T,S);
printf("Get the depth of the Tree!\n");
printf("The depth of the tree is: %d\n",GetDepth(T));
}
创建也是用非递归方法创建的，创建顺序有点乱，大家自己可以用自己习惯的方法创建。
|