要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列,分别建立二叉树存储结构的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数。
时间: 2024-02-20 10:59:48 浏览: 92
好的,以下是基于二叉链表存储结构的输入函数、输出层序遍历序列的函数和输出先序遍历序列的函数的示例代码(使用C++语言实现):
```c++
#include <iostream>
#include <queue>
using namespace std;
// 定义二叉树结点结构体
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 输入函数
void input(TreeNode*& root) {
char ch;
cin >> ch;
if (ch == '#') {
root = NULL;
} else {
root = new TreeNode(ch);
input(root->left);
input(root->right);
}
}
// 层序遍历函数
void levelorder(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left != NULL) {
q.push(cur->left);
}
if (cur->right != NULL) {
q.push(cur->right);
}
}
}
// 先序遍历函数
void preorder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
int main() {
TreeNode* root;
input(root);
cout << "层序遍历序列:";
levelorder(root);
cout << endl;
cout << "先序遍历序列:";
preorder(root);
cout << endl;
return 0;
}
```
其中,输入函数使用递归实现,每次读入一个字符,如果是`#`则表示该结点为空,否则创建一个新的结点,递归构建左右子树。
输出层序遍历序列的函数使用队列实现,将根结点入队,然后依次出队、输出并将左右子结点入队,直到队列为空。
输出先序遍历序列的函数使用递归实现,先输出当前结点的值,然后依次递归遍历左右子树。
阅读全文