c - 在树中搜索数字

Question

typedef struct Tree{
    int value;
    struct Tree* leftNode;
    struct Tree* rightNode;
}Tree;

Tree* Is_Existing_Number(Tree *root, int number, bool found) {

    if (!root || found)
        return root;

    if (root->value == number)
        found = true;

    else {
         Is_Existing_Number(root->leftNode, number, found);
         Is_Existing_Number(root->rightNode, number, found);
    }
}

我有一个问题：我想查找一棵树中是否有特定的数字。如果是这样，我希望函数返回一个指向它的指针，所以基本上我想遍历整个树并检查树中是否存在该数字。

为什么这段代码不起作用？

标签： crecursionbinary-treebinary-search-tree

Answer 1

我假设您使用二叉搜索树 (BST)。否则，使用二叉树将毫无意义；数组/列表将适合模式。

BST 中的值是有序的。因此，存储在子节点（即leftNode）分支中的所有值都大于当前节点中的值。另一个子节点（即rightNode）中的值小于当前节点中的值。

这让它在查找值时跳过整个子分支。

代码应如下所示：

Tree *FindNumber(Tree* root, int value) {
  if (root == NULL) { // hit the leaf, value is absent
    return NULL;
  } else if (root->value == value) { // value found
    return root;
  } else if (root->value > value) { // try left node
    return FindNumber(root->leftNode, value);
  } else {
    return FindNumber(root->rightNode, value); // try right node
  }
}

您可能需要根据树的排序方式交换左右节点的角色。

如果函数返回非 NULL，则该值存在于树中。