Реализация дерева поиска список сыновей

#include <iostream>
#include <list>
using namespace std;
 
template<typename T> 
struct Node
{
T key;
Node *left_;
Node *right_;
Node *parent_;
Node *root_;
Node(const T& key_)
:key(key_), left_(nullptr), right_(nullptr)
{root_=this; parent_=this;}
Node(const T& key_, Node *root)
:key(key_), root_(root), left_(nullptr), right_(nullptr), parent_(nullptr)
{}
 
Node (const Node & rhs)
:key(rhs.key), root_(rhs.root_), left_(rhs.left_), right_(rhs.right_), parent_(rhs.parent_)
{}
 
void insert( Node *x,  Node *z){            // x — корень поддерева, z — вставляемый элемент
    
    while (x != nullptr){
     if (z->key >= x->key)
        if (x->right_ != nullptr)
           x = x->right_;
        else{
           z->parent_ = x;
           x->right_ = z;
           break;
        }
     else if (z->key < x->key)
        if (x->left_ != nullptr)
           x = x->left_;
        else{
           z->parent_ = x;
           x->left_ = z;
           break;
        }
    }
}
void add(Node *x, T key){
 
    if(root_==nullptr){
        root_=new Node(key);
root_->root_=this;
root_->parent_=this; 
    }
else
{
Node *y=new Node(key, root_);
 
insert( x, y );
}
}
void add(T key){
    if(root_==nullptr){ root_=new Node(key);
        root_->root_=this;
root_->parent_=this; 
    }
else{
Node *y=new Node(key, root_);
insert( root_, y );
}
}
void inorderTraversal(Node *x){
    if (x != nullptr){
      inorderTraversal(x->left_);
      cout << x->key<<' ';
      inorderTraversal(x->right_);
    }
}
 
void inorderTraversal(Node *x, list<list<Node *>>& lst){
    if (x != nullptr){
     inorderTraversal(x->left_, lst);      
     list<Node *> lint;
     lint.push_back(x);
     lst.push_back(lint);
     inorderTraversal(x->right_, lst);
    }
}
 
void 
get_next_level_nodes_list( 
    list<list<Node*>>& list_nodes_by_levels, int level=0    
        ){
    list<list<Node*>>::const_iterator it_begin =  list_nodes_by_levels.begin(), it_last =  list_nodes_by_levels.end();
    if(it_last == it_begin){
    cout<<"The tree is empty"<<endl;
    return;
    }
    it_last--;
    list<Node*> list_nodes_next_level;
    list<Node*>::const_iterator it=it_last->begin(), it_fin = it_last->end();
    cout<<level<<'\t';
    for(; it  != it_fin; ++it){
    cout<<(*it)->key<<' ';
    if((*it)->left_)
    list_nodes_next_level.push_back((*it)->left_);
    if((*it)->right_)
    list_nodes_next_level.push_back((*it)->right_);
    }
    cout<<endl;
    if(!list_nodes_next_level.empty()){
    list_nodes_by_levels.push_back(list_nodes_next_level);
    get_next_level_nodes_list( list_nodes_by_levels, ++level); 
    }
}
 
};
int main(int argc, char* argv[])
{
const int sz=7;
 
int a[sz]={2,6,1,3,5,7};
Node<int> *node_root=new Node<int>(4);
 
for(int i=0; i<sz-1; ++i)node_root->add(node_root, a[i] );
cout<<endl;
node_root->inorderTraversal(node_root);
cout<<endl;
cout<<"\nlevels of the tree:\n";
list<Node<int>*> list_nodes_next_level;
list_nodes_next_level.push_back(node_root->root_);
list<list<Node<int>*>> list_nodes_by_levels;
list_nodes_by_levels.push_back(list_nodes_next_level);
node_root->get_next_level_nodes_list(list_nodes_by_levels);
 
//вот ваше задание Bonttpol
typedef list<Node<int>*> level_lists;
 
list<level_lists> sones_list; 
cout<<"\nInorderTraversalNextNode\n";
list<level_lists> root_list;
node_root->inorderTraversal(node_root, root_list);
list<level_lists>::iterator root_list_it_ben = root_list.begin(), 
root_list_it_end = root_list.end();
for(;root_list_it_ben  != root_list_it_end ; ++root_list_it_ben){
Node<int> *nod=(*root_list_it_ben->begin());
cout << nod->key << ' ';
if(nod->left_)root_list_it_ben->push_back(nod->left_);
if(nod->right_)root_list_it_ben->push_back(nod->right_);
}
cout<<"\n\nSones list\n";
root_list_it_ben = root_list.begin();
cout<<endl;
for(;root_list_it_ben  != root_list_it_end ; ++root_list_it_ben){
    level_lists::iterator level_lists_beg=root_list_it_ben->begin(),
        level_lists_end=root_list_it_ben->end();
for(;level_lists_beg  != level_lists_end ; ++level_lists_beg){
Node<int> *nod=*level_lists_beg;
cout << nod->key << ' ';
}
cout<<endl;
}
 
cout<<endl;
system("pause");
return 0;
}

    typedef Node* NodePtr;
    typedef list<NodePtr> NodePtrLst;
    typedef list<NodePtrLst> list_lists;
    typedef typename list_lists::iterator list_lists_it;//почему он без typename не может вывести тип - загадка для меня :D
    list_lists_it it_begin =  list_nodes_by_levels.begin();
    list_lists_it it_last =  list_nodes_by_levels.end();
    //auto it_begin =  list_nodes_by_levels.begin(), it_last =  list_nodes_by_levels.end();//так тоже работает

