没有节点的二叉搜索树递归结构

Question

我必须为大学完成一个项目，但我无法弄清楚它是如何完成的。

问题是我想用下面给出的函数构建一个二叉查找树应用程序。我需要构建某种递归，但我的问题是bst_insert（tree * bst，int key）函数将树作为输入而不是节点。所以我的想法，我写在下面（bst_insert（bst-> root_node-> left，key）;）不起作用。

有人知道我能做些什么来获得可行的解决方案吗？

非常感谢！

这里是我的头文件的一部分（tree.h中）

typedef struct node { 
     int key; 
     struct node *left; 
     struct node *right; 
    } node; 

    typedef struct tree { 
     node *root_node; 
     int (*compare_keys)(int x, int y); 
    } tree; 

    void bst_insert(tree *bst, int key); 

这里是tree.c文件

void init(tree *bst) { 
    bst->root_node = 0; 
    bst->compare_keys = 0; 
} 

void bst_insert(tree *bst, int key) {  
    if (bst->root_node == NULL) { 
    bst->root_node = (node*)malloc(sizeof(node)); 
    bst->root_node->key = key; 
    bst->root_node->left = NULL; 
    bst->root_node->right = NULL; 
    } 
    else { 
    if (key < bst->root_node->key) { 
     bst_insert(bst->root_node->left, key); 
    } 
    if (key > bst->root_node->key) { 
     bst_insert(bst->root_node->right, key); 
    } 
    } 
} 

Answer 1

即使你被允许的一部分，通过bst->root_node->left直接不会工作。函数参数按值传递，递归调用可能需要更改bst->root_node->left的值（如果它是NULL）。

如果你想有一个功能f能够改变一个变量x，最简单的解决方案是f采取一个指针，并称呼其为f(&x)（合格x地址）。我们可以应用到你的递归插入功能：

void bst_insert(node **ppnode, int key) {  
    if (*ppnode == NULL) { 
     *ppnode = malloc(sizeof **ppnode); 
     (*ppnode)->key = key; 
     (*ppnode)->left = NULL; 
     (*ppnode)->right = NULL; 
    } 
    else if (key < (*ppnode)->key) { 
     bst_insert(&(*ppnode)->left, key); 
    } 
    else if (key > (*ppnode)->key) { 
     bst_insert(&(*ppnode)->right, key); 
    } 
} 

此代码的工作，但正如你所说，它有错误的类型。

然而，这不是一个大问题：我们可以简单地重命名这个函数，并提供一个正确名称和类型的包装。

static void bst_node_insert(node **ppnode, int key) {  
    if (*ppnode == NULL) { 
     *ppnode = malloc(sizeof **ppnode); 
     (*ppnode)->key = key; 
     (*ppnode)->left = NULL; 
     (*ppnode)->right = NULL; 
    } 
    else if (key < (*ppnode)->key) { 
     bst_node_insert(&(*ppnode)->left, key); 
    } 
    else if (key > (*ppnode)->key) { 
     bst_node_insert(&(*ppnode)->right, key); 
    } 
} 

void bst_insert(tree *bst, int key) { 
    bst_node_insert(&bst->root_node, key); 
} 

这段代码的结构反映您的数据类型的结构：您有一个包含一个指向node，其中包含指向本身tree。同样，树插入功能bst_insert包含对节点插入功能bst_node_insert的调用，该功能包含对其自身的调用。

Answer 2

既然你说你不能改变bst_insert的定义，我认为解决的办法是在调用函数之前创建一个新的临时树。这感觉有点怪，但低于类似的代码应工作：

tree tempTree; 
... 
if (key < bst->root_node->key) { 
    if (bst->root_node->left == NULL) 
    { 
     // Add a new node 
     bst->root_node->left = malloc(sizeof(node)); 
     bst->root_node->left->key = key; 
     bst->root_node->left->left = NULL; 
     bst->root_node->left->right = NULL; 
     return; 
    } 

    // Make a temporary tree for a recursive call 
    tempTree.root_node = bst->root_node->left; 
    tempTree.compare_keys = bst->compare_keys; 
    bst_insert(&tempTree, key); 
    return; 
} 

此外，我认为你正在做的事情错在这条线：

if (key < bst->root_node->key) { 

我敢肯定，你应该使用compare_keys函数。可能是这样的：

if (compare_keys(key, bst->root_node->key) < 0) {