1. 二叉树的遍历
先序遍历、中序遍历、后序遍历，无论这三种遍历的哪一种，左子树一定先与右子树遍历；所谓的“先中后”是指访问根结点顺序在遍历中的位置。例外还有层次遍历，即广度优先遍历
<img src="https://tva1.sinaimg.cn/large/006tNbRwly1g9ncg3d3gtj30py0eg3z4.jpg" style="zoom:40%;" />
-
先序：根结点->>左子树->>右子树
void preOrder(node* root){ //先序遍历 if(root == NULL){ return; } preOrder(root->lchild); preOrder(root->rchild); }
-
中序：左子树->>根结点->>右子树
void inOrder(node* root){ //中序遍历 if(root == NULL){ return; } inOrder(root->lchild); printf("%d",root->data); inOrder(root->rchild); }
-
后序：左子树->>右子树->>根结点
void postOrder(node* root){ //后序遍历 if(root == NULL){ return; } postOrder(root->lchild); postOrder(root->rchild); printf("%d",root->data); } -
层次遍历（BFS遍历）
void BFS(node* root){ //层次遍历 queue<node*> q; q.push(root); while(!q.empty()){ node* now = q.front(); q.pop(); printf("%d",now->data); if(now->lchild != NULL) q.push(now->lchild); if(now->rchild != NULL) q.push(now->rchild); } }
2. 创建二叉树
中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建唯一的二叉树，而后三者两两搭配或是三个一起上都无法构建唯一的二叉树。原因是先序、后序、层序均是提供根结点，功能是相同的，都必须由中序序列来区分出左右子树。
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
struct node{
node* lchild;
node* rchild;
int data;
};
int n;
vector<int> pre;
vector<int> in;
vector<int> post;
vector<int> layer;
//根据中序和后序，创建二叉树
node* createByPostAndIn(int postL, int postR, int inL, int inR){
if(postL > postR) return NULL;
node* root = new node;
root->data = post[postR];
int k;
for(k = inL; k <= inR; k++){
if(in[k] == post[postR]){
break;
}
}
int numLeft = k - inL; //左子树的结点个数
root->lchild = createByPostAndIn(postL, postL + numLeft - 1, inL, k - 1);
root->rchild = createByPostAndIn(postL + numLeft, postR - 1, k + 1, inR);
return root;
}
//根据中序和前序，创建二叉树
node* createByPreAndIn(int preL, int preR, int inL, int inR){
if(preL > preR) return NULL;
node* root = new node;
root->data = pre[preL];
int k;
for(k = inL; k <= inR; k++){
if(in[k] == pre[preL]){
break;
}
}
int numLeft = k - inL; //左子树的结点个数
root->lchild = createByPreAndIn(preL + 1, preL + numLeft, inL, k - 1);
root->rchild = createByPreAndIn(preL + numLeft + 1, preR, k + 1, inR);
return root;
}
//根据中序和层序创建二叉树
node* createByLayerAndIn(vector<int> layer, vector<int> in, int inL, int inR){
if(inL > inR || layer.size() == 0) return NULL;
node* root = new node;
root->data = layer[0];
int pos;
for(pos = inL; pos <= inR; pos++){
if(in[pos] == layer[0]){
break;
}
}
vector<int> layerLeft, layerRight; //存放左、右子树的层序序列
for(int i = 1; i < layer.size(); i++){
int j;
for(j = inL; j < pos; j++){
if(in[j] == layer[i]){
layerLeft.push_back(layer[i]); //如果在pos前找到，插入左子树
break;
}
}
//超过pos，j==pos时即为在左子树中没有找到插入右子树（层序遍历保持左右子树层序遍历顺序的一致性）
if(j == pos) layerRight.push_back(layer[i]);
}
root->lchild = createByLayerAndIn(layerLeft, in, inL, pos - 1);
root->rchild = createByLayerAndIn(layerRight, in, pos + 1, inR);
return root;
}
int num = 0;
void BFS(node* root){ //层次遍历
queue<node*> q;
q.push(root);
while(!q.empty()){
node* now = q.front();
q.pop();
printf("%d",now->data);
num++;
if(num < n){
printf(" ");
}
if(now->lchild != NULL) q.push(now->lchild);
if(now->rchild != NULL) q.push(now->rchild);
}
}
void preOrder(node* root){ //先序遍历
if(root == NULL){
return;
}
printf("%d",root->data);
num++;
if(num < n){
printf(" ");
}
preOrder(root->lchild);
preOrder(root->rchild);
}
void inOrder(node* root){ //中序遍历
if(root == NULL){
return;
}
inOrder(root->lchild);
printf("%d",root->data);
num++;
if(num < n){
printf(" ");
}
inOrder(root->rchild);
}
void postOrder(node* root){ //后序遍历
if(root == NULL){
return;
}
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d",root->data);
num++;
if(num < n){
printf(" ");
}
}
int main(){
scanf("%d",&n);
int temp;
for(int i = 0; i < n; i++){
scanf("%d",&temp);
in.push_back(temp);
}
/*测试数据：中后
7
1 2 3 4 5 6 7
2 3 1 5 7 6 4
*/
for(int i = 0; i < n; i++){
scanf("%d",&temp);
post.push_back(temp);
}
node* root = createByPostAndIn(0, n -1, 0, n -1);
/*测试数据：中前
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
*/
// for(int i = 0; i < n; i++){
// scanf("%d",&temp);
// pre.push_back(temp);
// }
// node* root = createByPreAndIn(0, n -1, 0, n -1);
/*测试数据：中层
7
1 2 3 4 5 6 7
4 1 6 3 5 7 2
*/
// for(int i = 0; i < n; i++){
// scanf("%d",&temp);
// layer.push_back(temp);
// }
// node* root = createByLayerAndIn(layer, in, 0, n -1);
BFS(root);
return 0;
}
网友评论