文章目录
目录
文章目录
一、先序遍历
1.知识点概述
2.图片理解
编辑
3.代码
二、中序遍历
1.知识点概述
2.图片理解
3.代码
三、后序遍历
1.知识点概念
2.图片理解
3.代码
四、层序遍历
1.知识点概述
2.图片理解
3.代码
五、二叉树的建立
1.补空法
六、二叉树的还原
1.算法步骤
2.代码
总结（二叉树的四种遍历代码）
一、先序遍历
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; }
