I'm trying to implement the iterator design pattern on a binary tree to perform an iterative BFS traversal, this is what I've done:
#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;
}
Output
2->1->3->4->5->
2->1->3->4->5->
2->2->2->2->2->
So, acording to this output the first one is a recursive preoder traversal, the second one is iterative BFS and the last one sould be the IteratorBFS... but I'm a litte bit confused here... how to change the to the next value?
TNKS!!!
Aucun commentaire:
Enregistrer un commentaire