Как сделать обход BFS через двоичное дерево, используя шаблон проектирования Iterator - PullRequest
Новая
       30

Как сделать обход BFS через двоичное дерево, используя шаблон проектирования Iterator

0 голосов
/ 01 мая 2020

Я пытаюсь реализовать шаблон проектирования итератора в двоичном дереве для выполнения итеративного обхода 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->

Итак, согласно этому выводу первый является рекурсивным обходом преодера, второй - итеративным BFS, а последним может быть IteratorBFS ... но я немного запутался здесь ... Как изменить следующее значение?

TNKS !!!

1 Ответ

0 голосов
/ 02 мая 2020

Спасибо за комментарии, я смог решить проблему, Вот решение 

#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->
...