#include
     
      using namespace std;struct TreeNode{    int height;   //每一个结点都要保存自己的高度    int data;    TreeNode* leftC;    TreeNode* rightC;};//得到此时结点高度int getHeight(TreeNode* s){    if (s != NULL)    {        return s->height;    }    return -1;}//右旋void rightRotate(TreeNode*& root){    TreeNode *l1 = root;    TreeNode *l2 = root->leftC;    l1->leftC = l2->rightC;    l2->rightC = l1;    l1->height = (getHeight(l1->leftC) > getHeight(l1->rightC) ? getHeight(l1->leftC) : getHeight(l1->rightC)) + 1;    l2->height = (getHeight(l2->leftC) > getHeight(l2->rightC) ? getHeight(l2->leftC) : getHeight(l2->rightC)) + 1;    root = l2;}//左旋void leftRotate(TreeNode*& root){    TreeNode *l1 = root;    TreeNode *l2 = root->rightC;    l1->rightC = l2->leftC;    l2->leftC = l1;    l1->height = (getHeight(l1->leftC) > getHeight(l1->rightC) ? getHeight(l1->leftC) : getHeight(l1->rightC)) + 1;    l2->height = (getHeight(l2->leftC) > getHeight(l2->rightC) ? getHeight(l2->leftC) : getHeight(l2->rightC)) + 1;    root = l2;}//左右，先左旋，再右旋void DoubleRotateLR(TreeNode* &n1){    leftRotate(n1->leftC);    rightRotate(n1);}//右左，先右旋，后左旋void DoubleRotateRL(TreeNode* &n1){    rightRotate(n1->rightC);    leftRotate(n1);}void Insert(TreeNode** node, int data){    if (*node == NULL)    {        TreeNode* tmp = new TreeNode();        tmp->data = data;        tmp->height = 0;        tmp->leftC = NULL;        tmp->rightC = NULL;        *node = tmp;        return;    }    if ((*node)->data > data)//结点的值大于data    {        Insert(&((*node)->leftC), data);//不断插入        if ((getHeight((*node)->leftC) - getHeight((*node)->rightC)) == 2)        {//说明需要右旋            if (data < (*node)->leftC->data)            {                rightRotate(*node);            }            else            {                DoubleRotateLR(*node);            }        }    }    else if ((*node)->data < data)//没有相同的值    {        Insert(&((*node)->rightC), data);        //如果高度之差为2的话就失去了平衡,需要旋转        if (2 == getHeight((*node)->rightC) - getHeight((*node)->leftC))        {            if (data > (*node)->rightC->data)            {                leftRotate(*node);            }            else            {                DoubleRotateRL(*node);            }        }    }        (*node)->height = (getHeight((*node)->leftC) > getHeight((*node)->rightC) ? getHeight((*node)->leftC) : getHeight((*node)->rightC)) + 1;}void preOrder(TreeNode* node){    if (node == NULL)    {        return;    }    cout << node->data << " ";    preOrder(node->leftC);    preOrder(node->rightC);}void  inOrderTraversal(TreeNode* root){    if(root)    {    	inOrderTraversal(root->leftC);    	cout << root->data << " ";    	inOrderTraversal(root->rightC);    }}int main(){	int n;	cin>>n;	while(n-->0)	{	    int num;	    cin>>num;	    TreeNode *head=NULL;        int point;        for(int i=0;i
      
       >point;            Insert(&head, point);        }        preOrder(head);        cout<