实现二叉搜索树

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;

让根目录全局不是一个好主意，所以最好在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);
}

搜索与插入的逻辑几乎相同，请自行开发。