需求：
以层遍历一棵二叉树，二叉树的结点结构如下
struct tree_node{
struct tree_node *lc;
struct tree_node *rc;
int data;
};
例如：
// 1
// / \
// 2 3
// /
// 4
// \
// 5
层遍历后输出1,2,3,#,#,4,#,#,5，#代表该结点为空。
要求：空间复杂度为O(n)，时间复杂度为O(n)
思路：
使用一个大小为n的数组，以逐层结点方式记录该数组；
在扫描上一层结点的同时，可以知道下一层结点的非空结点数目；
扫描本层同时打印出下层结点的值或空值。
数组在这里起到可重复索引上一层结点的作用。
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> struct tree_node;
struct tree_node{
struct tree_node *lc;
struct tree_node *rc;
int data;
};
typedef struct tree_node treenode;
//*先序为DLR(D:根节点,L:左子树,R:右子树)
// a
// / \
// b c
// / \ / \
// d * * e
//*/
//先序序列为abdce,输入为abd***c*e**(*表示空格,代表空树),输入按满二叉树输入
//每一个节点都是一个子树的根节点
void pre_create_tree(treenode **T){ //递归法
int datatemp; fflush(stdin);
scanf("%d", &datatemp); if(datatemp==-1){
*T=NULL;
}
else{
if((*T=(treenode*)malloc(sizeof(treenode)))==NULL){
exit(0);
}
else{
(*T)->data=datatemp;
(*T)->lc = (*T)->rc = NULL;
pre_create_tree(&(*T)->lc);
pre_create_tree(&(*T)->rc);
}
}
} void pre_visit_tree(treenode *T, int *n){ //递归法
if(T!=NULL){
n++;
printf("%d ", T->data);
pre_visit_tree(T->lc, n);
pre_visit_tree(T->rc, n);
}
else{
return;
}
} typedef struct{
treenode* node;
int kid;
}treenode_info; //思路：用n个元素数组以层顺序记录二叉树
// 1
// / \
// 2 3
// /
// 4
// \
// 5
//记录为： 1 2 3 4 5
//记录层元素个数，在遍历上一层时，就可以求得下一层的元素个数，然后就可知 1 | 2 3 | 4 | 5 的信息了
void level_visit_tree(treenode *T, int n){
treenode **myinfo, **tt;
treenode *ptemp, **temp;
int k=1, levelcnt=0, cnt, levelcnttemp, prelevelcnt=1;
//levelcnt:当前层元素个数,levelcnttemp:下一层元素个数 //初始化循环记录
myinfo = (treenode**)malloc(sizeof(treenode*)*n);
*myinfo = T;
if(T->lc!=NULL)
levelcnt++;
if(T->rc!=NULL)
levelcnt++;
temp = myinfo;
tt = temp+1;
printf("%d ", (*temp)->data);
while(levelcnt){
//本层没有元素,可以结束循环了
for(cnt=0, levelcnttemp=0; cnt<levelcnt; ){ //tt:从数组myinfo中指向本层元素,遍历本层元素,有cnt计数,不用怕访问到其它层的元素
if((*temp)->lc!=NULL){ //打印本层元素的孩子,有则输出孩子值,没有就输出#
printf("%d ", (*temp)->lc->data);
*(tt+cnt) = (*temp)->lc;
if((*(tt+cnt))->lc!=NULL)
levelcnttemp++;
if((*(tt+cnt))->rc!=NULL)
levelcnttemp++;
cnt++;
}
else
printf("# ");
if((*temp)->rc!=NULL){
printf("%d ", (*temp)->rc->data);
*(tt+cnt) = (*temp)->rc;
if((*(tt+cnt))->lc!=NULL)
levelcnttemp++;
if((*(tt+cnt))->rc!=NULL)
levelcnttemp++;
cnt++;
}
else
printf("# ");
temp++;
}
tt = tt+cnt;
levelcnt=levelcnttemp;
}
} int main(void){
int n;
treenode *tree; pre_create_tree(&tree);
pre_visit_tree(tree, &n); printf("\n");
level_visit_tree(tree, n); printf("\n"); system("pause");
return 0;
}