0

所以这个用于创建搜索和删除节点到 BST 的代码效果很好，但只有当它的大小为 9 时，当我将 SIZE 更改为 20 时，我如何使其大小为 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 TREE\n");
        for (b =0; b < SIZE; b++)
        {
        printf("#%2d > ", b+1);
        scanf("%d", &a[b]);
        }

    printf("--- C Binary Search Tree ---- \n\n");
    printf("Insert: ");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ",a[i]);
        root = insert_node(root,int_comp,a[i]);
    }
    printf(" into the tree.\n\n");

    /* 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 found\n",key);
        }
    }

    /* remove the whole tree */
    dispose(root);
    return 0;
}

谢谢你的帮助！

4

2 回答 2

0

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

于 2013-04-27T08:47:26.340 回答
0

无需将输入存储在数组中。在您从用户那里读取输入的代码部分，只需将数字插入到数组中。我对 C 不太熟悉，但可以执行以下操作：

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

在您的情况下它可以正常工作，但是如果您将大小更改为 20，它会非常缓慢，这就是您认为它不起作用的原因。以这种方式执行此操作将加快代码速度。

于 2013-04-28T03:08:00.917 回答