详解二叉树遍历（C/C++）
【摘要】 提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录目录文章目录一、先序遍历1.知识点概述2.图片理解编辑 3.代码二、中序遍历1.知识点概述2.图片理解3.代码三、后序遍历1.知识点概念2.图片理解3.代码四、层序遍历1.知识点概述2.图片理解3.代码五、二叉树的建立1.补空法六、二叉树的还原1.算法步骤2.代码 总结（二叉树的四种遍历代码）一、先序遍历1.知识点...
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
一、先序遍历
1.知识点概述
若二叉树为空，则空操作返回，否先访问根结点，然后先序遍历左子树，再先序遍历右子树
简记 ： 根左右
2.图片理解
顺序为 A B D E C F G
思路：
3.代码
代码如下
void preorder(Btree T)//先序遍历
{
if(T)
{
cout<<T->data<<" ";
preorder(T->lchild);
preorder(T->rchild);
}
}
二、中序遍历
1.知识点概述
中序遍历是指中序遍历根结点的左子树，然后访问根结点，在中序遍历右子树（左子树为空或者已经遍历才能访问根）
简记：左根右
2.图片理解
顺序为 D B E A F G C
最开始看A的左节点B, B的最结点不为空，然后看D，D的左节点为空，访问D，然后此时的
B做左节点D，已经遍历，可以访问B，然后看E，E因为左节点为空，可以访问，然后看根结点A，访问A，看 C ，C结点不为空看F,F左节点为空，可以访问F，G的左节点为空，访问G,最后C的左节点完成访问，可以访问C。
3.代码
代码如下
void inorder(Btree T)//中序遍历
{
if(T)
{
inorder(T->lchild);
cout<<T->data<<" ";
inorder(T->rchild);
}
}三、后序遍历
1.知识点概念
后序遍历是指后序遍历左子树，后序遍历右子树，然后访问根（左子树、右子树为空或已遍历才能访问根）
简记：左右根
2.图片理解
最开始看B,但是B不满足条件左右都不为空，所以不遍历，所以遍历D，因D左右子树皆为空，访问D,然后看E，它的左右子树为空，所以访访问E，B的左右结点都已经遍历可以访问B,然后看C，C的左节点不为空，看F,F的右节点不为空，看G，G满足条件，访问G，此时F左为空，右已遍历，可以访问F，然后F遍历了，C右又为空，所以C可以访问，最后访问A。
最终顺序为：D E B G F C A
3.代码
代码如下
void posorder(Btree T)//后序遍历
{
if(T)
{
posorder(T->lchild);
posorder(T->rchild);
cout<<T->data<<" ";
}
}四、层序遍历
1.知识点概述
从根结点开始访问，从上到下逐层遍历，在同一层中，按照从左到右的顺序逐个访问
2.图片理解
顺序为 A B C D E F G
算法思想：
① 初始化一个辅助队列
②根结点入队
③若队列非空，则对头结点出队，访问该节点，并将其左右孩子插入队尾
3.代码
代码如下
bool Leveltraverse(Btree T)
{
Btree p;
if(!T)
return false;
queue<Btree>Q; //创建一个普通队列(先进先出)，里面存放指针类型
Q.push(T); //根指针入队
while(!Q.empty()) //如果队列不空
{
p=Q.front();//取出队头元素作为当前扩展结点livenode
Q.pop(); //队头元素出队
cout<<p->data<<" ";
if(p->lchild)
Q.push(p->lchild); //左孩子指针入队
if(p->rchild)
Q.push(p->rchild); //右孩子指针入队
}
return true;
}五、二叉树的建立
1.补空法
补空法是指如果左子树或右子树为空时，用特殊字符补空，如 “#”，然后按照先序遍历的顺序，得到先序遍历序列，根据该序列创建二叉树
步骤
输入补空后的二叉树先序遍历序列；
如果ch = '#',T = NULL; 否则创建一个新结点T,令 T->date = ch; 递归创建T的左子树，递归创建T的右子树。
代码如下：
void Createtree(Btree &T) /*创建二叉树函数*/
{
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
cin >> ch;
if(ch=='#')
T=NULL; //递归结束，建空树
else{
T=new Bnode;
T->data=ch; //生成根结点
Createtree(T->lchild); //递归创建左子树
Createtree(T->rchild); //递归创建右子树
}
}六、二叉树的还原
列如 ：已知一棵二叉树的先序序列ABDECFG 和中序序列DBEAFGC，画出这棵二叉树。
1.算法步骤
1. 先序序列的第一个字符为根；
2. 在中序列中，以根为中心划分左右子树；
3. 还原左右子树。
2.代码
#include <iostream>
using namespace std;
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BiTNode,*BiTree;
BiTree pre_mid_createBiTree(char *pre,char *mid,int len) //前序中序还原建立二叉树
{
if(len==0)
return NULL;
char ch=pre[0]; //找到先序中的第一个结点
int index=0;
while(mid[index]!=ch)//在中序中找到的根结点的左边为该结点的左子树，右边为右子树
{
index++;
}
BiTree T=new BiTNode;//创建根结点
T->data=ch;
T->lchild=pre_mid_createBiTree(pre+1,mid,index);//建立左子树
T->rchild=pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);//建立右子树
return T;
}
BiTree pro_mid_createBiTree(char *last,char *mid,int len)//后序中序还原建立二叉树
{
if(len==0)
return NULL;
char ch=last[len-1]; //取得后序遍历顺序中最后一个结点
int index=0;//在中序序列中找根结点，并用index记录长度
while(mid[index]!=ch)//在中序中找到根结点，左边为该结点的左子树，右边为右子树
index++;
BiTree T=new BiTNode;//创建根结点
T->data=ch;
T->lchild=pro_mid_createBiTree(last,mid,index);//建立左子树
T->rchild=pro_mid_createBiTree(last+index,mid+index+1,len-index-1);//建立右子树
return T;
}
void pre_order(BiTree T)//前序递归遍历二叉树
{
if(T)
{
cout<<T->data;
pre_order(T->lchild);
pre_order(T->rchild);
}
}
void pro_order(BiTree T)//后序递归遍历二叉树
{
if(T)
{
pro_order(T->lchild);
pro_order(T->rchild);
cout<<T->data;
}
}
int main()
{
BiTree T;
int n;
char pre[100],mid[100],last[100];
cout<<"1. 前序中序还原二叉树\n";
cout<<"2. 后序中序还原二叉树\n";
cout<<"0. 退出\n";
int choose=-1;
while(choose!=0)
{
cout<<"请选择:";
cin>>choose;
switch (choose)
{
case 1://前序中序还原二叉树
cout<<"请输入结点的个数:"<<endl;
cin>>n;
cout<<"请输入前序序列:"<<endl;
for(int i=0;i<n;i++)
cin>>pre[i];
cout<<"请输入中序序列:"<<endl;
for(int i=0;i<n;i++)
cin>>mid[i];
T=pre_mid_createBiTree(pre,mid,n);
cout<<endl;
cout<<"二叉树还原成功，输出其后序序列:"<<endl;
pro_order(T);
cout<<endl<<endl;
break;
case 2://后序中序还原二叉树
cout<<"请输入结点的个数:"<<endl;
cin>>n;
cout<<"请输入后序序列:"<<endl;
for(int i=0 ;i<n;i++)
cin>>last[i];
cout<<"请输入中序序列:"<<endl;
for(int i=0 ;i<n;i++)
cin>>mid[i];
T=pro_mid_createBiTree(last,mid,n);
cout<<endl;
cout<<"二叉树还原成功，输出其先序序列:"<<endl;
pre_order(T);
cout<<endl<<endl;
break;
}
}
return 0;
}总结（二叉树的四种遍历代码）
#include <iostream>
#include <queue>//引入队列头文件
using namespace std;
typedef struct Bnode /*定义二叉树存储结构*/
{ char data;
struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T) /*创建二叉树函数*/
{
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
cin >> ch;
if(ch=='#')
T=NULL; //递归结束，建空树
else{
T=new Bnode;
T->data=ch; //生成根结点
Createtree(T->lchild); //递归创建左子树
Createtree(T->rchild); //递归创建右子树
}
}
void preorder(Btree T)//先序遍历
{
if(T)
{
cout<<T->data<<" ";
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(Btree T)//中序遍历
{
if(T)
{
inorder(T->lchild);
cout<<T->data<<" ";
inorder(T->rchild);
}
}
void posorder(Btree T)//后序遍历
{
if(T)
{
posorder(T->lchild);
posorder(T->rchild);
cout<<T->data<<" ";
}
}
bool Leveltraverse(Btree T)
{
Btree p;
if(!T)
return false;
queue<Btree>Q; //创建一个普通队列(先进先出)，里面存放指针类型
Q.push(T); //根指针入队
while(!Q.empty()) //如果队列不空
{
p=Q.front();//取出队头元素作为当前扩展结点livenode
Q.pop(); //队头元素出队
cout<<p->data<<" ";
if(p->lchild)
Q.push(p->lchild); //左孩子指针入队
if(p->rchild)
Q.push(p->rchild); //右孩子指针入队
}
return true;
}
int main()
{
Btree mytree;
cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
Createtree(mytree);//创建二叉树
cout<<endl;
cout<<"二叉树的先序遍历结果："<<endl;
preorder(mytree);//先序遍历二叉树
cout<<endl;
cout<<"二叉树的中序遍历结果："<<endl;
inorder(mytree);//中序遍历二叉树
cout<<endl;
cout<<"二叉树的后序遍历结果："<<endl;
posorder(mytree);//后序遍历二叉树
cout<<endl;
cout<<"二叉树的层次遍历结果："<<endl;
Leveltraverse(mytree);//层次遍历二叉树
return 0;
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）