c++ - 二叉搜索树中的搜索函数实现

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;
            }
    };

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
}

Also which would be the better way to implement this recursive or iterative.

没有确定的答案。如果您可能存储很多值，因此搜索深度变大，您不希望递归调用，因为这样可能会导致堆栈溢出。