#include <iostream>  
using namespace std;  
typedef int Data;  
  
struct Node  
{  
    Node(Data d):data(d){left = right = NULL;};  
    Data data;  
    Node* left;  
    Node* right;  
};

struct ListNode
{
    ListNode(Node* n):data(n){next = NULL;};
    ListNode* next;
    Node* data;
};
  
class Tree  
{  
public:  
    Tree():root(NULL){};  
    Node* root;  
    void insert(Data data, Node* node = NULL)  
    {  
        if(root == NULL)  
        {  
            root = new Node(data);  
            return;  
        }  
        if(node == NULL) node = root;  
        if(data == node->data)  
        {  
            return;  
        } else if(data < node->data) {  
            if(node->left == NULL)  
                node->left = new Node(data);      
            else  
                insert(data, node->left);  
        } else {  
            if(node->right == NULL)  
                node->right = new Node(data);  
            else  
                insert(data, node->right);  
        }  
    };
    int depth(Node* node)
    {
        if(node == NULL)
            return 0;
        int left = depth(node->left);
        int right = depth(node->right);
        return (left>right?left:right) + 1;
    };
    void createList()
    {
        int height = depth(root);
        ListNode** ret = new ListNode*[height];
        ret[0] = new ListNode(root);
        for(int i=1; i<height; i++)
        {
            ret[i] = NULL;
            ListNode* p = ret[i-1];
            while(p != NULL)
            {
                if(p->data->left != NULL)
                {
                    ListNode* n = new ListNode(p->data->left);
                    n->next = ret[i];
                    ret[i] = n;
                }
                if(p->data->right != NULL)
                {
                    ListNode* n = new ListNode(p->data->right);
                    n->next = ret[i];
                    ret[i] = n;
                }
                p = p->next;
            }
        }
        for(int i=0; i<height; i++)
        {
            ListNode* p = ret[i];
            while(p != NULL)
            {
                cout<<p->data->data<<" ";
                p = p->next;
            }
            cout<<endl;
        }
    }
};  
  
int main()  
{  
    Tree tree;  
    tree.insert(5);  
    tree.insert(1);  
    tree.insert(7);  
    tree.insert(4);  
    tree.insert(3);
    tree.createList();
    system("pause");  
};