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

Question

我必须为大学完成一个项目，但我不知道如何完成。

问题是我想使用以下给定函数构建一个二叉搜索树应用程序。我需要构建某种递归，但我的问题是 bst_insert(tree *bst, int key) 函数将 tree 作为输入而不是节点。所以我在下面写的想法(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);
}

此代码的结构反射(reflect)了数据类型的结构:您有一个包含指向节点的指针的树，该节点包含指向其自身的指针。同样，树插入函数 bst_insert 包含对节点插入函数 bst_node_insert 的调用，该函数包含对其自身的调用。