タイトル1503:二叉検索ツリーと双方向チェーンテーブル-九度

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct node{
    int val;
    node *left;
    node *right;
}node;
node * input_tree(){
	int tmp;
	scanf("%d",&tmp);
	if(0==tmp){
		return NULL;
	}
	node *new_node=new node;
	new_node->val=tmp;
	new_node->left=input_tree();
	new_node->right=input_tree();
	return new_node;
}

void tree_to_link(node *root){
	if(root!=NULL){
        node *p=root->left;
        while(p!=NULL&&p->right!=NULL){// find it pre
            p=p->right;
        }
        node *q=root->right;
        while(q!=NULL&&q->left!=NULL){// find it next
            q=q->left;
        }
        tree_to_link(root->left);//handle left
        tree_to_link(root->right);//handle right
        if(p!=NULL){//link
            p->right=root;
            root->left=p;
        }
        if(q!=NULL){//link
            q->left=root;
            root->right=q;
        }
	} 
}
int main()
{
	int n;
	scanf("%d",&n);
	while(n--){
		node *t=new node;
		scanf("%d",&t->val);
		
		t->left=input_tree();    
		t->right=input_tree();    
		node *lhead=t;
		while(lhead!=NULL&&lhead->left!=NULL){
            lhead=lhead->left;
		}
		tree_to_link(t);
		while(lhead!=NULL){
            printf("%d ",lhead->val);
            lhead=lhead->right;
		}
		printf("
");
	}
	return 0;
}