分别建立二叉树存储结构的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数。
时间: 2023-12-20 09:04:12 浏览: 72
好的,以下是分别建立二叉树存储结构的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数的完整代码实现:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结点的结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 输入二叉树函数
void input(TreeNode* &root) {
int val;
cin >> val;
if (val == -1) { // 如果输入 -1,表示当前结点为空
root = NULL;
} else {
root = new TreeNode(val); // 新建结点
input(root->left); // 递归输入左子树
input(root->right); // 递归输入右子树
}
}
// 层序遍历函数
void levelorder(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q; // 定义队列
q.push(root); // 根节点入队
while (!q.empty()) {
TreeNode* node = q.front(); // 取出队首元素
q.pop(); // 队首元素出队
cout << node->val << " "; // 输出队首元素的值
if (node->left != NULL) q.push(node->left); // 左子结点入队
if (node->right != NULL) q.push(node->right); // 右子结点入队
}
}
// 先序遍历函数
void preorder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
int main() {
TreeNode* root;
cout << "请输入二叉树结点的值,以 -1 结束:" << endl;
input(root);
cout << "层序遍历结果为:" << endl;
levelorder(root);
cout << endl << "先序遍历结果为:" << endl;
preorder(root);
return 0;
}
```
在程序运行时,我们可以依次输入二叉树的结点值,以 `-1` 结束。程序将会分别输出层序遍历和先序遍历的结果。
例如,我们输入了一棵如下图所示的二叉树:
```
1
/ \
2 3
/ / \
4 6 7
/ \
8 9
```
程序将会输出以下结果:
```
请输入二叉树结点的值,以 -1 结束:
1 2 4 -1 -1 -1 3 6 8 -1 -1 9 -1 -1 7 -1 -1
层序遍历结果为:
1 2 3 4 6 7 8 9
先序遍历结果为:
1 2 4 3 6 8 9 7
```
阅读全文