用C++建立一个二叉树对象b,数据域为整型,按照前序遍历顺序从键盘输入各结点值(-1为结束符值,即子树为空的话输入﹣1),并输出二叉树的前序中序和后序遍历序列。
时间: 2024-10-28 14:10:43 浏览: 32
在C++中,我们可以使用结构体定义二叉树节点,并结合递归算法来实现前序、中序和后序遍历。首先,我们创建一个简单的二叉树节点:
```cpp
struct TreeNode {
int val; // 节点的整数值
TreeNode* left; // 左子树指针
TreeNode* right; // 右子树指针
};
```
然后,你可以按照以下步骤构造二叉树:
1. 定义一个函数`buildTree()`用于读取输入,构建二叉树:
```cpp
TreeNode* buildTree() {
TreeNode* root = nullptr;
int input;
do {
cin >> input;
if (input != -1) {
TreeNode* newNode = new TreeNode{input, nullptr, nullptr};
if (!root) {
root = newNode;
} else {
insertNode(root, newNode);
}
}
} while (input != -1);
return root;
}
// 插入新节点到已有的二叉树(这里假设insertNode是一个辅助函数,根据输入插入正确的子节点)
void insertNode(TreeNode*& node, TreeNode* newNode) {
if (newNode->val < node->val) {
if (!node->left) {
node->left = newNode;
} else {
insertNode(node->left, newNode);
}
} else {
if (!node->right) {
node->right = newNode;
} else {
insertNode(node->right, newNode);
}
}
}
```
2. 实现前序、中序和后序遍历的递归函数:
```cpp
void preOrder(TreeNode* node) {
if (node) {
cout << node->val << " ";
preOrder(node->left);
preOrder(node->right);
}
}
void inOrder(TreeNode* node) {
if (node) {
inOrder(node->left);
cout << node->val << " ";
inOrder(node->right);
}
}
void postOrder(TreeNode* node) {
if (node) {
postOrder(node->left);
postOrder(node->right);
cout << node->val << " ";
}
}
```
最后,在主函数里调用这些函数:
```cpp
int main() {
TreeNode* b = buildTree();
cout << "Preorder traversal: ";
preOrder(b);
cout << "\nInorder traversal: ";
inOrder(b);
cout << "\nPostorder traversal: ";
postOrder(b);
// 清理内存
delete b;
return 0;
}
```
阅读全文