以二叉树的链式存储为基础,创建二叉树,并分别用先序、中序和后序的方式遍历二叉树,输出每个结点的值。
时间: 2024-05-04 14:18:00 浏览: 87
对所建立的二叉树分别进行先序、中序和后序遍历,并输出结果。
4星 · 用户满意度95%
好的,以下是基于链式存储的二叉树的创建和遍历代码(使用 C++ 实现):
```cpp
#include <iostream>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 创建二叉树
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1) { // -1 表示空结点
return NULL;
} else {
TreeNode* root = new TreeNode(val);
root->left = createTree(); // 递归创建左子树
root->right = createTree(); // 递归创建右子树
return root;
}
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " "; // 输出结点的值
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left); // 递归遍历左子树
cout << root->val << " "; // 输出结点的值
inOrder(root->right); // 递归遍历右子树
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
cout << root->val << " "; // 输出结点的值
}
int main() {
cout << "请输入二叉树的结点值,空结点用 -1 表示:" << endl;
TreeNode* root = createTree(); // 创建二叉树
cout << "先序遍历结果:" << endl;
preOrder(root); // 先序遍历
cout << endl;
cout << "中序遍历结果:" << endl;
inOrder(root); // 中序遍历
cout << endl;
cout << "后序遍历结果:" << endl;
postOrder(root); // 后序遍历
cout << endl;
return 0;
}
```
运行程序后,根据提示输入二叉树的结点值,空结点用 -1 表示。然后程序将自动创建该二叉树,并分别用先序、中序和后序的方式遍历二叉树,输出每个结点的值。
阅读全文