二叉搜索树中的搜索元素

Question

struct node {
    int data;
    struct node *left; /* left tree part */
    struct node *right; /* right tree part */
};

bool search(struct node *root, int element) {
    
    if ( root -> data == element) {
        return true;
    }

    if (root->data < element) {
        search (root->right, element);
    }
    if (root->data > element) {
        search(root->left, element);
    }
    return false;

}

如果在二叉搜索树中找到给定元素，我希望此程序 return 为真。否则 return 为假。这个递归过程有什么问题？

Answer 1

What's the problem for this recursive progress?

如评论中所述，您没有对该函数中递归调用的结果执行任何操作。你想 return 他们这样：

if (root->data < element) {
    return search(root->right, element);
}
if (root->data > element) {
    return search(root->left, element);
}

一旦达到终止递归调用的条件，您就会看到是否找到了元素。

bool search(struct node *root, int element) {

    // element is not found
    if(!root) return false;
    
    // element is found
    if (root->data == element) {
        return true; // terminate recursive calls
    }

    if (root->data < element) {
        return search(root->right, element);
    }
    if (root->data > element) {
        return search(root->left, element);
    }

}

编辑：小心点，不像我，一定要检查 root 是否为 null ;)

二叉搜索树中的搜索元素

Search element in binary search tree

c

binary-search-tree