[已解决]构造二叉检索树

yangzhixiaohuli

本题目构造一棵二叉检索树。要求读入n个整数，以0结束。最后输出这棵树的先序序列。

输入格式:
输入n个整数，以0表示结束，数据间以空格隔开。

输出格式:
输出这棵树的先序序列，以一个空格隔开，结尾也有一个空格。

输入样例:
34 50 23 12 30 23 0
输出样例:
34 23 12 23 30 50

这题用C语言或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-12-15 14:01:00

在C或C++中构造二叉检索树（又称为二叉搜索树）的过程涉及创建节点结构、插入节点以及遍历树。下面是一个简单的解决方案，完成了这些要求，并实现了先序遍历输出。

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. // 定义节点结构
   
5. struct TreeNode {
   
6.     int data;
   
7.     TreeNode* left;
   
8.     TreeNode* right;
   
9.     TreeNode(int val) : data(val), left(NULL), right(NULL) {}
   
10. };
    
11. 
    
12. // 插入节点到二叉搜索树
    
13. TreeNode* insert(TreeNode* root, int data) {
    
14.     if (root == NULL) {
    
15.         return new TreeNode(data);
    
16.     }
    
17.     if (data < root->data) {
    
18.         root->left = insert(root->left, data);
    
19.     } else {
    
20.         root->right = insert(root->right, data);
    
21.     }
    
22.     return root;
    
23. }
    
24. 
    
25. // 先序遍历树并输出结果
    
26. void preorder(TreeNode* root) {
    
27.     if (root != NULL) {
    
28.         cout << root->data << " ";
    
29.         preorder(root->left);
    
30.         preorder(root->right);
    
31.     }
    
32. }
    
33. 
    
34. int main() {
    
35.     TreeNode* root = NULL;
    
36.     int num;
    
37. 
    
38.     // 读入数据并插入到树中，直到遇到0
    
39.     while (cin >> num && num != 0) {
    
40.         root = insert(root, num);
    
41.     }
    
42. 
    
43.     // 输出先序遍历结果
    
44.     preorder(root);
    
45.     cout << endl;
    
46. 
    
47.     return 0;
    
48. }

复制代码

以上代码在C++中实现了二叉检索树的构造和先序遍历。在构造过程中：
1. 定义了一个二叉树的节点结构 `TreeNode`。
2. 使用 `insert` 函数去插入节点数据，按照二叉搜索树的规则，左子树的节点值小于根节点值，右子树的节点值大于或等于根节点值。
3. 使用 `preorder` 函数进行先序遍历（根节点 -> 左子树 -> 右子树）并输出节点数据。

输入一系列整数，最后以0结束，程序将输出这些数构成的二叉搜索树的先序遍历序列。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

在C或C++中构造二叉检索树（又称为二叉搜索树）的过程涉及创建节点结构、插入节点以及遍历树。下面是一个简单的解决方案，完成了这些要求，并实现了先序遍历输出。

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. // 定义节点结构
   
5. struct TreeNode {
   
6.     int data;
   
7.     TreeNode* left;
   
8.     TreeNode* right;
   
9.     TreeNode(int val) : data(val), left(NULL), right(NULL) {}
   
10. };
    
11. 
    
12. // 插入节点到二叉搜索树
    
13. TreeNode* insert(TreeNode* root, int data) {
    
14.     if (root == NULL) {
    
15.         return new TreeNode(data);
    
16.     }
    
17.     if (data < root->data) {
    
18.         root->left = insert(root->left, data);
    
19.     } else {
    
20.         root->right = insert(root->right, data);
    
21.     }
    
22.     return root;
    
23. }
    
24. 
    
25. // 先序遍历树并输出结果
    
26. void preorder(TreeNode* root) {
    
27.     if (root != NULL) {
    
28.         cout << root->data << " ";
    
29.         preorder(root->left);
    
30.         preorder(root->right);
    
31.     }
    
32. }
    
33. 
    
34. int main() {
    
35.     TreeNode* root = NULL;
    
36.     int num;
    
37. 
    
38.     // 读入数据并插入到树中，直到遇到0
    
39.     while (cin >> num && num != 0) {
    
40.         root = insert(root, num);
    
41.     }
    
42. 
    
43.     // 输出先序遍历结果
    
44.     preorder(root);
    
45.     cout << endl;
    
46. 
    
47.     return 0;
    
48. }

复制代码

以上代码在C++中实现了二叉检索树的构造和先序遍历。在构造过程中：
1. 定义了一个二叉树的节点结构 `TreeNode`。
2. 使用 `insert` 函数去插入节点数据，按照二叉搜索树的规则，左子树的节点值小于根节点值，右子树的节点值大于或等于根节点值。
3. 使用 `preorder` 函数进行先序遍历（根节点 -> 左子树 -> 右子树）并输出节点数据。

输入一系列整数，最后以0结束，程序将输出这些数构成的二叉搜索树的先序遍历序列。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。