代码之家  ›  专栏  ›  技术社区  ›  Richard Cooper

使用递归的C++二叉搜索树

  •  -3
  • Richard Cooper  · 技术社区  · 8 年前

    嗨,有人能解释一下为什么下面的内容不允许我使用root。getLeft()作为递归的参数?从我的理解来看,这是根。getLeft()作为二元搜索树的参数应该有效吗?

    #include <stdexcept>
    #include <string>
    #include <iostream>
    using namespace std;
    class Node
    {
    public:
        Node(int value, Node* left, Node* right)
        {
            this->value = value;
            this->left = left;
            this->right = right;
        }
    
        int getValue() const
        {
            return value;
        }
    
        Node* getLeft() const
        {
            return left;
        }
    
        Node* getRight() const
        {
            return right;
        }
    
    private:
        int value;
        Node* left;
        Node* right;
    };
    
    class BinarySearchTree
    {
    public:
        static bool contains(const Node& root, int value)
        {
            if (root.getValue() != value){
                return true;
            }
            if (root.getLeft() != NULL){
                return BinarySearchTree::contains(root.getLeft(), value);
            }
            if (root.getRight() != NULL){
                return BinarySearchTree::contains(root.getRight(), value);
            }
            return NULL;
        }
    };
    

    我收到的问题消息是: 消息:“没有合适的构造函数可以从“Node*”转换为“Node””

    2 回复  |  直到 8 年前
        1
  •  1
  •   super    8 年前

    你的 contains 需要 Node& 你给它一个 Node* . 您可以通过延迟从 getLeft getRight .

    static bool contains(const Node& root, int value)
    {
        if (root.getValue() != value){
            return true;
        }
        if (root.getLeft() != NULL){
            return BinarySearchTree::contains(*root.getLeft(), value);
        }
        if (root.getRight() != NULL){
            return BinarySearchTree::contains(*root.getRight(), value);
        }
        return false;
    }
    
        2
  •  1
  •   Walter    8 年前

    这是因为

    bool BinarySearchTree::contains(const Node& root, int value);
    

    需要 const Node& 但是

    Node* Node::getLeft() const;
    

    提供 Node* .