赞
踩
借助一个辅助队列。
void LevelOrder(BiTree T) { InitQueue(&Q); // 初始化辅助队列 BiTree p; EnQueue(&Q, T); // 将根节点入队 while(!IsEmpty(Q)) // 队列不空则循环 { DeQueue(Q, p); // 队头结点出队 visit(p); if (p->lchild != NULL) { EnQueue(Q, p->lchild); // 左子树不空,则左子树根节点入队 } if (p->rchild != NULL) { EnQueue(Q, p->rchild); // 右子树不空,则右子树根节点入队 } } }
根据上面的代码思路,需要实现两个数据结构,一个二叉树,一个队列,需要实现的功能有
#include <stdio.h> #include <stdlib.h> using namespace std; typedef char TElemType; const int MAXSIZES = 50; // 二叉树的存储结构 typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; typedef BiTree QElemType; // 队列的存储结构 typedef struct { QElemType data[MAXSIZES]; int front; int rear; }SqQueue; // 通过前序遍历创建二叉树 void CreateBiTree(BiTree *T) { TElemType ch; scanf("%c", &ch); if (ch == '#') { *T = NULL; } else { *T = (BiTree) malloc(sizeof(BiTNode)); if (!T) { exit(0); } (*T)->data = ch; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } // 初始化队列 void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; } // 辅助队列的入队操作 void EnQueue(SqQueue *Q, QElemType q) { if ((Q->rear + 1) % MAXSIZES == Q->front) return; Q->data[Q->rear] = q; Q->rear = (Q->rear + 1) % MAXSIZES; } // 辅助队列的出队操作 void DeQueue(SqQueue *Q, QElemType *q) { if (Q->front == Q->rear) return; *q = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZES; } // 二叉树的中序遍历 void InOrderTraverse(BiTree T) { if (!T) { return; } InOrderTraverse(T->lchild); printf("%c", T->data); InOrderTraverse(T->rchild); } // 二叉树的层序遍历 void LevelOrder(BiTree T) { SqQueue Q; InitQueue(&Q); // 初始化辅助队列 BiTree p; EnQueue(&Q, T); // 将根节点入队 while(Q.front != Q.rear) // 队列不空则循环 { DeQueue(&Q, &p); // 队头结点出队 printf("%c", p->data); if (p->lchild != NULL) { EnQueue(&Q, p->lchild); // 左子树不空,则左子树根节点入队 } if (p->rchild != NULL) { EnQueue(&Q, p->rchild); // 右子树不空,则右子树根节点入队 } } } int main() { BiTree t; printf("请按照前序扩展二叉树进行输入:(#表示空结点)\n"); CreateBiTree(&t); printf("中序遍历: "); InOrderTraverse(t); printf("\n层序遍历: "); LevelOrder(t); return 0; }
参考:
层序遍历思路来《王道数据结构》
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。