チェーン式の列を利用して、二叉樹の階層遍歴(C言語)を実現します.
7819 ワード
ルール:は、木が空かどうかを判断し、空ならば戻ります. が空でなければ、木の第一階からです.つまりルートノードがアクセスを開始します. は、上から下へ層ごとに巡回し、同じ層において、左から右への順にノードを個別に訪問する.
#include<stdio.h>
#include<stdlib.h>
typedef struct tree{
char date;
struct tree*pLeft,*pRight;
}TREE,*PTREE;
typedef struct List{
PTREE pBit;
struct List *pNext;
}NODE,*PNODE;
typedef struct queue{
PNODE front;
PNODE rear;
}QUEUE,*PQUEUE;
void init_queue(PQUEUE); /* */
void en_queue(PQUEUE,PTREE); /* */
PTREE out_queue(PQUEUE); /* */
void creat_tree(PTREE*); /* */
void traverse_tree(PTREE); /* */
int main (void)
{
PTREE pT = NULL;
creat_tree(&pT);
traverse_tree(pT);
return 0;
}
void init_queue(PQUEUE pQ)
{
pQ->rear = pQ->front = (PNODE)malloc(sizeof(NODE));
if(pQ->front == NULL)
exit(0);
pQ->front->pNext = NULL;
return;
}
void en_queue(PQUEUE pQ,PTREE pT)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(pNew == NULL)
exit(0);
else
{
pNew->pBit = pT;
pNew->pNext = NULL;
pQ->rear->pNext = pNew;
pQ->rear = pNew;
return;
}
}
PTREE out_queue(PQUEUE pQ)
{
PNODE p = pQ->front->pNext;
if(pQ->front == pQ->rear)
return NULL;
pQ->front->pNext = p->pNext;
if(pQ->rear == p)
pQ->rear = pQ->front;
return p->pBit;
}
void creat_tree(PTREE *pT)
{
char a;
scanf("%c",&a);
if(a == '#')
*pT = NULL;
else
{
(*pT) = (PTREE)malloc(sizeof(TREE));
if((*pT) == NULL)
exit(0);
(*pT)->date = a;
creat_tree(&(*pT)->pLeft);
creat_tree(&(*pT)->pRight);
return;
}
}
void traverse_tree(PTREE pT)
{
PTREE t = NULL;
QUEUE pQ;
init_queue(&pQ);
if(pT != NULL)
en_queue(&pQ,pT); /* ， */
else
return;
while(pQ.front != pQ.rear) /* */
{
t = out_queue(&pQ); /* */
printf("%c\t",t->date);
if(t->pLeft != NULL) /* */
en_queue(&pQ,t->pLeft); /* */
if(t->pRight != NULL) /* */
en_queue(&pQ,t->pRight); /* */
}
printf("
");
return;
}