构造下图二叉树,并实现前中后序遍历写出 c++代码
时间: 2024-12-11 17:27:58 浏览: 24
为了构造一个二叉树并实现前序、中序和后续遍历,我们可以创建一个简单的二叉树结构,然后定义递归函数分别处理这三种遍历方法。这里是一个基本的例子:
首先,我们定义一个二叉树节点(TreeNode):
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
接下来,我们将实现前序遍历(根-左-右),中序遍历(左-根-右),以及后续遍历(左-右-根):
```cpp
void preOrder(TreeNode* root) {
if (root != nullptr) {
std::cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(TreeNode* root) {
if (root != nullptr) {
inOrder(root->left);
std::cout << root->val << " ";
inOrder(root->right);
}
}
void postOrder(TreeNode* root) {
if (root != nullptr) {
postOrder(root->left);
postOrder(root->right);
std::cout << root->val << " ";
}
}
```
最后,你可以根据需要构建一个具体的二叉树实例,并调用这些函数进行遍历。例如,构造一个简单二叉树:
```cpp
// 示例:构造一个二叉树
TreeNode* buildTree() {
// 这里可以添加具体代码来构造你的二叉树结构
// ... (假设有一个数组存储了节点值)
return new TreeNode(1); // 使用一个根节点开始
}
int main() {
TreeNode* root = buildTree();
std::cout << "Preorder traversal: ";
preOrder(root);
std::cout << "\nInorder traversal: ";
inOrder(root);
std::cout << "\nPostorder traversal: ";
postOrder(root);
delete root; // 别忘了释放内存
return 0;
}
```
阅读全文