首页 > 代码库 > 二叉树前序中序遍历求后序遍历
二叉树前序中序遍历求后序遍历
已知先序和中序遍历序列，求后序遍历序列。
已知该二叉树的先序遍历序列为：A-B-D-E-G-C-F，中序遍历序列为：D-B-G-E-A-C-F。
接下来我们就可以求出该二叉树的后序遍历序列，具体步骤如下：
第一步：先求root根节点，根据先序遍历规则我们可知root为先序遍历序列的第一个节点，因此该二叉树的root节点为A。
第二步：求root的左子树和右子树，这点我们可以从中序遍历序列中找出，位于root节点A左侧的D-B-G-E为root的左子树，位于A右侧的C-F为右子树。
第三步：求root的左孩子leftchild和右孩子rightchild，leftchild为左子树的根节点，rightchild为右子树的根节点。我们可以找到左子树D-B-E-G在先序遍历序列中的排列顺序为B-D-E-G，由于先序遍历首先访问根节点，所以B为左子树的根节点，即B为root的leftchild；同理root的rightchild为C。
第四步：我们可以根据上面的步骤找到B的左子树和右子树，以及C的左子树和右子树，然后分别求出左右子树的根节点。以此类推，只要求出根节点及其leftchild和rightchild，剩下的过程都是递归的，最后我们就可以还原整个二叉树。
文字转自邵鸿鑫二叉树系列
#include <iostream>#include <cstdio>#include <queue>#include <cstring>using namespace std;const int MAXN = 100;struct Node { int value; Node *left_child; Node *right_child; Node () { left_child = right_child = NULL; }};bool first = true;void Pos_order(Node *tree) { if(tree->left_child != NULL) { Pos_order(tree->left_child); } if(tree->right_child != NULL) { Pos_order(tree->right_child); } if(first) { cout << tree->value; first = false; } else cout << " " << tree->value;}Node* build(int pre[], int in[], int n) { if(n == 0) return NULL; Node *tmp = new Node; for(int i = 0; i < n; i++) { if(in[i] == pre[0]) { tmp->value = http://www.mamicode.com/pre[0]; tmp->left_child = build(pre+1, in, i); tmp->right_child = build(pre+i+1, in+i+1, n-i-1); return tmp; } } return NULL;}int main() { int n, pre[MAXN], in[MAXN]; scanf("%d", &n); first = false; for(int i = 0; i < n; i++) scanf("%d", &in[i]); for(int i = 0; i < n; i++) scanf("%d", &pre[i]); Node *tree = build(pre, in, n); Pos_order(tree); return 0;}
二叉树前序中序遍历求后序遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。