fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Node{
  6. 	int data;
  7. 	int index;
  8. 	Node* left;
  9. 	Node* right;
  10. 	Node* parent;
  11. };
  12. bool cmpNode(const Node &x,const Node &y){
  13. 	return x.data < y.data;
  14. }
  15. void pre_order(Node* ptr){
  16. 	cout<< ptr->data <<' ';
  17. 	if(ptr->left)
  18. 		pre_order(ptr->left);
  19. 	if(ptr->right)
  20. 		pre_order(ptr->right);
  21. }
  22. int main(){
  23. 	int N;
  24. 	Node* nodes=NULL;
  25. 	Node* ptr=NULL;
  26. 	while(cin>>N){
  27. 		nodes=new Node[N];
  28. 		for(int i=0;i<N;++i){
  29. 			cin>>nodes[i].data;
  30. 			nodes[i].index=i;
  31. 			nodes[i].left=NULL;
  32. 			nodes[i].right=NULL;
  33. 			nodes[i].parent=NULL;
  34. 		}
  35. 		sort(nodes,nodes+N,cmpNode);
  36.         for(int i=1;i<N;++i){
  37.             if(nodes[i].index<nodes[i-1].index){
  38.                 if(nodes[i-1].parent){
  39.                     ptr=nodes[i-1].parent;
  40.                     bool done=false;
  41.                     while(ptr!=NULL){
  42.                         if(nodes[i].index < ptr->index){
  43. 							if(ptr->parent)
  44. 								ptr=ptr->parent;
  45. 							else break;
  46. 						}
  47.                         else{
  48.                             nodes[i].parent=ptr;
  49.                             nodes[i].left=ptr->right;
  50.                             ptr->right->parent=&nodes[i];
  51.                             ptr->right=&nodes[i];
  52.                             done=true;
  53.                             break;
  54.                         }
  55.                     }
  56.                     if(!done){
  57.                         nodes[i].left=ptr;
  58.                         ptr->parent=&nodes[i];
  59.                     }
  60.                 }
  61.                 else{
  62.                     nodes[i].left=&nodes[i-1];
  63.                     nodes[i-1].parent=&nodes[i];
  64.                 }
  65.             }
  66.             else{
  67. 				nodes[i-1].right=&nodes[i];
  68.                 nodes[i].parent=&nodes[i-1];
  69.             }
  70.         }
  71.         ptr=&nodes[0];
  72.         while(ptr->parent!=NULL)
  73.             ptr=ptr->parent;
  74.         pre_order(ptr);
  75. 		cout<<endl;
  76. 		delete[] nodes;
  77. 		nodes=NULL;
  78. 	}
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 3144KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4WpYMQ
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!