二叉树层次遍历与创建

/二叉树的竖向显示就是二叉树的按层显示。
编写数据结构和算法来实现。要求：算法输入参数为一颗二叉树，无输出参数，显示过程在函数体内部直接执行/
分析过程
1、先序创建二叉树，输入一个值作为结点，申请空间存放数据，递归访问左右孩子结点。用#表示结点为空，同时跳出一侧的递归循环。
2、层次遍历二叉树。输入二叉树头节点的指针。先将头节点入队，将结点指针交给P，后出队。然后再将P左右孩子入队。循环至全部遍历。

注意递归创建过程：
因为先序创建二叉树是左右递归创建，所以一个结束符是结束了一侧的递归调用，两个结束符号结束两侧的递归调用。可以理解将普通二叉树看作满二叉树，结束符是满二叉树当中的空位。

#define MAX_SIZE  20            //层次遍历的队列大小
#define elemtype char           //类型为char                        
typedef struct BTNode
{  elemtype  data ;
struct BTNode  *Lchild , *Rchild;
}BTNode,*Btree ;               //二叉树数据结构
typedef struct  {Btree queue[MAX_SIZE];int front,rear;
}Queue;                        //层次遍历队列
void preoder_initBtree ( Btree &btree );    //先序遍历创建二叉树
void visit(Btree &btree);                   //访问函数
void leveorder(Btree &btree);               //层次遍历函数
#include
#include
void preoder_initBtree(Btree &btree){                //先序创建二叉树elemtype ch;scanf("%c", &ch);                                //输入一个值作为结点if(ch =='#')                                     //#号标识结点为空跳出递归{btree=NULL;}else{btree=(Btree)malloc(sizeof(BTNode));         //申请空间btree->data=ch;preoder_initBtree(btree->Lchild);            //左孩子递归preoder_initBtree(btree->Rchild);            //右孩子递归}
}
void visit(Btree &btree)
{if(btree!=NULL)printf("%c\t", btree->data);                    //打印结点数据
}
void leveorder(Btree &T)
{
Queue q;                                           //层次变量的队列
Btree p;                                            
q.front=0;
q.rear=0;                                          //队列初始化
q.queue[q.rear]=T;                                 //头节点入队列
q.rear++;                                          //队尾加1
while(q.front!=q.rear){                             p=q.queue[q.front];                            visit(q.queue[q.front]);q.front++;                                     //结点出队队首减1if(p->Lchild){q.queue[q.rear]=p->Lchild;                 q.rear++;                                    //访问左孩子入队尾}if(p->Rchild){q.queue[q.rear]=p->Rchild;q.rear++;                                    //右孩子入队尾}}
}
int main()
{
Btree btree;
printf("put in the Bitree: \n");
preoder_initBtree(btree);
//Print(btree);
leveorder(btree);
while(1);
return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！