如何在深度优先函数中实现 lambda

Question

我正在编写一个家谱，我被指示在深度优先搜索中使用 lambda。我已经尝试实现它，并且我了解 lambda 的基础知识。我终其一生都无法理解如何按照我从老师那里得到的指示让它发挥作用。这是我尝试应用代码的方式。

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: 
    {
        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;

有效的旧代码：

    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;

编辑：老师告诉我那个node(this);应该指向正在搜索的当前节点。我可能没有最正确的老师。但它应该首先搜索二叉树深度，一个节点一个节点。没有使用向量或索引，因为我被告知不需要。有一个 class 节点和一个在节点中实现的 class 人。如果有比这更好的遍历树的方法，请随时告诉我。

编辑以添加人员和节点。

编辑以显示我们被告知要刻录的旧代码。我只亲自得到了有关 lambda 的说明，但简而言之，我被告知要创建 lambda 以在 void 函数搜索中的当前节点上使用，然后向右走，然后向左走。它可以在删除和其他功能中重复使用。

已编辑以添加所有代码中的最后一个。我是否应该回到我知道可以编译和工作的旧代码（但更少的 OOP）？我对旧的有很多不好的评论，以至于我的小组决定开始一个新的。但现在只是一团糟。（请记住，“新”代码现在位于不同的头文件中，因此在控制台和主文件方面可能会更加混乱）

Answer 1

您直接将 class Person 中的私有变量初始化为右值（即 std::move？）是有原因的吗？ std::string 可以绑定允许的右值，只要它们是常量即可。

例如下面的代码：

        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(std::string firstName, std::string lastName, int age, std::string gender, bool alive) \
        : firstName_{firstName}, lastName_{lastName}, age_{age}, gender_{gender}, alive_{alive} {}

使 Person 中的成员成为右值将为他们的移动做准备，这看起来不像您在代码的前面所做的那样。

        template <typename T>
        void Person<T>::setFirstName(const std::string &firstName)
        {
        firstName_ = firstName;
        }

这些值在 Person 的函数参数中作为左值引用传递，您在上述 class 的构造函数中将其更改为右值。没有必要这样做。它们并不意味着是临时值。使用 {} 而不是 () 消除了部分成员隐式转换（缩小）的机会。

Answer 2

你正在考虑从内到外或颠倒 - 你应该传递一个 lambda（或另一个函数）给这个函数，这应该在 depth-first 方式。

您还需要一个带有 Node* 指示当前节点的辅助函数。

一个非常简单的例子，先序遍历：

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_); 
}

你应该像这样使用它：

FamilyTree tree = ... whatever ...;
auto process = [](const Node* p) { ... print p ... };
// This will now print in preorder.
tree.traverse(process);

如何在深度优先函数中实现 lambda

How to implement a lambda within a depth first function

c++

lambda

binary-tree

c++17