二叉搜索树

Question

所以我用 C 编写了一个二叉搜索树，它看起来是这样的结构：

struct tnode {
    int content;
    struct tnode *left; /* left tree part */
    struct tnode *right; /* right tree part */
};

我的主要方法：

int main() {

    struct tnode *Baum = NULL;
    struct tnode *tmpPos = NULL;
    Baum = addelement (Baum, 32);
    Baum = addelement(Baum, 50);
    Baum = addelement(Baum, 60);
    tmpPos = searchnode(Baum,50);
}

所以基本上这为我创建了一个包含 3 个元素 (32,50,60) 的二叉搜索树。我的 searchnode 方法应该将指针移动到“50”，这样我就可以在之后删除它。但是，如果我正在搜索的元素是我的二叉搜索树的根，我的搜索节点方法只有 returns 指针。

搜索节点：

struct tnode *searchnode(struct tnode *p, int nodtodelete) {
    if (p == NULL) {
        printf("Baum ist leer oder Element nicht vorhanden \n");
    }

    if ( p -> content == nodtodelete) {
        return p;
    }

    if (p->content > nodtodelete) {
        searchnode (p->right, p->content);
    }
    if (p->content < nodtodelete) {
        searchnode(p->left, p->content);
    }
}

也许你们可以帮助我。

Answer 1

您应该传递要搜索的值，而不是节点的值：

searchnode (p->right, nodtodelete);
                      ^

对另一个递归调用进行相同的更改。

searchnode(p->left, nodtodelete);

Answer 2

你的函数有未定义的行为，因为它在递归调用中没有任何 return 语句。

此外，需要修复递归调用以使用正确的输入。

struct tnode *searchnode(struct tnode *p, int nodtodelete)
{
   if (p == NULL)
   {
      printf("Baum ist leer oder Element nicht vorhanden \n");
      return NULL;
   }

   if ( p -> content == nodtodelete)
   {
      return p;
   }

   // This is copied from OP's question but it seems suspect.
   // It should probably be:
   // if (p->content < nodtodelete)
   if (p->content > nodtodelete)
   {
      return searchnode (p->right, nodtodelete);
   }

   return searchnode(p->left, nodtodelete);
}

二叉搜索树

Binary Search Tree

c

binary-tree

binary-search-tree