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

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

#include <iostream>
using namespace std;

// 定义节点结构
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// 插入节点到二叉搜索树
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return new TreeNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

// 先序遍历树并输出结果
void preorder(TreeNode* root) {
    if (root != NULL) {
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

int main() {
    TreeNode* root = NULL;
    int num;

    // 读入数据并插入到树中，直到遇到0
    while (cin >> num && num != 0) {
        root = insert(root, num);
    }

    // 输出先序遍历结果
    preorder(root);
    cout << endl;

    return 0;
}

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

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

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

跳转到最佳答案楼层

FishC

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

#include <iostream>
using namespace std;

// 定义节点结构
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// 插入节点到二叉搜索树
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return new TreeNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

// 先序遍历树并输出结果
void preorder(TreeNode* root) {
    if (root != NULL) {
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

int main() {
    TreeNode* root = NULL;
    int num;

    // 读入数据并插入到树中，直到遇到0
    while (cin >> num && num != 0) {
        root = insert(root, num);
    }

    // 输出先序遍历结果
    preorder(root);
    cout << endl;

    return 0;
}

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

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

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