设计思路：
char* pre为前序遍历的顺序
char* in为中序遍历的顺序
首先建立一个指针p，用循环在in中找到根节点
left为左子树个数=p-in（指针差值）
right为右子树个数（n-left-1）
之后递归调用该函数构建左右子树
代码：
/** *作者：魏宝航 *2020年11月27日,下午15:50 */ #include<iostream> using namespace std; class Node { public: char ch; Node* left; Node* right; Node() { ch = '\0'; left = NULL; right = NULL; } Node(char ch, Node* left, Node* right) { this->ch = ch; this->left = left; this->right = right; } }; //二叉树的前序遍历 void preOrder(Node* root) { if (root == NULL) { return; } cout << root->ch << " "; preOrder(root->left); preOrder(root->right); } //二叉树的中序遍历 void midOrder(Node* root) { if (root == NULL) { return; } midOrder(root->left); cout << root->ch << " "; midOrder(root->right); } //二叉树的后序遍历 void postOrder(Node* root) { if (root == NULL) { return; } postOrder(root->left); postOrder(root->right); cout << root->ch << " "; } //由前序遍历和中序遍历构建二叉树 Node* buildTree(char* pre, char* in, int n) { if (n == 0) { return NULL; } Node* root = new Node(); root->ch = *pre; char* p; //在中序中找到根节点 for (p = in; p < in + n; p++) { if (*p == *pre) { break; } } int left = p - in;//左子树个数 int right = n - left - 1;//右子树个数 //递归构建左子树 root->left = buildTree1(pre + 1, in, left); //递归构建右子树 root->right = buildTree1(pre + left + 1, p + 1, right); return root; } int main() { char a[] = { 'A','B','D','E','C','F' }; char b[] = { 'D','B','E','A','C','F' }; Node* root = new Node(); root = buildTree(a, b, 6); preOrder(root); midOrder(root); }
