目录

1.理论依据&＃xff1a;

具体情况下&＃xff1a;

一般情况下&＃xff1a;

2.代码

1.理论依据&＃xff1a;

具体情况下&＃xff1a;

已知后序遍历&＃xff1a;post1、post2、……、postN&＃xff0c;中序遍历&＃xff1a;in1、in2、……、inN。

由先序遍历的性质可知&＃xff1a;preN是当前二叉树根节点的值&＃xff0c;然后&＃xff0c;在中序遍历中遍历一遍&＃xff0c;找到根节点&＃xff08;记为k&＃xff09;&＃xff0c;k左侧的就是左子树&＃xff0c;k右侧的就是右子树。

左子树的长度&＃xff1a;numleft&＃61;k-1&＃xff1b;

那么&＃xff0c;先序遍历中左子树的范围&＃xff1a;1~1&＃43;numleft-1 &＃xff0c; 右子树的范围&＃xff1a;1&＃43;numleft~N-1

          中序遍历中左子树的范围&＃xff1a; 1~k-1 &＃xff0c;右子树的范围&＃xff1a;k&＃43;1~N

一般情况下&＃xff1a;

已知后序遍历&＃xff1a;postL、……、postR&＃xff0c;中序遍历&＃xff1a;inL、in2、……、inR。

由先序遍历的性质可知&＃xff1a;postR是当前二叉树根节点的值&＃xff0c;然后&＃xff0c;在中序遍历中过一遍&＃xff0c;找到根节点&＃xff08;记为k&＃xff09;&＃xff0c;k左侧的就是左子树&＃xff0c;k右侧的就是右子树。

左子树的长度&＃xff1a;numleft&＃61;k-inL&＃xff1b;

那么&＃xff0c;先序遍历中左子树的范围&＃xff1a;postL~postL&＃43;numleft-1 &＃xff0c; 右子树的范围&＃xff1a;postL&＃43;numleft~postR-1

           中序遍历中左子树的范围&＃xff1a; inL~k-1 &＃xff0c;右子树的范围&＃xff1a;k&＃43;1~inR

2.代码
 

node* create(int postL,int postR,int inL,int inR){if(postL>postR){ // 先序序列小于0&＃xff0c;则返回 return NULL;}node* root&＃61;new node;root->data&＃61;post[postR]; // 根节点赋值 int k;for(k&＃61;inL;klchild&＃61;create(postL,postL&＃43;numLeft-1,inL,k-1); //对右子树进行递归 root->rchild&＃61;create(postL&＃43;numLeft,postR-1,k&＃43;1,inR);return root;
}

完整的代码&＃xff1a;

#include
#include
#include
#include
using namespace std;
#define range 100
#define NULL 0
struct node{int data;node* lchild;node* rchild;
};
node* Root&＃61;NULL;
int post[range];
int in[range];
node* create(int postL,int postR,int inL,int inR){if(postL>postR){ // 先序序列小于0&＃xff0c;则返回 return NULL;}node* root&＃61;new node;root->data&＃61;post[postR]; // 根节点赋值 int k;for(k&＃61;inL;klchild&＃61;create(postL,postL&＃43;numLeft-1,inL,k-1); //对右子树进行递归 root->rchild&＃61;create(postL&＃43;numLeft,postR-1,k&＃43;1,inR);return root;
}
void preorder(node* root){ // 先序遍历 if(root&＃61;&＃61;NULL){return ;}printf("%d ",root->data);preorder(root->lchild);preorder(root->rchild);
}
void inorder(node* root){ // 中序遍历 if(root&＃61;&＃61;NULL){return ;}inorder(root->lchild);printf("%d ",root->data);inorder(root->rchild);
}
void postorder(node* root){ // 后序遍历 if(root&＃61;&＃61;NULL){return ;}postorder(root->lchild);postorder(root->rchild);printf("%d ",root->data);
}
void layerorder(node* root){ // 层次遍历 queue s;s.push(root);node* temp&＃61;NULL;while(!s.empty()){temp&＃61;s.front();s.pop();printf("%d ",temp->data);if(temp->lchild!&＃61;NULL) s.push(temp->lchild);if(temp->rchild!&＃61;NULL)s.push(temp->rchild);}
}
//测试数据: 10 9 8 7 4 5 6 3 2 1
int main(){int i,j;cout<<"请输入节点个数:"<>j;cout<<"请输入后序遍历:"<>post[i];cout<<"请输入中序遍历:"<>in[i];Root&＃61;create(0,j-1,0,j-1);cout<}