c - 实现二叉搜索树

Question

我正在尝试实现一个二叉搜索树来保存订购库存。库存商品属性存储在这样的节点中:

typedef struct item item_t;
struct item{
    char name;
    int price;
    int quantity;
    item_t *left;
    item_t *right;
};

想法是提示用户输入上述属性，然后将输入的项目添加到节点。这是我到目前为止写的:

item_t *root = NULL;
item_t *current_leaf = NULL;

void prompt_user(){
    /*
    In here contains the code that prompts the user for the item attributes
    and stores it in a variable called input
    */
    insert_node(input);
}

void insert_node(char *input){
    /*If tree doesnt have a root...*/
    if (root == NULL){

        /*Create one...*/
        *root = create_node(input);
    }

    else{
        item_t *cursor = root;
        item_t *prev = NULL;
        int is_left = 0;
        int comparison;

        while(cursor != NULL){

            /*comparison will be 1 is the key of input is less than the key   
            of the cursor, and 2 otherwise...*/
            comparison = compare(input, cursor);
            prev = cursor;

            if(comparison == 1){
                is_left = 1;
                cursor = cursor->left;
            }
            else if (comparison == 2){
                is_left = 0;
                cursor = cursor->right;
            }
        }

        if(is_left){
            *prev->left = create_node(input);
            current_leaf = prev->left;
        }
        else{
            *prev->right = create_node(input);
            current_leaf = prev->right;
        }
    }
}

item_t create_node(char *input){

    item_t *new_node = (item_t*)malloc(sizeof(item_t));

    if (new_node == NULL){
        printf("Out of memory. Shutting down.\n");
        exit(EXIT_FAILURE);
    }

    /*Add data to the node...*/
    update_item(input, new_node);

    new_node->left = NULL;
    new_node->right = NULL;

    current_leaf = new_node;

    return *new_node;
}

我希望 root 始终指向输入的第一个项目，而 current_leaf 指向最后处理的项目。如果正在处理的项 (input) 小于最后处理的项 (current_leaf)，compare 返回 1。 update_item 是为新节点(叶子)设置数据的内容。

以上内容并不完整，但这是我目前正在做的事情。我正在努力研究如何编写 add_node 以及如何保持 current_leaf 正确更新。

编辑:修改我的代码

Answer 1

这是 BST 的一个例子。树的结构是:

typedef struct node{
    int data;
    struct node *left, *right;
}node;

让 root 全局化不是一个好主意，因此最好在 main() 中声明它，这样 insert() 将从 main 中调用，如下所示:

int main()
{
    int n,data;
    node *root=NULL;
    printf("How many elements? ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
         scanf("%d",&data);
         insert(&root,data);
    }
    inorder(root);
    return 0;
}

这是插入和遍历二叉树的代码-

void insert(node **root, int data)
{
    node *n1,*temp;
    n1=(node *)malloc(sizeof(node));

    n1->data=data;
    n1->left=n1->right=NULL;
    if(!(*root))
    {
        (*root)=n1;
        //printf("Node inserted\n");
        return;
    }
    temp=*root;
    while(temp!=NULL)
    {
        if(temp->data<temp->data)
        {
            //printf("To the right");
            if(temp->right==NULL)
            {
                temp->right=n1;
                break;
            }
            else
                temp=temp->right;
        }
        else if(temp->data>=n1->data)
        {
            if(temp->left==NULL)
            {
                temp->left=n1;
                break;
            }
            else
                temp=temp->left;
        }
    }
    //printf("Inserted\n");
}

void inorder(node *root)
{
    if(root==NULL)
        return;
    inorder(root->left);
    printf("item: %d",root->data);
    inorder(root->right);
}

The searching will be same almost same logic as insert, please develop it yourself.