c++实现树（⼆叉树）的建⽴和遍历算法（⼀）（前序，中序，
后序）
最近学习树的概念，有关⼆叉树的实现算法记录下来。。。
不过学习之前要了解的预备知识：树的概念；⼆叉树的存储结构；⼆叉树的遍历⽅法。。
⼆叉树的存储结构主要了解⼆叉链表结构，也就是⼀个数据域，两个指针域，（分别为指向左右孩⼦的指针），从下⾯程序1，⼆叉树的存储结构可以看出。
⼆叉树的遍历⽅法：主要有前序遍历，中序遍历，后序遍历，层序遍历。（层序遍历下⼀篇再讲，本篇主要讲的递归法）下篇主要是，之后会有c++模板实现和。
如这样⼀个⼆叉树：
它的前序遍历顺序为：ABDGHCEIF（规则是先是根结点，再前序遍历左⼦树，再前序遍历右⼦树）
它的中序遍历顺序为：GDHBAEICF（规则是先中序遍历左⼦树，再是根结点，再是中序遍历右⼦树）
它的后序遍历顺序为：GHDBIEFCA（规则是先后序遍历左⼦树，再是后序遍历右⼦树，再是根结点）
如果不懂的话，可以参看有关数据结构的书籍。。
1，⼆叉树的存储结构（⼆叉链表）
//⼆叉树的⼆叉链表结构，也就是⼆叉树的存储结构，1个数据域，2个指针域（分别指向左右孩⼦）
typedef struct BiTNode
{
猴年纪念币
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
2，⾸先要建⽴⼀个⼆叉树，建⽴⼆叉树必须要了解⼆叉树的遍历⽅法。
//⼆叉树的建⽴，按前序遍历的⽅式建⽴⼆叉树，当然也可以以中序或后序的⽅式建⽴⼆叉树
void CreateBiTree(BiTree *T)
{
ElemType ch;
cin >> ch;
if (ch == '#')
*T = NULL; //保证是叶结点
el菌菇炖鸡
{
*T = (BiTree)malloc(sizeof(BiTNode));
//if (!*T)
//exit(OVERFLOW); //内存分配失败则退出。
(*T)->data = ch;//⽣成结点
CreateBiTree(&(*T)->lchild);//构造左⼦树
CreateBiTree(&(*T)->rchild);//构造右⼦树
}
}
3.⼆叉树的遍历（递归⽅式，⾮递归⽅式见下篇：）：
巨型猫品种大全主要有三种⽅法：
/递归⽅式前序遍历⼆叉树
void PreOrderTraver(BiTree T, int level)
{
if (T == NULL)
return;
/*此处表⽰对遍历的树结点进⾏的操作，根据你⾃⼰的要求进⾏操作，这⾥只是输出了结点的数据*/ //operation1(T->data);
operation2(T->data, level); //输出了层数
PreOrderTraver(T->lchild, level + 1);
PreOrderTraver(T->rchild, level + 1);
}
//递归⽅式中序遍历⼆叉树
void InOrderTraver(BiTree T,int level)
{
if(T==NULL)
鲜榨苹果汁return;
InOrderTraver(T->lchild,level+1);
//operation1(T->data);
operation2(T->data, level); //输出了层数
InOrderTraver(T->rchild,level+1);
}
//递归⽅式后序遍历⼆叉树
void PostOrderTraver(BiTree T,int level)
{
if(T==NULL)
return;
PostOrderTraver(T->lchild,level+1);
PostOrderTraver(T->rchild,level+1);
//operation1(T->data);
operation2(T->data, level); //输出了层数
}
4.完整代码：
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef char ElemType;
//⼆叉树的⼆叉链表结构，也就是⼆叉树的存储结构，1个数据域，2个指针域（分别指向左右孩⼦）typedef struct BiTNode
{
白萝卜怎么腌ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//⼆叉树的建⽴，按前序遍历的⽅式建⽴⼆叉树，当然也可以以中序或后序的⽅式建⽴⼆叉树
void CreateBiTree(BiTree *T)
{
ElemType ch;
cin >> ch;
if (ch == '#')
*T = NULL; //保证是叶结点
el
{
*T = (BiTree)malloc(sizeof(BiTNode));
//if (!*T)
//exit(OVERFLOW); //内存分配失败则退出。
(*T)->data = ch;//⽣成结点
CreateBiTree(&(*T)->lchild);//构造左⼦树
CreateBiTree(&(*T)->rchild);//构造右⼦树
}
}
//表⽰对遍历到的结点数据进⾏的处理操作，此处操作是将树结点前序遍历输出
void operation1(ElemType ch)
{
cout << ch << "";
}
//此处在输出的基础上，并输出层数形容静的词语
void operation2(ElemType ch, int level)
{
cout << ch << "在第" << level << "层" << endl;
}
//递归⽅式前序遍历⼆叉树
void PreOrderTraver(BiTree T, int level)
如何解压文件{
if (T == NULL)
return;
/*此处表⽰对遍历的树结点进⾏的操作，根据你⾃⼰的要求进⾏操作，这⾥只是输出了结点的数据*/
//operation1(T->data);
operation2(T->data, level); //输出了层数
PreOrderTraver(T->lchild, level + 1);
PreOrderTraver(T->rchild, level + 1);
}
//递归⽅式中序遍历⼆叉树
void InOrderTraver(BiTree T,int level)
{
if(T==NULL)
return;
InOrderTraver(T->lchild,level+1);
//operation1(T->data);
operation2(T->data, level); //输出了层数
InOrderTraver(T->rchild,level+1);
}
//递归⽅式后序遍历⼆叉树
void PostOrderTraver(BiTree T,int level)
{
if(T==NULL)
学习感受
return;
PostOrderTraver(T->lchild,level+1);
PostOrderTraver(T->rchild,level+1);
//operation1(T->data);
operation2(T->data, level); //输出了层数
}
int main()
{
int level = 1; //表⽰层数
BiTree T = NULL;
cout << "请以前序遍历的⽅式输⼊扩展⼆叉树："; //类似输⼊AB#D##C##
CreateBiTree(&T);// 建⽴⼆叉树，没有树，怎么遍历
cout << "递归前序遍历输出为：" << endl;
PreOrderTraver(T, level);//进⾏前序遍历，其中operation1()和operation2()函数表⽰对遍历的结点数据进⾏的处理操作 cout << endl;
cout << "递归中序遍历输出为：" << endl;
InOrderTraver(T, level);
cout << endl;
cout << "递归后序遍历输出为：" << endl;
PostOrderTraver(T, level);
cout << endl;
return0;
}
注意：这⾥有⼏个知识点补充下：
（1）建⽴⼆叉树时，这⾥是以前序遍历的⽅式，输⼊的是扩展⼆叉树，也就是要告诉计算机什么是叶结点，否则将⼀直递归，当输⼊“#”时，指针指向NULL，说明是叶结点。
如图为扩展⼆叉树：（前序遍历为：ABDG##H###CE#I##F##）
（2）operation1( )函数只是对各个结点的输出；
operation2( )函数不仅输出了各个结点，同时输出了结点所在的层数。（调试时可以只先运⾏⼀个）
5.运⾏结果
只是运⾏了operation2( )函数，有层数输出：
或者运⾏只运⾏operation1( )函数
