mercredi 26 septembre 2018

Depth first search with smart pointers for a binary search tree

This is my first time implementing DFS with smart pointers. I get this unknown error thrown:

    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 &'

I am not sure how to go about fixing this issue. Here is my code:

#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();
}

I tried to follow what others have done in Java since I could not find a good example in C++. I just want to know what I should do for this implementation or if there is a reference I could see, thanks!

Aucun commentaire:

Enregistrer un commentaire