#include "pch.h"
#include <iostream>
#include <list>
 
using namespace std;
 
template<typename T>
 
struct Node
{
    T key;
    Node *left_;
    Node *right_;
    Node *parent_;
    Node *root_;
 
    Node(const T& key_)
        :key(key_), left_(nullptr), right_(nullptr)
    {
        root_ = this; parent_ = this;
    }
    Node(const T& key_, Node *root)
        :key(key_), root_(root), left_(nullptr), right_(nullptr), parent_(nullptr)
    {}
 
    Node(const Node & rhs)
        :key(rhs.key), root_(rhs.root_), left_(rhs.left_), right_(rhs.right_), parent_(rhs.parent_)
    {}
 
    void insert(Node *x, Node *z) {            // x — корень поддерева, z — вставляемый элемент
 
        while (x != nullptr) {
            if (z->key >= x->key)
                if (x->right_ != nullptr)
                    x = x->right_;
                else {
                    z->parent_ = x;
                    x->right_ = z;
                    break;
                }
            else if (z->key < x->key)
                if (x->left_ != nullptr)
                    x = x->left_;
                else {
                    z->parent_ = x;
                    x->left_ = z;
                    break;
                }
        }
    }
    void add(Node *x, T key) {
 
        if (root_ == nullptr) {
            root_ = new Node(key);
            root_->root_ = this;
            root_->parent_ = this;
        }
        else
        {
            Node *y = new Node(key, root_);
 
            insert(x, y);
        }
    }
 
    void add(T key) {
        if (root_ == nullptr) {
            root_ = new Node(key);
            root_->root_ = this;
            root_->parent_ = this;
        }
        else {
            Node *y = new Node(key, root_);
            insert(root_, y);
        }
    }
 
    void inorderTraversal(Node *x) {
        if (x != nullptr) {
            inorderTraversal(x->left_);
            cout << x->key << ' ';
            inorderTraversal(x->right_);
        }
    }
 
    void preorderTraversal(Node *x) {
        if (x != nullptr) {
            cout << x->key << ' ';
            preorderTraversal(x->left_);
            preorderTraversal(x->right_);
        }
    }
 
    void postorderTraversal(Node *x) {      
        if (x != nullptr) {
            cout << x->key << ' ';
            postorderTraversal(x->left_);
            postorderTraversal(x->right_);
        }
    }
 
    void get_next_level_nodes_list(list<list<Node*>>& list_nodes_by_levels) {
        auto it_begin = list_nodes_by_levels.begin(), it_last = list_nodes_by_levels.end();
        if (it_last == it_begin) {
            cout << "The tree is empty" << endl;
            return;
        }
        it_last--;
        list<Node*> list_nodes_next_level;
        auto it = it_last->begin(), it_fin = it_last->end();
        for (; it != it_fin; ++it) {
            list<Node*> this_children;
            if ((*it)->left_)
            { 
                list_nodes_next_level.push_back((*it)->left_);
                this_children.push_back((*it)->left_);
            }
            if ((*it)->right_)
            {
                list_nodes_next_level.push_back((*it)->right_);
                this_children.push_back((*it)->right_);
            }
            list_nodes_by_levels.push_back(this_children);
            this_children.clear();
            get_next_level_nodes_list(list_nodes_by_levels);
        }
        cout << endl;
        if (!list_nodes_next_level.empty()) {
            get_next_level_nodes_list(list_nodes_by_levels);
        }
    }
};
 
int main(int argc, char* argv[])
{
    cout << "How match nodes: ";
    cin >> sz;
    int *a = new int[sz];
    cout << "Node's key: " << endl;
    for (int i = 0; i < sz; ++i) cin >> a[i];
 
    Node<int> *node_root = new Node<int>(a[0]);
 
    for (int i = 1; i < sz; ++i) node_root->add(node_root, a[i]);
    cout << endl << "Tree:" << endl;
    A_root->preorderTraversal(node_root);
    cout << endl;
    delete a;
 
    list<Node<int>*> list_nodes_next_level;
    list_nodes_next_level.push_back(node_root->root_);
    list<list<Node<int>*>> list_nodes_by_levels;
    list_nodes_by_levels.push_back(list_nodes_next_level);
    node_root->get_next_level_nodes_list(list_nodes_by_levels);
    list<list<Node<int>*>> list_node = list_nodes_by_levels;
    list_nodes_by_levels.clear();
 
    cout << endl;
    system("pause");
    return 0;
}

    size_t sz;///////////////////////////////////////// надо объявить
    cout << "How match nodes: ";
    cin >> sz;
    int *a = new int[sz];
    cout << "Node's key: " << endl;
    for (int i = 0; i < sz; ++i) cin >> a[i];
 
    Node<int> *node_root = new Node<int>(a[0]);
 
    for (int i = 1; i < sz; ++i) node_root->add(node_root, a[i]);
    cout << endl << "Tree:" << endl;
    node_root->preorderTraversal(node_root);//////////////////////A_root