CC++：⼆叉树的各种遍历（前序，中序，后序，层次）
（⼀）
所谓的⼆叉树是指树中所有节点的⼦节点个数都不超过2的树。对于⼆叉树，有深度遍历和⼴度遍历，深度遍历有前序、中序以及后序三种遍历⽅法，⼴度遍历即我们平常所说的层次遍历。
前序遍历⾸先访问根结点然后遍历左⼦树，最后遍历右⼦树。在遍历左、右⼦树时，仍然先访问根结点，然后遍历左⼦树，最后遍历右⼦树。
若⼆叉树为空则结束返回，否则：
（1）访问根结点。
（2）前序遍历左⼦树。
（3）前序遍历右⼦树。
需要注意的是：遍历左右⼦树时仍然采⽤前序遍历⽅法。
类似的：
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层次遍历：从上到下，从左到右
前序遍历：A B D E C F
中序遍历：D B E A C F
后序遍历：D E B F C A
层次遍历：A B C D E F
1，创建节点
struct BiTNode{
char data;
struct BiTNode *lchild, *rchild;//左右孩⼦
};
BiTNode*T;
2，先序递归创建⼆叉树表
void CreateBiTree(BiTNode* &T){
//按先序输⼊⼆叉树中结点的值（⼀个字符），空格字符代表空树，
//构造⼆叉树表表⽰⼆叉树T。
char ch;
if ((ch = getchar()) == '#')T = NULL;//其中getchar（）为逐个读⼊标准库函数
else{
T = new BiTNode;//产⽣新的⼦树
T->data = ch;//由getchar（）逐个读⼊来
CreateBiTree(T->lchild);//递归创建左⼦树
CreateBiTree(T->rchild);//递归创建右⼦树
}
}//CreateTree
3，前中后序遍历
void PreOrderTraverse(BiTNode* &T){
//先序递归遍历⼆叉树
if (T){//当结点不为空的时候执⾏
cout << T->data;
PreOrderTraverse(T->lchild);//
PreOrderTraverse(T->rchild);
}
else cout << "";
}//PreOrderTraverse
//================================================中序遍历⼆叉树
void Inorder(BiTNode* &T){//中序递归遍历⼆叉树
if (T){//bt=null退层
Inorder(T->lchild);//中序遍历左⼦树
cout << T->data;//访问参数
Inorder(T->rchild);//中序遍历右⼦树
}
else cout << "";
}//Inorder
//=================================================后序递归遍历⼆叉树  c void Posorder(BiTNode* &T){
if (T){
Posorder(T->lchild);//后序递归遍历左⼦树
Posorder(T->rchild);//后序递归遍历右⼦树
cout << T->data;//访问根结点
}
else cout << "";
先序中序后序遍历二叉树}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。