数据结构中二叉树的层次遍历算法（知识分享数据结构）
数据结构中二叉树的层次遍历算法（知识分享数据结构）输入：ABC_ _DE_G_ _F_ _ _注意创建的时候如果没有左右子树要输入空格后序：CGEFDBA层次：ABCDEFGtypedef char TElemType; typedef int Status; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild *rchild; }BiTNode *BiTree; Status PreCreateBiTree(BiTree &T);//先序输入二叉树 Status PreOrderTraverse(BiTree T Status(*Visit)(TElemType e)); Status InOrderTraverse1(BiTree T Status(*Visit)(TElemType e)); Status InOrderTraverse2(B
今日份分享：将树的基本操作C语言实现，主要考察树的先序，中序，后序和层次遍历方法
二叉树如图：
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层次：ABCDEFG
BiTree.h：typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild *rchild;
}BiTNode *BiTree;
Status PreCreateBiTree(BiTree &T);//先序输入二叉树
Status PreOrderTraverse(BiTree T Status(*Visit)(TElemType e));
Status InOrderTraverse1(BiTree T Status(*Visit)(TElemType e));
Status InOrderTraverse2(BiTree T Status(*Visit)(TElemType e));
Status PostOrderTraverse(BiTree T Status(*Visit)(TElemType e));
Status LevelOrderTraverse(BiTree T Status(*Visit)(TElemType e));
Status Visit(TElemType e);
Status GetDepth(BiTree T);
Status CountNode(BiTree T int &d);
主要函数：
① 先序创建二叉树注意创建的时候如果没有左右子树要输入空格
输入：ABC_ _DE_G_ _F_ _ _
Status PreCreateBiTree(BiTree &T)
{
char ch;
ch=getchar();
if(ch==' ')T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);
T->data=ch;
PreCreateBiTree(T->lchild);
PreCreateBiTree(T->rchild);
}
return OK;
}② 先序遍历（递归算法）
Status PreOrderTraverse(BiTree T Status(*Visit)(TElemType e))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->lchild Visit))
if(PreOrderTraverse(T->rchild Visit))return OK;
return ERROR;
}else return OK;
}③ 中序遍历（递归算法）
Status InOrderTraverse2(BiTree T Status(*Visit)(TElemType e))
{
if(T){
InOrderTraverse2(T->lchild Visit);
Visit(T->data);
InOrderTraverse2(T->rchild Visit);
}
return OK;
}④ 中序遍历（非递归算法）
注意此处需要包含C STL头文件include<stack>
Status InOrderTraverse1(BiTree T Status(*Visit)(TElemType e))
{
stack<BiTree>S;
BiTree p;
S.push(T);
while(!S.empty()){
while(p=S.top())S.push(p->lchild);
p=S.top();
S.pop();
if(!S.empty()){
p=S.top();
S.pop();
if(!Visit(p->data))return ERROR;
S.push(p->rchild);
}
return OK;
}
}⑤ 后序遍历（递归算法）
Status PostOrderTraverse(BiTree T Status(*Visit)(TElemType e))
{
if(T){
PostOrderTraverse(T->lchild Visit);
PostOrderTraverse(T->rchild Visit);
Visit(T->data);
}
return OK;
}⑥ 层次遍历（使用QUEUE）
可以包含STL<queue>或者定义一个数组，使用循环队列即可。
Status LevelOrderTraverse(BiTree T Status(*Visit)(TElemType e))
{
BiTree p;
BiTNode *Q[100];
int front rear;
front=rear=-1;
rear ;
Q[rear]=T;
while(front!=rear){
front=(front 1)0;
p=Q[front];
Visit(p->data);
if(p->lchild!=NULL){
rear=(rear 1)0;
Q[rear]=p->lchild;
}
if(p->rchild!=NULL){
rear=(rear 1)0;
Q[rear]=p->rchild;
}
}
return OK;
}⑦ Visit函数此处使用的是输出
Status Visit(TElemType e)
{
printf("%c " e);
return OK;
}⑧ 计算树的节点数
Status CountNode(BiTree T int &d)
{
if(T){
d ;
CountNode(T->lchild d);
CountNode(T->rchild d);
}
return OK;
}⑨ 计算树的深度
Status GetDepth(BiTree T)
{
int hl hr;
if(T==NULL)return 0;
else{
hl=GetDepth(T->lchild);
hr=GetDepth(T->rchild);
if(hl>hr)return hl 1;
else return hr 1;
}
}Main函数：
int main()
{
printf("Create\n");
BiTree T;
PreCreateBiTree(T);
printf("先序PreTraverse:\n");
PreOrderTraverse(T Visit);
printf("\n中序InTraverse:\n");
InOrderTraverse2(T Visit);
printf("\n后序PostTraverse:\n");
PostOrderTraverse(T Visit);
printf("\nLevelTraverse:\n");
LevelOrderTraverse(T Visit);
printf("\n");
CountNode(T d);
printf("\n节点数:%d\n" d);
printf("树的深度:%d\n" GetDepth(T));
system("pause");
return 0;
}
注意：
1. 遍历函数可以写成递归和非递归，递归函数更加简洁。
2. 层次遍历需要使用队列，可以包含C STL<queue>或者定义一个数组，使用循环队列即可。注意每次判断时要把队列的头赋值给临时变量P，左右子树从队尾插入。
3.先序创建树时，要注意创建的时候如果没有左右子树要输入空格
输入：ABC_ _DE_G_ _F_ _ _
————
希望对大家有帮助，有什么C/C 学习上的问题也可以来和我交流！
写在最后：对于准备学习C/C 编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！
编程学习书籍分享：
编程学习视频分享：
整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）
欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！
对于C/C 感兴趣可以关注小编在后台私信我：【编程交流】一起来学习哦！可以领取一些C/C 的项目学习视频资料哦！已经设置好了关键词自动回复，自动领取就好了！
