使用递归函数在二叉搜索树中插入项目

Question

问题：当指针在嵌套结构中时，如何在 BST 中插入项？
语言： 仅限 C。

我知道二叉搜索树以及如何插入删除和打印。但是这次我有嵌套结构，内部结构包含指针。所以我需要帮助/提示如何去做。

示例传统上我们有这样的结构

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

在适当的地方插入节点是这样的

struct node* insert(struct node* node, int data)
 {
     if (node == NULL) 
    {
       // code to implement root code;
       node = create_node(); 
     }
     else
     {
       // 2. Otherwise, recur down the tree
       if (data <= node->data) 
       { 
         node->left = insert(node->left, data);
       } 
       else 
      {
        node->right = insert(node->right, data);
      }
     return(node);
     }
 }

但是我现在的是嵌套结构

struct link
{
   struct link *left;
   struct link *right;
};

struct item
{
   struct link link; 
   uint8_t c;
};

由于此处 item 没有指向 left 和 right 的指针，我将如何以递归方式插入 item 。我的尝试

 struct item* insert_item( item* root, uint8_t key )
{
    if( !root )
    {
        root = create_item( key ); // some function create_item to create first item
    }
    /* Otherwise, recur down the tree */
    else
   {
        if( key < root->c )
        {
            insert_item( ); // The node  does not have pointer ?? how would I traverse left or right?
        }
        else
        {
          // how would I apply recursive to right side of tree?

        }
   }
  return root;
}

Answer 1

在insert_item()中使用类似这样的东西向左或向右遍历：

root.link->left
root.link->right

但请记住，在您的 insert 方法中，您将返回 void 除了 *node 就像传统插入一样。

请注意，您的 struct node* insert(struct node* node, int data) 将给出 Undefined Behavior，因为 node == NULL 时没有 return 语句。

编辑： 正如 OP 在评论中所问的那样，"but root.link->left is of type link. how it will work ?"

所以改变

struct link
{
   struct link *left;
   struct link *right;
};

到，

struct link
{
   struct item *left;
   struct item *right;
};

这将解决您的问题。但是不要忘记struct item的前向声明。否则在 struct link 中编译器将引发错误，因为它不知道 item 是什么。

Answer 2

解决方案是使用强制转换。

int insert(struct link** node, uint8_t data) {
  if (*node == NULL) {
    // code to implement root code;
    *node = malloc( sizeof(struct item) );
    if(*node == NULL) return -1;
    ( (struct item*) *node)->c = data;
    ( (struct item*) *node)->link.left = ( (struct item*) *node)->link.right = NULL;
  } else {
    // 2. Otherwise, recur down the tree
    int rc;
    if (data <= ( (struct item*) *node)->c) { 
      rc = insert(&( ( (struct item*) *node)->link.left ), data);
      if( rc < 0 ) return rc;
    } else {
      rc = insert(&( ( (struct item*) *node)->link.right ), data);
      if( rc < 0 ) return rc;
    }
  }
  return 0;
}

请注意，我对您的代码进行了一些更改。即，我不再假设 node->left 和 node->right 未分配。

使用递归函数在二叉搜索树中插入项目

using recursive function to insert item in Binary search tree

c

recursion

pointers

binary-search-tree