需求:
以层遍历一棵二叉树,二叉树的结点结构如下
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(" "); level_visit_tree(tree, n); printf(" "); system("pause"); return 0; }