BST с рекурсией и заданными структурами

Question

Я должен написать несколько методов для BST, и у меня есть некоторые проблемы, позвольте мне объяснить.

У меня есть следующие структуры:

struct node {
    struct node *lChild; 
    struct node *rChild; 
    int value; 
};

и

struct tree {
    struct node *root;
};

вместе со следующими функциями:

struct tree* constructNewTree()
{
    struct tree *T=malloc(sizeof(struct tree));
    T->root=NULL;

    return T;
}

и

struct node* constructNewNode(int i)
{
    struct node *N=malloc(sizeof(struct node));
    N->value=i;
    N->lChild=NULL;
    N->rChild=NULL;

    return N;
}

И в моем основном я должен назвать это (например):

int main()
{
    struct tree *T;
    T=constructNewTree();

    insertKey(5,T);
    insertKey(2,T);
    insertKey(9,T);
    return 0;
}

Что мне нужно сделать, так это создать функцию insertKey (int i, struct tree * T) с использованием рекурсии.

Я хотел сделать что-то вроде

void insertKey(int i, struct tree *T)
{
    if (T->root==NULL) {
        T->root=constructNewNode(i);
        return;
    }
    else {
        if (i<=T->root->value) {
            T->root->lChild=constructNewNode(i);
        else if (i>T->root->value) {
            T->root->rChild=constructNewNode(i);
        }
    }
}

Но это не очень далеко, использование рекурсии позволило бы мне снова вызвать insertKey, но я не могу использовать узел и дерево одинаково.

Кто-нибудь знает, как я мог бы сделать это, не изменяя данные структуры?

Большое спасибо.

Answer 1

Ваш insertKey принимает дерево в качестве аргумента. Дерево - это только указатель на самый верх.

Я рекомендую вам написать функцию insertKey, которая принимает Node в качестве аргумента. Также в этой функции вы должны проверить, есть ли другое дерево слева / справа от ребенка.

В настоящее время вы просто создаете новый узел независимо от того, что там есть. Это заменит все предыдущие вставки.