/*二叉树的层次遍历，借助队列来实现，这里用数组实现队列*/
#include
#include
#include
typedef struct node
{
char data; //节点
struct node *lchild, *rchild; //左右孩子的指针
}*BiTree, BiTNode;
void creat(BiTree *T) // 递归法建树 ,用先序遍历法输入数据，如：abc***d**
{
char ch;
scanf("%c",&ch);
if (ch == '*') //*代表结束
(*T) = NULL;
else
{
if (! ( (*T) = (BiTree) malloc(sizeof(BiTNode))))
exit(1);
(*T)->data = ch;
creat( & ((*T)->lchild));
creat( & ((*T)->rchild));
}
}
/*层次遍历树,用队列实现*/
void levelTraverse(BiTree T)
{
BiTree Queue[20]; //注意，要保证数组队列够用
BiTree p;
int front=0, rear=0; /*表示队头指针和队尾指针*/
if (T)
{
p = T;
Queue[rear] = p; //根指针入队
rear = (rear+1) % 20; //队尾指针加1对20求余可以实现循环队列，合理利用空间
while (front != rear) //队不空
{
p = Queue[front]; //出队,进行访问
printf("%c",p->data);
front = (front+1) % 20; //实现循环
if (p->lchild) //如果p有左子树，则左子树入队
{
Queue[rear] = p->lchild;
rear = (rear+1) % 20;
}
if (p->rchild) //如果p有右子树，将右子树入队
{
Queue[rear] = p->rchild;
rear = (rear+1) % 20;
}
}//while
}//if
}
int main()
{
BiTree T;
creat(&T);
printf("层次遍历的结果\n");
levelTraverse(T);
printf("\n");
return 0;
} |
转播
