前序序列：A,B,H,F,D,E,C,K,G 中序序列：H,B,D,F,A,E,K,C,G求二叉树结构

### 已知前序和中序序列构造二叉树的 C++ 实现 以下是一个完整的 C++ 程序，用于根据给定的前序序列和中序序列构建二叉树。程序的核心逻辑是从前序序列的第一个元素确定根节点，在中序序列中定位该根节点的位置，从而划分出左子树和右子树的范围，并递归地完成整棵树的构建。 ```cpp #include <iostream> #include <unordered_map> #include <string> using namespace std; // 定义二叉树节点结构 struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} }; // 构建函数声明 TreeNode* buildTreeHelper(const string& preorder, const string& inorder, unordered_map<char, int>& indexMap, int preStart, int preEnd, int inStart, int inEnd); // 主函数入口 TreeNode* buildTree(const string& preorder, const string& inorder) { if (preorder.empty() || inorder.empty()) return nullptr; // 建立哈希表加速查找中序遍历中的索引位置 unordered_map<char, int> indexMap; for (int i = 0; i < inorder.size(); ++i) { indexMap[inorder[i]] = i; } return buildTreeHelper(preorder, inorder, indexMap, 0, preorder.size() - 1, 0, inorder.size() - 1); } // 辅助递归函数 TreeNode* buildTreeHelper(const string& preorder, const string& inorder, unordered_map<char, int>& indexMap, int preStart, int preEnd, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) return nullptr; // 当前子树的根节点值从前序序列获取 char rootVal = preorder[preStart]; TreeNode* root = new TreeNode(rootVal); // 获取根节点在中序序列中的索引 int rootIndexInOrder = indexMap[rootVal]; // 计算左子树长度 int leftSize = rootIndexInOrder - inStart; // 递归构建左子树和右子树 root->left = buildTreeHelper(preorder, inorder, indexMap, preStart + 1, preStart + leftSize, inStart, rootIndexInOrder - 1); root->right = buildTreeHelper(preorder, inorder, indexMap, preStart + leftSize + 1, preEnd, rootIndexInOrder + 1, inEnd); return root; } // 层次遍历打印二叉树（辅助调试） void levelOrderTraversal(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); cout << node->val << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } cout << endl; } int main() { // 输入前序和中序序列 string preorder = "ABHFDECKG"; string inorder = "HBDFAEKC"; // 构造二叉树 TreeNode* root = buildTree(preorder, inorder); // 打印层次遍历结果 cout << "Level Order Traversal of Constructed Tree:" << endl; levelOrderTraversal(root); return 0; } ``` --- #### 关键点说明 - **输入数据**： 给定前序序列 `"A,B,H,F,D,E,C,K,G"` 和中序序列 `"H,B,D,F,A,E,K,C,G"`，通过这些信息可以唯一确定一棵二叉树[^2]。 - **核心逻辑**： 1. 使用前序序列的第一个字符作为当前子树的根节点。 2. 在中序序列中找到该根节点的位置，以此划分为左子树和右子树的部分。 3. 对于每一部分分别递归调用相同的逻辑，直到处理完所有的节点[^3]。 - **性能优化**： 使用 `unordered_map` 存储中序序列中每个字符对应的索引，以便快速查找到某个节点在中序序列中的位置，减少时间复杂度[^1]。 - **输出验证**： 提供了一个简单的层序遍历函数 `levelOrderTraversal` 来验证生成的二叉树是否正确。 ---