在二叉树中查找元素

Question

如何在二叉树中搜索不是 bst 的元素？

这是我的树的外观示例

这就是我正在做的事情：

treeNode * find(treeNode *T, int x) {
    if(T == NULL) return NULL;
    if(x == T -> element) {
        return T;
    }
    find(T -> left, x);
    find(T -> right, x);
    return NULL;
}

问题是满足if的时候递归没有停止

Answer 1

您的递归调用缺少 return 语句。因此，不仅递归会继续，而且该值永远不会 returned 给原始调用者。

treeNode * find(treeNode *T, int x) {
    if(T == NULL) return NULL;
    if(x == T -> element) {
        return T;
    }
   auto findLeft = find(T -> left, x)
   if (findLeft) return findLeft;
   return find(T -> right, x);
}

Answer 2

您忽略了递归调用中的 return 值：

treeNode * find(treeNode *T, int x) {
    if(T == NULL) return NULL;
    if(x == T -> element) {
        return T;
    }
    treeNode *result = find(T -> left, x);
    if ( result ) // if the return value was found, this will not be NULL, so return the node
        return result;
    return find(T -> right, x); // will return NULL if its not found
}

Answer 3

在上下文中 -

The problem is that the recursion does not stop when the if is satisfied

-原因是因为你必须检查你的递归调用是否 return 一个有效的结果并停止进一步搜索。

改变-

find(T -> left, x);
find(T -> right, x);

-类似于-

    treeNode* result = find(T -> left, x);
    if (result != NULL)
        return result;
    return find(T -> right, x);

Answer 4

查看每次尝试的结果x

treeNode * find(treeNode *T, int x) {
    if(T == NULL) return NULL;
    if(x == T -> element) {
        return T;
    }
    treeNode* result = find(T -> left, x);
    if (result)
        return result;

    result = find(T -> right, x);
    if (result)
        return result;

    return NULL;
}

ETA：到此结束可以简化。如果不是 NULL，则返回 result，否则返回 NULL...与返回 result 相同。实际上，我们所做的只是返回从对 find 的调用返回的值。所以...

treeNode * find(treeNode *T, int x) {
    if(T == NULL) return NULL;
    if(x == T -> element) {
        return T;
    }
    treeNode* result = find(T -> left, x);
    if (result)
        return result;

    return find(T -> right, x);
}

Answer 5

二叉树通常用于保持数据排序并快速 add/find 按该顺序排列的项目。

无序二叉树应用不多。因此，当我看到您的树图片时，我怀疑您错过了最重要的属性 b 树，并且可能是您任务的重要部分。

如果您注意到顺序在您的任务中很重要，请查看该代码：

class Node;

using NodePtr = std::uniqeu_ptr<Node>;
class Node
{
    int value;
    NodePtr left;
    NodePtr right;
};

void insert(NodePtr &node, int value)
{
    if (node) {
       insert((value < node->value) ? node->left : node->right, value);
    } else {
       node.reset(new Node{value});
    }
}

Node* find(Node* node, int value)
{
    if (!node) {
       return nullptr;
    }
    if (node->value == value) {
       return node.get();
    }
    return find((value < node->value) ? node->left.get() : node->right.get(), value);
}

在二叉树中查找元素

Find an element in a binary tree

c++

binary-tree

data-structures