二叉搜索树中的搜索功能实现

Question

我已经实现了一个名为“searchkey”的函数，以便在二叉搜索树中如果存在键则返回节点，但它返回的是根节点。我添加了一个最小可重现的代码。
虽然同样的迭代方法能够工作。实现这个功能使用递归还是迭代更好呢？

template<class T>
    class Node{
    public:
        T m_data;  
        Node<T>* m_left;
        Node<T>* m_right;
    
        Node(T data){
             m_data=data;
             m_left=nullptr;
             m_right=nullptr;
         }
    };
    
    template<class T>
    class bst {
    private:
        Node<T>* root;
    
    public:
        bst() { root = nullptr; }
        ~bst() { deltree(root); }
        void addnode(Node<T>* node, T data) {
            
            if(this->root == nullptr) {
                Node<T>* new_node= new Node<T>(data);
                this->root = new_node;
            } else if(data > node->m_data) {
                if(node->m_right != nullptr) {
                    addnode(node->m_right, data);
                } else {
                    Node<T>* new_node = new Node<T>(data);
                    node->m_right = new_node;
                }
            } else if(data < node->m_data) {
                if(node->m_left != nullptr) {
                    addnode(node->m_left, data);
                } else {
                    Node<T>* new_node = new Node<T>(data);
                    node->m_left = new_node;
                }
            }
        }
        void addnode(T data) { addnode(this->root, data); }
    
         Node<T>* searchkey(T data) { 
            return searchkey(data,this->root);
    }
    
            Node<T>* searchkey(T data, Node<T> *node) {
        if (node == nullptr) { // <-- check if node is null
            return node;
        } else if (data == node->m_data) {
            return node;
        } else if (node->m_data > data) {
            searchkey(data, node->m_left);
        } else if (node->m_data < data) {
            searchkey(data, node->m_right);
        }
        return node;
    }
    
    void deltree(Node<T>* node) {
            if(node) {
                deltree(node->m_left);
                deltree(node->m_right);
                delete node;
            }
    };

- user10057478

Answer 1

在你的搜索函数中似乎缺少了一些return语句。此外，测试data == node->m_data是不必要的。函数末尾的回退return意味着如果你在递归调用时return，则会找到匹配项。

Node<T>* searchkey(T data, Node<T> *node) {
    if (node == nullptr) { // <-- check if node is null
        return node;
    } else if (node->m_data > data) {
        return searchkey(data, node->m_left);
    } else if (node->m_data < data) {
        return searchkey(data, node->m_right);
    }
    return node; // match found
}

在您的原始代码中，您调用了 searchkey 但没有返回它返回的值。该函数继续返回作为函数参数给定的相同 node ，除搜索存储在 root 节点中的值之外，在所有情况下都会得到错误的结果。

另一种观点：

Node<T>* searchkey(T data, Node<T> *node) {
    if (node != nullptr) {
        if (node->m_data > data) {
            node = searchkey(data, node->m_left);
        } else if (node->m_data < data) {
            node = searchkey(data, node->m_right);
        } // else { here we know that node->m_data == data }
    }
    return node; // nullptr or the matching Node* is returned
}

同时，递归和迭代哪种方式更好？

并没有确切的答案。如果你要存储很多值，使得搜索深度变大，那么你不想使用递归调用，因为可能会导致栈溢出。

- Ted Lyngmo

---

虽然这个可以正常工作，但你能否解释一下它是如何工作的？ - user10057478

我在递归方面有点生疏，所以我想问一下这个递归调用是如何知道我们已经匹配了关键字的，因为我们没有在节点值和提供的关键字之间进行任何相等比较。 - user10057478

@Tushar 这只是剩下的唯一选择。我们已经确定 node->m_data 既不小于也不大于 data - 所以它们相等。我会在另一个视图中添加一条注释。 - Ted Lyngmo

好的，我有这个想法，但对此持怀疑态度！实际上，我能够理解的是，searchkey()将返回一个节点给它的递归调用者，然后调用其祖先节点，从而我们得到了该节点。 - user10057478

@Tushar 是的，它变成了一个调用链，其中叶节点将返回匹配的 Node* 或 nullptr。然后将此返回值向上传播，直到返回给 searchkey() 的初始调用者。 - Ted Lyngmo