1

我有一个编程课作业，今晚 CDT 晚上 8 点到期，但我遇到了麻烦。我们将通过读取文件来获取以下数字的列表：

9 30 20 40 35 22 48 36 37 38

将它们放在一个数组中（很简单），然后使用 C 将它们读入二叉搜索树。列表中的第一个数字是树中元素的数量。其余的放置在以下结构中：

typedef struct node_struct {
    int data;
    struct node_struct* left;
    struct node_struct* right;
} Node;

我想我已经完成了第一部分。把使用 fscanf 中的东西（我没有选择使用这种方法，我更喜欢 fgets），在数组的每个成员上调用一个插入函数，然后在插入函数内部调用一个“createNode”函数。

问题是，我只让一名成员加入 BST。此外，BST 必须满足条件node->left->data <= node->data < node->right->data……换句话说，节点在树中必须是有序的。

这是我到目前为止所拥有的：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// def BST node struct
typedef struct node_struct {
    int data;
    struct node_struct* left;
    struct node_struct* right;
} Node;

// prototypes
Node* createNode(int data);
Node* bstInsert(Node* root, int data);
// helper function prototypes
void padding(char ch, int n);
void displayTree(Node* root, int depth);

int main(int argc, char **argv)
{
    FILE *in = NULL;
    int num_read, count=0, array_size = 0;

    if(argc != 2){
        printf("hw3 <input-file>\n");
        return 1;
    }

    in = fopen(argv[1], "r");

    if(in == NULL){
        printf("File can not be opened.\n");
        return 2;
    }

    // read in the first line to get the array size
    fscanf(in, "%d", &array_size);

    // declare the array
    int array[array_size];  

    // read from the second line to get each element of the array
    while(!feof(in)){
        fscanf(in, "%d", &num_read);
        array[count] = num_read;
        count++;
    }
    fclose(in);

    if (array_size != count) {
        printf("data error. Make sure the first line specifies the correct number of elements.");
        return 3;
    }

    Node *root1 = NULL, *root2 = NULL, *root3 = NULL;

    int i;
    // task1: construct a bst from the unsorted array
    printf("=== task1: construct a bst from the unsorted array ===\n");
    for (i = 0; i < array_size; i++) {
        root1 = bstInsert(root1, array[i]);
    }
    displayTree(root1, 0);
    return 0;
}   

Node* bstInsert(Node* root, int data) {
    if(root == NULL){
        root = createNode(data);

        if(root != NULL){
            root= createNode(data);
        }

        else{
            printf("%d not inserted, no memory available.\n", data);
        }
    }

    Node* current, previous, right;
    current = root;
    previous = root->left;
    next = root->right;
    else{
        if(previous->data <= current->data){

                }


     }
     return root;
}

Node* createNode(int data) {
    // TODO
    Node* aRoot;
    if(!data)
        return NULL;

    aRoot = malloc(sizeof(Node));
    if(!aRoot){
        printf("Unable to allocate memory for node.\n");
        return NULL;
    }
    aRoot->data = data;
    aRoot->left = NULL;
    aRoot->right = NULL;
    return aRoot;
}

    /* helper functions to print a bst; You just need to call displayTree when visualizing a bst */
void padding(char ch, int n)
{
    int i;
    for (i = 0; i < n; i++)
    printf("%c%c%c%c", ch, ch ,ch, ch);
}

void displayTree(Node* root, int depth){
    if (root == NULL) {
        padding (' ', depth);
        printf("-\n");
    }
    else {
        displayTree(root->right, depth+1);
        padding(' ', depth);
        printf ( "%d\n", root->data);
        displayTree(root->left, depth+1);
    }
}

main, createNode, displayTree, 并且padding没问题，我相信。这bstInsert就是我遇到麻烦的地方。我只是不确定如何订购东西以创建有效的树。

编辑：

我编辑了 bstInsert 并注入了更多逻辑。它应该在树上打印出更多的叶子，但是，它只打印出数字“30”。这是新功能。

Node* bstInsert(Node* root, int data) {


if(root == NULL){
    root = createNode(data);

    if(root != NULL){
        root= createNode(data);
    }

    else{
        printf("%d not inserted, no memory available.\n", data);
    }
}
else{
    if(data < root->data){
        bstInsert(root->left, data);
    }
    else if(data > root->data || data == root->data){
        bstInsert(root->right, data);
    }
        }
return root;
}
4

4 回答 4

1

您必须将新创建的节点指针分配给树的正确部分。这段代码就是这样做的。关键变化是bstInsert()正确使用返回值。其他变化是装饰性的。请注意，我通过打印输出来检查输入数组；此外，在构建 BST 时打印出它是明智的。

不要feof()用作循环控制条件。用作循环控制时几乎总是错误的，但至少您还必须检查随后的输入操作。我写过很多程序。我几乎没用过feof()（我在自己的代码中发现了两个地方；在这两个地方，它都正确地用于区分 EOF 和输入失败后的错误。）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// def BST node struct
typedef struct node_struct
{
    int data;
    struct node_struct* left;
    struct node_struct* right;
} Node;

// prototypes
Node *createNode(int data);
Node *bstInsert(Node *root, int data);
// helper function prototypes
void padding(char ch, int n);
void displayTree(Node *root, int depth);

