如何使用迭代器设计模式在二叉树上进行BFS遍历？

Question

我试图在二叉树上实现迭代器设计模式，以执行迭代的BFS遍历，这是我做的。

#include <iostream>
#include <memory>
#include <queue>

template<class T>class Node {
private:
    T data = 0;
    std::shared_ptr<Node<T>> left_ptr = nullptr;
    std::shared_ptr<Node<T>> right_ptr = nullptr;

public:
    Node(T data = 0, std::shared_ptr<Node<T>> left_ptr = nullptr, std::shared_ptr<Node<T>> right_ptr = nullptr)
        : data(data), left_ptr(left_ptr), right_ptr(right_ptr)
    {
        // std::cout << "created " << data << "\n";
    }

    ~Node() {
        // std::cout << "deleted " << data << "\n";
    }

    T getData() {
        return data;
    }

    std::shared_ptr<Node<T>>& getLeftNode() {
        return left_ptr;
    }

    std::shared_ptr<Node<T>>& getRightNode() {
        return right_ptr;
    }
};

template<class T>class Tree {
private:
    std::shared_ptr<Node<T>> root = nullptr;

public:
    Tree()
        : root(nullptr)
    { /* empty */ }

    ~Tree() {
        trim(root);
    }

    void addNode(T value) {
        addNode(root, value);
    }

    void preorder() {
        if(!root) {
            std::cout << "preorder::The tree is empty\n";
        } else {
            preorder(root);

            std::cout << "\n";
        }
    }

    void bfs() {
        if(!root) {
            std::cout << "bfs::The tree is empty\n";
        } else {
            bfs(root);

            std::cout << "\n";
        }
    }

    class Iterator {
    private:
        std::shared_ptr<Node<T>> node;
        std::queue<std::shared_ptr<Node<T>>> q;

    public:
        Iterator(std::shared_ptr<Node<T>> node = nullptr)
            : node(node)
        {
            q.push(node);
        }

        Iterator(std::queue<std::shared_ptr<Node<T>>> q)
            : q(q)
        {

        }

        bool hasMore() {
            return !q.empty();
        }

        Iterator getNext() {
            if(!q.empty()) {
                std::shared_ptr<Node<T>> p = q.front();
                q.pop();

                if (p->getLeftNode()) {
                    q.push(p->getLeftNode());
                }

                if (p->getRightNode()) {
                    q.push(p->getRightNode());
                }
            }

            return Iterator(q);
        }

        T getData() {
            return node->getData();
        }
    };

    Iterator begin() const {
        return Iterator(root);
    }

private:
    void addNode(std::shared_ptr<Node<T>>& node, T value) {
        if(!node) {
            node = std::shared_ptr<Node<T>>(new Node<T>(value));
        } else {
            if(value < node->getData()) {
                addNode(node->getLeftNode(), value);
            } else if(value > node->getData()) {
                addNode(node->getRightNode(), value);
            } else {
                std::cout << "This tree does not admit duplicates\n";
            }
        }
    }

    void preorder(std::shared_ptr<Node<T>> node) {
        if(node) {
            std::cout << node->getData() << "->";
            preorder(node->getLeftNode());
            preorder(node->getRightNode());
        }
    }

    void bfs(std::shared_ptr<Node<T>> node) {
        // Base Case
        if (!node)  return;

        // Create an empty queue for level order tarversal
        std::queue<std::shared_ptr<Node<T>>> q;

        // Enqueue Root and initialize height
        q.push(root);

        while (!q.empty()) {
            // Print front of queue and remove it from queue
            std::shared_ptr<Node<T>> node = q.front();
            std::cout << node->getData() << "->";
            q.pop();

            if (node->getLeftNode()) {
                q.push(node->getLeftNode());
            }

            if (node->getRightNode()) {
                q.push(node->getRightNode());
            }
        }
    }

    void trim(std::shared_ptr<Node<T>> node) {
        if(node) {
            trim(node->getLeftNode());
            trim(node->getRightNode());
        }
    }
};

int main() {
    Tree<int> tree;

    tree.addNode(2);
    tree.addNode(1);
    tree.addNode(3);
    tree.addNode(4);
    tree.addNode(5);

    tree.preorder();
    tree.bfs();

    Tree<int>::Iterator it = tree.begin();

    while(it.hasMore()) {
        std::cout << it.getData() << "->";
        it.getNext();
    }

    std::cout << "\n";


    return 0;
}

输出

2->1->3->4->5->
2->1->3->4->5->
2->2->2->2->2->

