首先,想如何层次的遍历一个二叉树呢?简单思路分为如下几步:
1.要先创建一个二叉树。(二叉树建立可参考上一篇博客)
2.采用队列思想,先进先出。也就是说先要创建一个队列。
3.首先根入队,然后出队,再入队它的左右孩子,然后左孩子出队,再入队左孩子的左右孩子,再出队右孩子,加入右孩子没有左右孩子为空,就什么就不用干,继续出队左孩子的左右孩子,直到所有元素都出完队时,遍历也就结束了。
代码:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode
{
int data;
struct TreeNode* lchild;
struct TreeNode* rchild;
}TreeNode; //定义树
typedef struct QueueNode
{
TreeNode* node;
struct QueueNode* pre;
struct QueueNode* next;
}; // 定义队
不再详细解释,如果不会看上一篇博客二叉树代码实现。
void creatTree(TreeNode** t,int* index,char* data)
{
char ch;
ch = data[*index];
(*index)++;
if (ch == '#')
*t = NULL;
else
{
*t = (TreeNode*)malloc(sizeof(TreeNode));
assert(*t);
(*t)->data = ch;
creatTree(&((*t)->lchild), index, data);
creatTree(&((*t)->rchild), index, data);
}
}
QueueNode* initQueue()
{
QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));
assert(Q);
Q->node = NULL;
Q->next =Q;
Q->pre = Q;
return Q;
}
//采用循环双链表队列模式,其它链表也可
void enQueue(QueueNode* Q,TreeNode* data)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
assert(newnode);
newnode->node = data;
newnode->pre= Q;
newnode->next = Q;
Q->pre->next = newnode;
Q->pre = newnode;
}
int is_emepty(QueueNode* Q)
{
if (Q->next == NULL)
return 0;
else
return 1;
}
QueueNode* deQueue(QueueNode* Q)
{
if (is_emepty(Q) == 0)
return NULL;
else
{
QueueNode* node = Q->next;
Q->next->next->pre = Q;
Q->next = Q->next->next;
return node;
}
}
void levelTraverse(QueueNode* Q, TreeNode* T)
{
enQueue(Q, T);
while (is_emepty(Q))
{
QueueNode* node = deQueue(Q);
printf("%c ", node->node->data);
if (node->node->lchild)
enQueue(Q, node->node->lchild);
if (node->node->rchild)
enQueue(Q, node->node->rchild);
}
}
void preOrder(TreeNode* t)
{
if (t == NULL)
return;
else
{
printf("%c", t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
int main()
{
TreeNode* t;
char data[100];
int index = 0;
gets_s(data);
creatTree(&t, &index, data);
preOrder(t);
printf("\n");
QueueNode* q = initQueue();
levelTraverse(q, t);
return 0;
}
ab##c##
abc
a b c
D:\VS\test.2\树\Debug\树.exe (进程 7660)已退出,代码为 -1073741819。
按任意键关闭此窗口. . .
adc#d####
adcd
a d c d
D:\VS\test.2\树\Debug\树.exe (进程 12196)已退出,代码为 -1073741819。
按任意键关闭此窗口. . .