I'm programming a family tree, and I was instructed to use lambda in the depth first search. I've tried to implement it, and I understand the basics of lambdas. I can't for the life of me understand how to make it work with the instructions I was getting from the teacher. Here is how I've tried to apply the code.
void depthFirst(const std::function<void(Node* )>& node) {
auto traverse = [](Node* node) {
node(this);
for( auto search: Person) {
search->depthFirst(node);
}
};
}
template<typename T>
class Node {
public:
explicit Node(const T& data, Node* parent = nullptr) : data_(data), parent_(parent) {}
explicit Node(T data): data_(std::move(data)) {}
virtual ~Node() = default;
T getData() const {
return data_;
}
void setData(T data) {
data_ = data;
}
Node *getParent() const {
return parent_;
}
void setParent(Node *parent) {
parent_ = parent;
}
bool leftExists() {
return this->left_ != nullptr;
}
void setLeft(const std::unique_ptr<Node> &left) {
left_ = left;
}
const std::unique_ptr<Node> &getLeft() const {
return left_;
}
bool rightExists() {
return this->right_ != nullptr;
}
const std::unique_ptr<Node> &getRight() const {
return right_;
}
void setRight(const std::unique_ptr<Node> &right) {
right_ = right;
}
private:
T data_; // node's data value with use of template
Node *parent_; // pointer to point at the parent node
std::unique_ptr<Node> left_;
std::unique_ptr<Node> right_;
};
template<typename T>
class Person {
public:
Person();
Person(std::string firstName, std::string lastName, int age, std::string gender, bool alive);
// setters
void setFirstName(const std::string &firstName);
void setLastName(const std::string &lastName);
void setGender(const std::string &gender);
bool isAlive() const;
void setAlive(bool alive);
void setAge(int age);
void setPerson();
// getters
const std::string& getFirstName() const;
const std::string& getLastName() const;
const std::string& getGender() const;
int getAge() const;
bool getAlive() const;
//operators
void displayPerson()const; // for testing atm
void setPerson(const Person& Person);
private:
std::string firstName_;
std::string lastName_;
int age_{};
std::string gender_;
bool alive_ = true;
};
// Functions that sets the data for the Person --->
template<typename T>
void Person<T>::setFirstName(const std::string &firstName) {
firstName_ = firstName;
}
template<typename T>
void Person<T>::setLastName(const std::string &lastName) {
lastName_ = lastName;
}
template<typename T>
void Person<T>::setGender(const std::string &gender) {
gender_ = gender;
}
template<typename T>
bool Person<T>::isAlive() const {
return alive_;
}
template<typename T>
void Person<T>::setAge(int age) {
age_ = age;
}
template<typename T>
void Person<T>::setAlive(bool alive) {
alive_ = alive;
}
// This is the default constructor, overload constructor and destructor for the person class --->
template<typename T>
Person<T>::Person(std::string firstName, std::string lastName, int age, std::string gender, bool alive) :
firstName_(std::move(firstName)), lastName_(std::move(lastName)), age_(age), gender_(std::move(gender)), alive_(alive) {}
template<typename T>
Person<T>::Person() {
}
// Functions that gets the data for the Person --->
template<typename T>
int Person<T>::getAge() const {
return 0;
}
template<typename T>
const std::string &Person<T>::getFirstName() const {
return this->firstName_;
}
template<typename T>
const std::string &Person<T>::getLastName() const
{
return this->lastName_;
}
template<typename T>
const std::string &Person<T>::getGender() const
{
return this->gender_;
}
template<typename T>
bool Person<T>::getAlive() const {
return false;
}
template<typename T>
class FamilyTree
{
public:
FamilyTree();
explicit FamilyTree(Node<T>* root); // Create new tree
FamilyTree(T data):
/*
void addNewPerson();
void addFather();
void addMother();
*/
void addNode(T data);
bool isEmpty();
private:
Node<T> *root_;
void addNode(Node<T>* root, T data);
};
template<typename T>
FamilyTree<T>::FamilyTree(Node<T> *root) {
this->root_ = root;
}
template<typename T>
bool FamilyTree<T>::isEmpty() {
return this->root_ == nullptr;
}
template<typename T>
FamilyTree<T>::FamilyTree() {
this->root_ = nullptr;
}
template<typename T>
void FamilyTree<T>::addNode(T data) {
if(root_ == nullptr)
root_ = std::make_unique(Node<T>(data));
else
addNode(root_, data);
}
//main
//just for test
void Person::displayPerson() const {
std::cout << "First Name: " << this->getFirstName() << std::endl;
std::cout << "Last Name: " << this->getLastName() << std::endl;
std::cout << "Age: " << this->getAge() << std::endl;
std::cout << "Gender: " << this->getGender() << std::endl;
std::cout << "Alive: " << this->getAlive() << std::endl << std::endl;
}
//main
int main(){
// Node test
Node node;
Node* setLeft(reinterpret_cast<Node *>(1));
Node* setRight(reinterpret_cast<Node *>(2));
std::cout << node.getData() << std::endl;
std::cout << node.getLeft() << std::endl;
std::cout << node.getRight() << std::endl;
//Person test
Person p0, p1("Robert", "Dane", 37, "Male", 1), p2("John", "Doe", 35, "Female", 1);
p0.displayPerson();
p1.displayPerson();
p2.displayPerson();
// FT test
return 0;
}
void ignoreLine() // inspiration from here: https://stackoverflow.com/questions/11523569/how-can-i-avoid-char-input-for-an-int-variable
{
std::cin.clear();
std::cin.ignore(INT_MAX, '\n');
}
void showMainMenu() // hold the output for the main menu
{
std::cout << "Welcome" << std::endl;
std::cout << "Please enter a number for your choice below:\n" << std::endl;
std::cout << "(1) Add new person to tree" << std::endl;
std::cout << "(2) Show information for a person" << std::endl;
std::cout << "(3) Print complete family-tree" << std::endl;
std::cout << "(4) Used for testing new choices" << std::endl;
std::cout << "(0) Quit" << std::endl;
std::cout << "\nYour choice: " << std::endl;
}
int main()
{
familyTree fT; // used to access/init. familytree class.
bool exit = true;
int option;
while (exit)
{
showMainMenu();
std::cin >> option;
while (std::cin.fail())
{
ignoreLine();
std::cout << "\nOnly a number between 0 and 10 is allowed: ";
std::cin >> option;
}
switch (option)
{
case 1:
fT.addNewPerson();
break;
case 2:
std::cout << "Enter name of person to show information: ";
int temp;
std::cin >> temp;
fT.show(fT.search(temp));
break;
case 3:
fT.printInOrder(fT.root, 0);
break;
case 4:
/* n/a */
break;
case 0:
exit = false;
break;
default: ;
}
std::cout << "\nPress enter to continue.." << std::endl;
ignoreLine();
}
return 0;
Old code that worked:
person *familyTree::traverseLeft(person *ptr, const std::string& person)
{
ptr = ptr->left;
while (ptr != nullptr)
{
if ((ptr->firstName) == person) {
return ptr;
}
else if (traverseRight(ptr, person) != nullptr)
{
return traverseRight(ptr, person);
}
else
{
ptr = ptr->left;
}
}
return nullptr;
}
person *familyTree::traverseRight(person *ptr, const std::string& person)
{
ptr = ptr->right;
while (ptr != nullptr)
{
if ((ptr->firstName) == person)
{
return ptr;
}
else if (traverseLeft(ptr, person) != nullptr)
{
return traverseLeft(ptr, person);
}
else
ptr = ptr->right;
}
return nullptr;
edit: The teacher told me that node(this); was supposed to point to the current node being searched. I may not have the most pedagogical correct teacher. But it is supposed to search the binary tree depth first, node for node. There is no use of vector or indexes, as I was told it was not needed. There is a class node and a class person that is implemented in to the node. If there is a better way of traversing a tree than this, feel free to let me know.
edited to add Person and Node.
edited to show old code that we got told to burn. I only got the instructions on lambda in person, but in short, was told to create lambda to use on a current node within a void function search, then go right, then go left. It could be reused in delete and other functions.
edited to add last of all code. Should I just go back to the old code (but less OOP) that I know compile and works? I got so much bad reviews on the old one that my group decided to start a new. But right now it's just a mess. (Keep in mind that the "new" code now is on different header files, so it might be more messy in regards to the console and main)
CodePudding user response：
You're thinking inside out or upside down - you should pass a lambda (or another function) to this function, and this should apply that function in a depth-first manner.
You also need a helper function that takes a Node* that indicates the current node.
A very simple example, with a preorder traversal:
private:
void traverse(const std::function<void(Node*)>& action, Node* current)
{
if (current != nullptr)
{
action(current);
traverse(action, current->getLeft());
traverse(action, current->getRight());
}
}
public:
void traverse(const std::function<void(Node*)>& action)
{
traverse(action, root_);
}
And you are supposed to use it something like this:
FamilyTree tree = ... whatever ...;
auto process = [](const Node* p) { ... print p ... };
// This will now print in preorder.
tree.traverse(process);
CodePudding user response：
Is there a reason why you direct initialize your private variables in class Person as rvalues (ie. std::move?) ? std::string can bind permitted rvalues as long as they're const.
For instance the code below:
template<typename T>
Person<T>::Person(std::string firstName, std::string lastName, int age, std::string gender, bool alive) \
: firstName_(std::move(firstName)), lastName_(std::move(lastName)), age_(age), gender_(std::move(gender)), alive_(alive) {}
Could be:
template <typename T>
Person<T>::Person(std::string firstName, std::string lastName, int age, std::string gender, bool alive) \
: firstName_{firstName}, lastName_{lastName}, age_{age}, gender_{gender}, alive_{alive} {}
Making the the members in Person rvalues would be preparing them for a move, which it does not look like you're doing earlier in the code.
template <typename T>
void Person<T>::setFirstName(const std::string &firstName)
{
firstName_ = firstName;
}
The values are being passed as lvalue references in the function parameters of Person, which you are changing to rvalues in the constructor of said class. There is no need to do this. They are not meant to be temporary values. The use of {} instead of () eliminates the chance of implicit conversion (narrowing) on part of the members.