所以，根据这个输出，第一个是递归preoder遍历，第二个是迭代BFS，最后一个应该是IteratorBFS......但是我这里有点困惑......怎么改到下一个值？

TNKS!!!

Answer 1

谢谢你的意见，我能够解决这个问题，以下是解决方案

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

template<class T>class Node {
private:
    T data = 0;
    std::shared_ptr<Node<T>> left_ptr = nullptr;
    std::shared_ptr<Node<T>> right_ptr = nullptr;

public:
    Node(T data = 0, std::shared_ptr<Node<T>> left_ptr = nullptr, std::shared_ptr<Node<T>> right_ptr = nullptr)
        : data(data), left_ptr(left_ptr), right_ptr(right_ptr)
    {
        // std::cout << "created " << data << "\n";
    }

    ~Node() {
        // std::cout << "deleted " << data << "\n";
    }

    T getData() {
        return data;
    }

    std::shared_ptr<Node<T>>& getLeftNode() {
        return left_ptr;
    }

    std::shared_ptr<Node<T>>& getRightNode() {
        return right_ptr;
    }
};

template<class T>class Tree {
private:
    std::shared_ptr<Node<T>> root = nullptr;

public:
    Tree()
        : root(nullptr)
    { /* empty */ }

    ~Tree() {
        trim(root);
    }

    void addNode(T value) {
        addNode(root, value);
    }

    void preorder() {
        if(!root) {
            std::cout << "preorder::The tree is empty\n";
        } else {
            preorder(root);

            std::cout << "\n";
        }
    }

    void bfs() {
        if(!root) {
            std::cout << "bfs::The tree is empty\n";
        } else {
            bfs(root);

            std::cout << "\n";
        }
    }

    class Iterator {
    private:
        std::queue<std::shared_ptr<Node<T>>> q;

    public:
        Iterator(std::shared_ptr<Node<T>> root) {
            std::shared_ptr<Node<T>> node = root;

            q.push(node);
        }

        std::shared_ptr<Node<T>> current() {
            return q.top();
        }

        void getNext() {
            std::shared_ptr<Node<T>> node = q.front();
            q.pop();

            if(node->getLeftNode()) {
                q.push(node->getLeftNode());
            }

            if(node->getRightNode()) {
                q.push(node->getRightNode());
            }
        }

        bool hasMore() {
            return !q.empty();
        }

        T getData() {
            return q.front()->getData();
        }
    };

    Iterator begin() {
        return Iterator(root);
    }

private:
    void addNode(std::shared_ptr<Node<T>>& node, T value) {
        if(!node) {
            node = std::shared_ptr<Node<T>>(new Node<T>(value));
        } else {
            if(value < node->getData()) {
                addNode(node->getLeftNode(), value);
            } else if(value > node->getData()) {
                addNode(node->getRightNode(), value);
            } else {
                std::cout << "This tree does not admit duplicates\n";
            }
        }
    }

    void preorder(std::shared_ptr<Node<T>> node) {
        if(node) {
            std::cout << node->getData() << "->";
            preorder(node->getLeftNode());
            preorder(node->getRightNode());
        }
    }

    void bfs(std::shared_ptr<Node<T>> node) {
        // Base Case
        if (!node)  return;

        // Create an empty queue for level order tarversal
        std::queue<std::shared_ptr<Node<T>>> q;

        // Enqueue Root and initialize height
        q.push(root);

        while (!q.empty()) {
            // Print front of queue and remove it from queue
            std::shared_ptr<Node<T>> node = q.front();
            std::cout << node->getData() << "->";
            q.pop();

            if (node->getLeftNode()) {
                q.push(node->getLeftNode());
            }

            if (node->getRightNode()) {
                q.push(node->getRightNode());
            }
        }
    }

    void trim(std::shared_ptr<Node<T>> node) {
        if(node) {
            trim(node->getLeftNode());
            trim(node->getRightNode());
        }
    }
};

int main() {
    Tree<int> tree;

    tree.addNode(5);
    tree.addNode(3);
    tree.addNode(7);
    tree.addNode(2);
    tree.addNode(4);
    tree.addNode(6);
    tree.addNode(8);

    tree.bfs();

    Tree<int>::Iterator it = tree.begin();

    while(it.hasMore()) {
        std::cout << it.getData() << "->";
        it.getNext();
    }

    std::cout << "\n";


    return 0;
}

产量

5->3->7->2->4->6->8->
5->3->7->2->4->6->8->