C++实现根据输入构建二叉树并进行先序、中序和后序遍历

以下是实现该功能的C++代码： ```cpp #include <iostream> #include <vector> using namespace std; // 定义二叉树节点结构体 struct TreeNode { char val; TreeNode* left; TreeNode* right; // 构造函数 TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} }; // 构建二叉树 TreeNode* buildTree(int n) { vector<TreeNode*> nodes(n + 1); // 初始化所有节点 for (int i = 1; i <= n; ++i) { nodes[i] = new TreeNode('A' + i - 1); } // 构建树的结构 for (int i = 1; i <= n; ++i) { char l, r; cin >> l >> r; if (l != '0') { nodes[i]->left = nodes[l - 'A' + 1]; } if (r != '0') { nodes[i]->right = nodes[r - 'A' + 1]; } } return nodes[1]; } // 先序遍历 void preOrder(TreeNode* root) { if (root == nullptr) return; cout << root->val; if (root->left or root->right) { cout << " "; } preOrder(root->left); preOrder(root->right); } // 中序遍历 void inOrder(TreeNode* root) { if (root == nullptr) return; inOrder(root->left); cout << root->val; if (root->left or root->right) { cout << " "; } inOrder(root->right); } // 后序遍历 void postOrder(TreeNode* root) { if (root == nullptr) return; postOrder(root->left); postOrder(root->right); cout << root->val; if (root->left or root->right) { cout << " "; } } // 释放二叉树内存 void freeTree(TreeNode* root) { if (root == nullptr) return; freeTree(root->left); freeTree(root->right); delete root; } int main() { int n; cin >> n; TreeNode* root = buildTree(n); // 先序遍历 preOrder(root); cout << endl; // 中序遍历 inOrder(root); cout << endl; // 后序遍历 postOrder(root); cout << endl; // 释放二叉树内存 freeTree(root); return 0; } ``` ### 代码解释 1. **TreeNode结构体**：定义二叉树节点，包含节点的值、左子节点指针和右子节点指针。 2. **buildTree函数**：根据输入构建二叉树。首先创建所有节点，然后根据输入的左右子节点信息连接这些节点。 3. **preOrder函数**：实现先序遍历，先访问根节点，再递归访问左子树和右子树。 4. **inOrder函数**：实现中序遍历，先递归访问左子树，再访问根节点，最后递归访问右子树。 5. **postOrder函数**：实现后序遍历，先递归访问左子树和右子树，最后访问根节点。 6. **freeTree函数**：释放二叉树占用的内存，避免内存泄漏。 7. **main函数**：读取输入，调用`buildTree`构建二叉树，分别调用三种遍历函数输出结果，最后调用`freeTree`释放内存。 ######[AI问答 | 892点数解答 | 2026-02-15 20:58:40]