如何在不使用 CC_TREE** 的情况下在 BST 中插入节点？

Question

所以我有一段代码，我必须在其中向 BST 添加一个节点。我的结构如下：

typedef struct _CC_TREE {
    // Members
    int Value;
    struct _CC_TREE* LChild;
    struct _CC_TREE* RChild;
} CC_TREE;

头文件中的插入函数如下所示：

int TreeInsert(CC_TREE *Tree, int Value);

我必须 return 插入状态。

我试着用另一个函数来做，并将它添加到树中

CC_TREE* InsertNewNode(CC_TREE* Tree, int Value)
{
    if (NULL == Tree)
    {
        Tree = (CC_TREE*)malloc(sizeof(CC_TREE));
        Tree->LChild = NULL;
        Tree->RChild = NULL;
        Tree->Value = Value;
        return Tree;
    }
    if (Value <= Tree->Value)
    {
        Tree->LChild = InsertNewNode(Tree->LChild, Value);
    }
    else if (Value >= Tree->Value)
    {
        Tree->RChild = InsertNewNode(Tree->RChild, Value);
    }
    return Tree;
}

int TreeInsert(CC_TREE *Tree, int Value)
{
    CC_UNREFERENCED_PARAMETER(Tree);
    CC_UNREFERENCED_PARAMETER(Value);

    Tree = InsertNewNode(Tree, Value);
    return 0;
}

我尝试在我的主要函数中构建树：

int retVal = -1;
CC_TREE* usedTree = NULL;

retVal = TreeCreate(&usedTree);
if (0 != retVal)
{
    printf("TreeCreate failed!\n");
    goto cleanup;
}

retVal = TreeInsert(usedTree, 20);
if (0 != retVal)
{
    printf("TreeInsert failed!\n");
}

但由于某种原因 usedTree 仍然为空。我知道我应该在插入函数中使用 CC_TREE** Tree，但我不允许这样做。

Answer 1

The insert function in the header file looks like this:
int TreeInsert(CC_TREE *Tree, int Value);

如果您不能更改函数签名或（呃！）使用全局变量 return 指向调用者的根指针，那么您最好的选择可能是使用虚拟树根。那看起来像这样：

int TreeInsert(CC_TREE *Tree, int Value) {
    // Tree points to a dummy root node containing no data.
    // Tree->LChild is the actual root pointer
    CC_TREE *root = Tree->LChild;
    int status = 0;

    // ... perform insertion, possibly resulting in a different value for the
    // root pointer ...

    Tree->LChild = root;
    return status;
}

假设 TreeInsert() 的第一个参数始终是指向 CC_TREE 的有效指针。如果您这样做，那么 所有其他树函数应该类似地工作。

您可以像这样使用 main() 中的那个：

    int retVal;
    CC_TREE dummy_tree_root = { 0 };
    
    retVal = TreeInsert(&dummy_tree_root, 42);

请注意，此方法实际上通过间接路由使用双指针（无双关语意）。 CC_TREE * 本身不是双指针，但在该指针与其指向的节点的左或右子节点之间仍然存在两级间接。

另请注意，一种更简洁的方法是提供一个表示整个树的包装结构，而不是为此目的使用裸树节点或树节点指针。数据结构将是这样的：

struct node {
    int value;
    struct node *left;
    struct node *right;
};

struct tree {
    struct node *root;
    // optionally other data, such as size, height, etc.
};

如何在不使用 CC_TREE** 的情况下在 BST 中插入节点？

How to insert a node in a BST without using CC_TREE**?

c

binary-tree

binary-search-tree

data-structures