#include<vector>
#include<queue>
#include<string>
#include<binaryNode.hpp>
#include<iostream>
#include<sstream>
template<typename T>
class traverse {
public:
    using D = T::value_type;
    void print_tree() {
        std::queue<binaryNode<D>*>q;
        q.push(tree.root());
        while (!q.empty())
        {
            std::vector<binaryNode<D>*>vec;
            while (!q.empty()) { vec.push_back(q.front()); q.pop(); }
            std::string line = "                        ";
            for (auto i : vec)
            {
                auto temp = i;
                if (temp)
                {
                    for (auto j = 0; j < inorder_vec.size(); ++j)
                    {
                        if (inorder_vec[j] == temp)
                        {
                            std::string str;
                            put << temp->data;
                            put >> str;
                            put.clear();
                            line.insert(j, str);
                            break;
                        }
                    }
                    if (temp->lson) q.push(temp->lson);
                    if (temp->rson) q.push(temp->rson);
                }
            }
            std::cout << line << std::endl;
        }


    }
    traverse(T& tree) :tree(tree)
    {
        inorder_traverse(tree.root());
    }
private:
    T &tree;
    std::stringstream put;
    std::queue<binaryNode<D>*> q;
    std::vector<binaryNode<D>*>inorder_vec;
    void inorder_traverse(binaryNode<D>* node)
    {
        if (!node)return;
        inorder_traverse(node->lson);
        inorder_vec.push_back(node);
        inorder_traverse(node->rson);
    }



};