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