设计思路：
char* post为后序遍历的顺序
char* in为中序遍历的顺序
首先建立一个指针p，用循环在in中找到根节点
left为左子树个数=p-in（指针差值）
right为右子树个数（n-left-1）
之后递归调用该函数构建左右子树
注意：要想构建二叉树，必须知道中序遍历，这样才可以知道根节点，进而确定左右子树
有前序和后序不能够构建二叉树
代码：
/** *作者：魏宝航 *2020年11月27日,下午21:58 */ #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; } }; static int i = 0; //#号法创建二叉树 Node* CreateTree(vector<char> arr,Node* root) { if (i < arr.size()) { char temp = arr[i++]; if (temp == '#') { return NULL; } else { root = new Node(); root->ch = temp; root->left = CreateTree(arr, root->left); root->right = CreateTree(arr, root->right); } } return root; } //二叉树的前序遍历 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 << " "; } //计算二叉树的高度 int treeDepth(Node* root) { int left = 0, right = 0; if (root == NULL) { return 0; } else { left = treeDepth(root->left) + 1; right = treeDepth(root->right) + 1; return max(left, right); } } Node* buildTree1(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; } Node* buildTree2(char* post, char* in, int n) { if (n == 0) { return NULL; } Node* root = new Node(); root->ch = *(post + n-1); char* p; for (p = in; p < in + n; p++) { if (*p == *(post + n - 1)) { break; } } int left = p - in; int right = n - left - 1; root->left = buildTree2(post,in, left); root->right = buildTree2(post + left , p + 1, right); return root; } int main() { char pre[] = { 'A','B','D','E','C','F' }; char mid[] = { 'D','B','E','A','C','F' }; char post[]= { 'D','E','B','F','C','A' }; Node* root = new Node(); root = buildTree2(post, mid, 6); cout << "前序遍历："; preOrder(root); cout << endl; cout << "中序遍历："; midOrder(root); cout << endl; cout << "后序遍历："; postOrder(root); cout << endl; }
