建立二叉树实现:先序遍历,中序遍历,后序遍历的结果. 输入说明:第一行节点数为n,以下行每行三个数,第一个是父亲,后两个依次是左右孩子,0为空。
时间: 2024-10-12 08:13:08 浏览: 30
要实现一个二叉树并支持先序(Preorder)、中序(Inorder)和后序(Postorder)遍历,你需要首先定义二叉树节点的数据结构,然后创建一个树的结构,接着分别实现三种遍历算法。这里我会为你提供基础的二叉树节点和遍历函数的示例。假设我们使用`TreeNode`表示节点:
```cpp
#include <iostream>
// 定义二叉树节点
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
std::cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->val << " ";
}
```
现在你可以按照以下步骤操作:
1. 首先读取输入的节点数 `n` 和父节点及其孩子的关系。
2. 创建一个空的树,根据输入的父子关系构建二叉树。
3. 当你有所有节点时,调用对应的遍历函数打印结果。
例如,如果输入如下的树结构:
```
5
3 7
2 4 6
```
这意味着根节点是5,其左子树是3,右子树是7,而3的左子树是2,右子树是4和6。你可以用这些信息创建树并执行遍历。
阅读全文