c - 具有递归和给定结构的 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 采用 Tree 作为其参数。树只是指向最顶部的指针。

我建议您编写一个 insertKey 函数，该函数采用 Node 作为其参数。同样在这个函数中，您必须检查左/右子节点上是否还有另一棵树。

目前，您只需构造一个新节点，而不管那里有什么。这将覆盖任何以前的插入。