本题目构造一棵二叉检索树。要求读入n个整数,以0结束。最后输出这棵树的先序序列。
时间: 2023-04-24 18:01:08 浏览: 228
好的,我来回答这个问题。
首先,二叉搜索树是一种特殊的二叉树,它的每个节点都有一个关键字,且满足左子树中所有节点的关键字都小于该节点的关键字,右子树中所有节点的关键字都大于该节点的关键字。这样的树可以快速地进行查找、插入和删除操作。
接下来,我们需要读入n个整数,并构造一棵二叉搜索树。我们可以从根节点开始,依次将每个整数插入到树中。如果该整数比当前节点的关键字小,则将其插入到左子树中;如果该整数比当前节点的关键字大,则将其插入到右子树中。如果当前节点为空,则将该整数作为新的节点插入到树中。
最后,我们需要输出这棵树的先序序列。先序遍历是指先访问根节点,然后依次遍历左子树和右子树。因此,我们可以使用递归的方式来实现先序遍历,并将每个节点的关键字输出到屏幕上。
下面是一个示例代码,供参考:
```
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void insert(TreeNode*& root, int val) {
if (root == NULL) {
root = new TreeNode(val);
} else if (val < root->val) {
insert(root->left, val);
} else {
insert(root->right, val);
}
}
void preorder(TreeNode* root) {
if (root != NULL) {
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
}
int main() {
int n, val;
TreeNode* root = NULL;
cin >> n;
while (n != ) {
cin >> val;
insert(root, val);
n--;
}
preorder(root);
return ;
}
```
希望能对你有所帮助!