int main(int argc, char **argv)
{
    FILE *in = NULL;
    int num_read, count=0, array_size = 0;

    if (argc != 2)
    {
        printf("hw3 <input-file>\n");
        return 1;
    }

    in = fopen(argv[1], "r");

    if (in == NULL)
    {
        printf("File can not be opened.\n");
        return 2;
    }

    // read in the first line to get the array size
    fscanf(in, "%d", &array_size);

    // declare the array
    int array[array_size];  

    // read from the second line to get each element of the array
    while (count < array_size && fscanf(in, "%d", &num_read) == 1)
        array[count++] = num_read;
    fclose(in);

    if (array_size != count)
    {
        printf("data error. Make sure the first line specifies the correct number of elements.");
        return 3;
    }

    for (int i = 0; i < array_size; i++)
        printf("%d: %d\n", i, array[i]);

    Node *root1 = NULL;

    // task1: construct a bst from the unsorted array
    printf("=== task1: construct a bst from the unsorted array ===\n");

    for (int i = 0; i < array_size; i++)
    {
        root1 = bstInsert(root1, array[i]);
        displayTree(root1, 0);
    }

    displayTree(root1, 0);
    return 0;
}   

Node *bstInsert(Node *root, int data)
{
    if (root == NULL)
    {
        root = createNode(data);
        if (root == NULL)
            printf("%d not inserted, no memory available.\n", data);
    }
    else if (data < root->data)
        root->left = bstInsert(root->left, data);
    else
        root->right = bstInsert(root->right, data);
    return root;
}

Node *createNode(int data)
{
    Node *aRoot;

    aRoot = malloc(sizeof(Node));
    if (!aRoot)
    {
        printf("Unable to allocate memory for node.\n");
        return NULL;
    }
    aRoot->data = data;
    aRoot->left = NULL;
    aRoot->right = NULL;
    return aRoot;
}

/* helper functions to print a bst; You just need to call displayTree when visualizing a bst */
void padding(char ch, int n)
{
    for (int i = 0; i < n; i++)
        printf("%c%c%c%c", ch, ch, ch, ch);
}

void displayTree(Node *root, int depth)
{
    if (root == NULL) {
        padding (' ', depth);
        printf("-\n");
    }
    else {
        displayTree(root->right, depth+1);
        padding(' ', depth);
        printf ( "%d\n", root->data);
        displayTree(root->left, depth+1);
    }
}
于 2012-10-28T21:41:21.830 回答
0

好的，想想你想在不同的树配置中做什么：

  • 当树为空时 -> 创建一个根节点
  • 当树不为空时->要插入的值与根的值如何比较？
    • 上面 -> 插入右子树
    • 下面 -> 在左子树中插入
    • 相等 -> 什么都不做（这实际上取决于您的作业告诉您如何处理重复项）

从这个基本算法中，您应该能够找出所有极端情况。

于 2012-10-28T21:27:47.470 回答
0

一个简化的解决方案（带有递归的简单插入，删除了数据输入噪声）：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static int nums[] = { 6, 8, 4, 1, 3, 7, 14, 10, 13 }; // instead of the user input

typedef struct _node {
    int value;
    struct _node *left;
    struct _node *right;
} node;

node *node_new(int v)
{
    node *n = malloc(sizeof(*n));
    assert(n);

    n->value = v;
    n->left = NULL;
    n->right = NULL;

    return n;
}

void insert(node **tree, node *leaf)
{
    if (*tree == NULL) {
        *tree = leaf;
    } else if (leaf->value > (*tree)->value) {
        insert(&((*tree)->right), leaf);
    } else {
        insert(&((*tree)->left), leaf);
    }
}

void dump(node *tree, int level)
{
    static const char *pad = "\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t";

    if (tree != NULL) {
        printf("%sSelf: %d\n", pad + 16 - level, tree->value);
        if (tree->left) {
            printf("%sLeft node:\n", pad + 16 - level);
            dump(tree->left, level + 1);
        }
        if (tree->right) {
            printf("%sRight node:\n", pad + 16 - level);
            dump(tree->right, level + 1);
        }
    } else {
        printf("%sEmpty\n", pad + 16 - level);
    }
}

int main()
{
    size_t n = sizeof(nums) / sizeof(*nums);
    int i;
    node *tree = NULL;
    for (i = 0; i < n; i++) {
        insert(&tree, node_new(nums[i]));
    }

    dump(tree, 0);

    // give some work to the kernel
    return 0;
}
于 2012-10-28T21:49:02.330 回答
0

您应该考虑递归执行此操作。请记住，每个节点本身就是一棵树：

#include <stdio.h>
#include <stdlib.h>

typedef struct tree_struct {
    int value;
    struct tree_struct* left;
    struct tree_struct* right;
} Tree;

Tree* addToTree(int value, Tree* tree)
{
    if (tree == NULL) {
        tree = malloc(sizeof(Tree));
        tree->value = value;
        tree->left = NULL;
        tree->right = NULL;
    } else {
        if (value < tree->value) {
            tree->left = addToTree(value, tree->left);
        } else {
            tree->right = addToTree(value, tree->right);
        }
    }
    return tree;
}

int main(int argc, char** argv)
{
    Tree* tree = NULL;
    int in;
    while (scanf("%d", &in) != EOF) {
        tree = addToTree(in, tree);
    }

    return 0;
}
于 2012-10-28T22:15:08.703 回答