pta二叉树遍历

### PTA平台上二叉树遍历的实现 #### 已知条件分析 给定一棵二叉树的前序遍历 `CABEFDHG` 和中序遍历 `BAFECHDG`，可以通过构建二叉树来推导其后序遍历。以下是具体的实现方法。 --- #### 构建二叉树并计算后序遍历 通过前序和中序遍历来重建二叉树的核心思想在于利用前序的第一个节点作为根节点，在中序中找到该根节点的位置，从而划分左子树和右子树[^1]。具体过程如下： 1. **确定根节点** 前序遍历中的第一个节点即为当前子树的根节点。对于本例，根节点为 `C`。 2. **分割左右子树** 在中序遍历中定位根节点位置（此处为第 3 位），左侧部分为左子树，右侧部分为右子树。因此： - 左子树中序：`BAFEC` - 右子树中序：`HDG` 3. **递归处理左右子树** 对于每棵子树重复上述操作，直到完成整棵树的构造。 4. **后序遍历顺序** 后序遍历遵循“左->右->根”的访问顺序。最终得到的结果为 `BEAFHGD`。 --- #### C++代码实现 以下是一个完整的程序用于根据前序和中序遍历生成后序遍历结果： ```cpp #include <iostream> #include <vector> using namespace std; struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char v):val(v),left(nullptr),right(nullptr){} }; // 根据前序和中序建立二叉树 TreeNode* buildTree(const vector<char>& preorder, const vector<char>& inorder, 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 index = inStart; while(inorder[index] != rootVal && index <= inEnd){ ++index; } // 计算左子树长度 int leftSize = index - inStart; // 递归构建左右子树 root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, index - 1); root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, index + 1, inEnd); return root; } void postOrder(TreeNode* node, vector<char> &result) { if(node == nullptr) return; postOrder(node->left, result); postOrder(node->right, result); result.push_back(node->val); } int main(){ string preStr = "CABEFDHG"; string inStr = "BAFECHDG"; vector<char> preorder(preStr.begin(), preStr.end()); vector<char> inorder(inStr.begin(), inStr.end()); TreeNode *root = buildTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1); vector<char> postResult; postOrder(root, postResult); for(auto ch : postResult){ cout << ch; } return 0; } ``` 此代码实现了基于前序和中序遍历创建二叉树，并输出后序遍历结果[^4]。 --- #### 层次遍历实现 层次遍历通常借助队列实现，按照从上至下、从左至右的方式逐层访问节点。下面展示如何扩展前述代码以支持层次遍历功能： ```cpp void levelOrder(TreeNode* node, vector<char> &result){ if(!node) return; queue<TreeNode*> q; q.push(node); while (!q.empty()){ TreeNode* current = q.front(); q.pop(); result.push_back(current->val); if(current->left) q.push(current->left); if(current->right) q.push(current->right); } } int main(){ // ... （省略前面相同的部分） vector<char> levelResult; levelOrder(root, levelResult); cout << "\nLevel Order Traversal: "; for(auto ch : levelResult){ cout << ch; } return 0; } ``` 以上代码片段展示了如何使用广度优先搜索算法执行层次遍历[^2]。 --- ###