c++ - 二叉搜索树的智能指针深度优先搜索

Question

这是我第一次用智能指针实现 DFS。我收到了这个未知错误:

    1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools
\msvc\14.15.26726\include\xmemory0(881): error C2664: 'Node::Node(Node &&)': 

cannot convert argument 1 from 'std::unique_ptr<Node,std::default_delete<_Ty>>' to 'const int &'

我不确定如何解决这个问题。这是我的代码:

#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <stack>
#include <queue>

struct Node {
    int data;
    std::unique_ptr<Node> left = nullptr;
    std::unique_ptr<Node> right = nullptr;

    Node(const int& x, std::unique_ptr<Node>&& p = nullptr, std::unique_ptr<Node>&& q = nullptr) :
        data(x),
        left(std::move(p)),
        right(std::move(q)) {}
};
std::unique_ptr<Node> root = nullptr;

void insert(std::unique_ptr<Node>& root, const int& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

    if (root == nullptr) {
        root = std::move(newNode);
        return;
    }
    else if (theData < root->data) {
        insert(root->left, theData);
    }
    else {
        insert(root->right, theData);
    }
}

void inorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

void preorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        std::cout << root->data << " ";
        inorderTraversal(root->left);
        inorderTraversal(root->right);
    }
}

void postorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        inorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

int getDepth(std::unique_ptr<Node>& root) {
    if (!root) return 0;

    else {
        int l = getDepth(root->left);
        int r = getDepth(root->right);
        return std::max(l, r) + 1;
    }
}

bool validate(std::unique_ptr<Node>& root, Node* previous) {
    if (root == nullptr) return true;

    if (!validate(root->left, previous)) return false;

    if (previous != nullptr && previous->data >= root->data) return false;

    previous = root.get();

    return validate(root->right, previous);
}

void DFS(std::unique_ptr<Node>& root) {
    std::stack<std::unique_ptr<Node>> s;
    s.push(root);

    while (!s.empty()) {
        std::unique_ptr<Node> x = std::make_unique<Node>(s.top());
        s.pop();
        if (x->right != nullptr) s.push(x->right);
        if (x->left != nullptr) s.push(x->left);
        std::cout << x->data << " ";
    }
}


int main() {

    insert(root, 8);
    insert(root, 10);
    insert(root, 4);
    insert(root, 2);
    insert(root, 6);

    inorderTraversal(root);
    std::cout << "\n";

    preorderTraversal(root);
    std::cout << "\n";

    postorderTraversal(root);
    std::cout << "\n";

    DFS(root);
    std::cout << "\n";

    std::cout << getDepth(root) << "\n";


    if (validate(root, nullptr)) {
        std::cout << "This is a BST!" << "\n";
    }
    else {
        std::cout << "This is not a BST!" << "\n";
    }

    std::cin.get();
}

我试图遵循其他人在 Java 中所做的事情，因为我在 C++ 中找不到一个好的例子。我只是想知道我应该为这个实现做些什么，或者是否有我可以看到的引用，谢谢!

Answer 1

你的错误发生是因为你试图复制不可复制的:即std::unique_ptr<Node>的实例.

但是您的堆栈不必托管 std::unique_ptr<Node> .它可以托管指向 std::unique_ptr<Node> 的 native 指针.或者甚至只是 const Node*

两者如下所示:

void DFS(std::unique_ptr<Node>& root)
{
    if (!root)
        return;

    std::stack<const std::unique_ptr<Node> *> s;
    s.push(&root);

    while (!s.empty())
    {
        auto pp = s.top();
        s.pop();

        if ((*pp)->right)
            s.push(&(*pp)->right);

        if ((*pp)->left)
            s.push(&(*pp)->left);

        std::cout << (*pp)->data << ' ';
    }
}

或者

void DFS(std::unique_ptr<Node>& root)
{
    if (!root)
        return;

    std::stack<Node const*> s;
    s.push(root.get());

    while (!s.empty())
    {
        auto p = s.top();
        s.pop();

        if (p->right)
            s.push(p->right.get());

        if (p->left)
            s.push(p->left.get());

        std::cout << p->data << ' ';
    }
}

通过任何一种更改，您的代码都应该通过编译并实际运行。