题目
输入某二叉树的前序遍历和中序遍历，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含有重复的数字。
例如，前序遍历序列：｛1，2，3，7，3，5，6，8｝，中序遍历序列：｛4，7，2，1，5，3，8，6｝
答案
前序遍历：
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
中序遍历：
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。
#include <iostream> using namespace std; struct binary_tree_node{ int value; binary_tree_node* left; binary_tree_node* right; }; binary_tree_node* binary_tree_constuct(int* preorder, int* inorder, int length); int main() { int pre[8] = {1,2,4,7,3,5,6,8}; int in[8] = {4,7,2,1,5,3,8,6}; binary_tree_node* root = binary_tree_constuct(pre, in, 8); } binary_tree_node* construct_method(int* preorder, int* endpreorder, int* inorder, int* endinorder) { int root_value = preorder[0]; binary_tree_node* root = new binary_tree_node(); root->left = NULL; root->right = NULL; cout<<root_value<<" "; if(preorder == endpreorder && inorder == endinorder) return root; int* rootIndex = preorder; rootIndex++; while(*rootIndex != root_value && rootIndex < endpreorder) rootIndex++; int left_len = rootIndex - preorder; int* left_preorder_end = preorder + left_len; //left if(left_len > 0) { root->left = construct_method(preorder+1, left_preorder_end, inorder, rootIndex-1); } //right if(left_len < endpreorder - preorder) { root->right = construct_method(left_preorder_end+1, endpreorder, rootIndex+1, endinorder); } return root; } binary_tree_node* binary_tree_constuct(int* preorder, int* inorder, int length) { if(preorder == NULL || inorder == NULL || length <= 0) { return NULL; } return construct_method(preorder, preorder+length-1, inorder,inorder+length-1); }
本文 由 cococo点点 创作，采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载，请注明出处：
转载自：cococo点点 http://www.cnblogs.com/coder2012
