有20个元素的二叉搜索树

Question

所以这段代码用于创建搜索和删除节点到BST工作得很好，但只有当它的大小为9时，我如何使它的大小为20，当我将size更改为20时，程序不会超过第一个打印语句，它说二叉树，对不起，长代码。

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

#define SIZE 9
typedef struct node
{
    int data;
    struct node* left;
    struct node* right;
} node;
 typedef int (*comparer)(int, int);
typedef void (*callback)(node*);

/*create a new node*/
node* create_node(int data)
{
    node *new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        fprintf (stderr, "Out of memory!!! (create_node)n");
        exit(1);
    }
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}
/*remove all nodes of the tree*/
void dispose(node* root)
{
    if(root != NULL)
    {
        dispose(root->left);
        dispose(root->right);
        free(root);
    }
}
/*search*/
node* search(node *root,const int data,comparer compare)
{
    if(root == NULL)
        return NULL;
    int r;
    node* cursor = root;
    while(cursor != NULL)
    {
        r = compare(data,cursor->data);
        if(r < 0)
            cursor = cursor->left;
        else if(r > 0)
            cursor = cursor->right;
        else
            return cursor;
    }
    return cursor;
}
/*delete a node*/
node* delete_node(node* root, int data,comparer compare)
{
    if(root == NULL)
        return NULL;
    node *cursor;
    int r = compare(data,root->data);
    if( r < 0)
        root->left = delete_node( root->left, data,compare);
    else if( r > 0 )
        root->right = delete_node(root->right,data,compare);
    else
    {
        if (root->left == NULL)
        {
            cursor = root->right;
            free(root);
            root = cursor;
        }
        else if (root->right == NULL)
        {
            cursor = root->left;
            free(root);
            root = cursor;
        }
        else 
        {
            cursor = root->right;
            node *parent = NULL;
            while(cursor->left != NULL)
            {
                parent = cursor;
                cursor = cursor->left;
            }
            root->data = cursor->data;
            if (parent != NULL)
                parent->left = delete_node(parent->left, parent->left->data,compare);
            else
                root->right = delete_node(root->right, root->right->data,compare);
        }
    }
    return root;
}
/*insert a new node*/
node* insert_node(node *root, comparer compare, int data)
{
    if(root == NULL)
    {
        root = create_node(data);
    }
    else
    {
        int is_left  = 0;
        int r        = 0;
        node* cursor = root;
        node* prev   = NULL;
        while(cursor != NULL)
        {
            r = compare(data,cursor->data);
            prev = cursor;
            if(r < 0)
            {
                is_left = 1;
                cursor = cursor->left;
            }
            else if(r > 0)
            {
                is_left = 0;
                cursor = cursor->right;
            }
        }
        if(is_left)
            prev->left = create_node(data);
        else
            prev->right = create_node(data);
    }
    return root;
}
/* compare two integers*/
int compare(int left,int right)
{
    if(left > right)
        return 1;
    if(left < right)
        return -1;
    return 0;
}
/*display a node's key*/
void display(node* nd)
{
    if(nd != NULL)
        printf("%d ",nd->data);
}
/*display tree or subtree*/
void display_tree(node* nd)
{
    if (nd == NULL)
        return;
    /* display node data */
    printf("%d",nd->data);
    if(nd->left != NULL)
        printf("(L:%d)",nd->left->data);
    if(nd->right != NULL)
        printf("(R:%d)",nd->right->data);
    printf("n");
    display_tree(nd->left);
    display_tree(nd->right);
}

int main()
{
    node* root = NULL;
    comparer int_comp = compare;
    callback f = display;
    /* insert data into the tree */
    int a[SIZE];
    int i,b;
/* This takes the input from the user for the tree*/
    printf("nPlease input the 20 numbers you want to summit to the TREEn");
        for (b =0; b < SIZE; b++)
        {
        printf("#%2d > ", b+1);
        scanf("%d", &a[b]);
        }
    printf("--- C Binary Search Tree ---- nn");
    printf("Insert: ");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ",a[i]);
        root = insert_node(root,int_comp,a[i]);
    }
    printf(" into the tree.nn");
    /* display the tree */
    display_tree(root);
    /* remove element */
    int r;
    do
    {
        printf("Enter data to remove, (-1 to exit):");
        scanf("%d",&r);
        if(r == -1)
            break;
        root = delete_node(root,r,int_comp);
        /* display the tree */
        if(root != NULL)
            display_tree(root);
        else
            break;
    }
    while(root != NULL);
    /* search for a node */
    int key = 0;
    node *s;
    while(key != -1)
    {
        printf("Enter data to search (-1 to exit):");
        scanf("%d",&key);
        s = search(root,key,int_comp);
        if(s != NULL)
        {
            printf("Found it %d",s->data);
            if(s->left != NULL)
                printf("(L: %d)",s->left->data);
            if(s->right != NULL)
                printf("(R: %d)",s->right->data);
            printf("n");
        }
        else
        {
            printf("node %d not foundn",key);
        }
    }
    /* remove the whole tree */
    dispose(root);
    return 0;
}

谢谢你的帮助!

Answer 1

不需要将输入存储在数组中。在从用户那里读取输入的代码部分，只需将数字插入到数组中。我不太熟悉C语言，但可以这样做:

int i;  
for (b =0; b < SIZE; b++)
  {
    printf("#%2d > ", b+1);
    scanf("%d", &i);
    root = insert_node(root, int_comp, i); 
  }

在你的例子中它是正常工作的，但是如果你将大小更改为20，它会运行得非常慢，这就是为什么你认为它不起作用。这样做可以加快代码的速度。

Answer 2

我尝试了您的代码，试图将SIZE更改为20，并且在这两种情况下都能正常工作。也许你还改变了什么?此外，正如OGH所说，为什么要先将输入存储在数组中，这会消耗更多的时间并限制输入的最大大小?