fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5. struct Node {
  6. 	int x;
  7. 	Node *l;
  8. 	Node *r;
  9. 	Node(int value=0, Node* left=NULL, Node* right=NULL) : x(value), l(left), r(right) {}
  10. };
  11.  
  12. void print_binary_tree(Node* node, int depth=0){
  13. 	if(!node)	return;
  14. 	print_binary_tree(node->r, depth+1);
  15. 	string str = "";
  16. 	for(int i=0; i<depth; i++)
  17. 		cout<<"|\t";
  18. 	cout<<node->x<<endl;
  19. 	print_binary_tree(node->l, depth+1);
  20. 	return;
  21. }
  22. void insert(Node* &root, Node* node){
  23.     if(!root)   root = node;
  24.     else insert(node->x<root->x?root->l:root->r, node);
  25. }
  26. Node* preorderd_to_bst(const vector<int> &v){
  27. 	Node* root = NULL;
  28. 	for(int x: v)
  29.         insert(root,new Node(x));
  30.     return root;
  31. }
  32. vector<int> bst_to_preorder(Node* root){
  33. 	stack<Node*> h;
  34. 	Node* node;
  35. 	h.push(root);
  36. 	vector<int> v;
  37. 	while(!h.empty()){
  38. 		node = h.top();
  39. 		h.pop();
  40. 		if(!node)	continue;
  41. 		v.push_back(node->x);
  42. 		h.push(node->r);
  43. 		h.push(node->l);
  44. 	}
  45. 	return v;
  46. }
  47. void random_run(int n = 100){
  48. 	Node* root = NULL;
  49. 	while(n--)
  50.         insert(root,new Node(rand()%1000));
  51. 	cout<<"Original Tree"<<endl;
  52. 	print_binary_tree(root);
  53. 	cout<<endl;
  54. 	vector<int> preorder = bst_to_preorder(root);
  55. 	cout<<"Preorder Traversal"<<endl;
  56. 	for(int x: preorder)
  57. 		cout<<x<<' ';
  58. 	cout<<endl<<endl;
  59. 	root = preorderd_to_bst(preorder);
  60. 	cout<<"Answer Tree"<<endl;
  61. 	print_binary_tree(root);
  62. 	cout<<endl;
  63. }
  64. int main() {
  65. 	int t,n,x;
  66. 	Node* root;
  67. 	vector<int> v;
  68. 	cin>>t;
  69. 	while(t--){
  70. 		cin>>n;
  71. 		v.clear();
  72. 		while(n--&&cin>>x)	v.push_back(x);
  73. 		root = preorderd_to_bst(v);
  74. 		print_binary_tree(root);
  75. 		cout<<endl;
  76. 	}
  77. 	random_run();
  78. 	return 0;
  79. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
1
6
8 5 1 7 10 12
stdout
copy 
|	|	12
|	10
8
|	|	7
|	5
|	|	1

Original Tree
|	|	|	|	|	|	996
|	|	|	|	|	980
|	|	|	|	|	|	956
|	|	|	|	|	|	|	932
|	|	|	|	929
|	|	|	926
|	|	|	|	|	925
|	|	|	|	919
|	|	915
|	|	|	895
|	886
|	|	|	|	|	873
|	|	|	|	|	|	862
|	|	|	|	862
|	|	|	|	|	|	|	857
|	|	|	|	|	|	846
|	|	|	|	|	|	|	814
|	|	|	|	|	|	|	|	808
|	|	|	|	|	802
|	|	|	793
|	|	|	|	|	|	788
|	|	|	|	|	784
|	|	|	|	782
|	|	777
|	|	|	|	|	|	|	763
|	|	|	|	|	|	|	|	|	|	754
|	|	|	|	|	|	|	|	|	750
|	|	|	|	|	|	|	|	|	|	739
|	|	|	|	|	|	|	|	736
|	|	|	|	|	|	|	|	|	729
|	|	|	|	|	|	690
|	|	|	|	|	|	|	|	676
|	|	|	|	|	|	|	651
|	|	|	|	|	649
|	|	|	|	|	|	|	|	|	|	586
|	|	|	|	|	|	|	|	|	584
|	|	|	|	|	|	|	|	582
|	|	|	|	|	|	|	567
|	|	|	|	|	|	|	|	545
|	|	|	|	|	|	540
|	|	|	|	|	|	|	|	|	539
|	|	|	|	|	|	|	|	537
|	|	|	|	|	|	|	530
|	|	|	|	|	|	|	|	526
|	|	|	|	|	|	|	|	|	505
|	|	|	|	492
|	|	|	|	|	|	|	|	456
|	|	|	|	|	|	|	|	|	434
|	|	|	|	|	|	|	429
|	|	|	|	|	|	426
|	|	|	|	|	|	|	421
|	|	|	|	|	421
|	|	|	|	|	|	|	413
|	|	|	|	|	|	|	|	403
|	|	|	|	|	|	|	|	|	399
|	|	|	|	|	|	393
|	|	|	386
383
|	|	|	|	373
|	|	|	|	|	370
|	|	|	|	|	|	368
|	|	|	368
|	|	|	|	367
|	|	|	|	|	364
|	|	362
|	|	|	336
|	335
|	|	|	|	|	|	|	|	327
|	|	|	|	|	|	|	324
|	|	|	|	|	|	|	|	315
|	|	|	|	|	|	|	|	|	|	|	313
|	|	|	|	|	|	|	|	|	|	305
|	|	|	|	|	|	|	|	|	281
|	|	|	|	|	|	|	|	|	|	276
|	|	|	|	|	|	229
|	|	|	|	|	|	|	226
|	|	|	|	|	211
|	|	|	|	|	|	198
|	|	|	|	|	|	|	178
|	|	|	|	172
|	|	|	|	|	|	|	|	170
|	|	|	|	|	|	|	167
|	|	|	|	|	|	135
|	|	|	|	|	|	|	124
|	|	|	|	|	123
|	|	|	|	|	|	|	|	|	94
|	|	|	|	|	|	|	|	91
|	|	|	|	|	|	|	|	|	|	87
|	|	|	|	|	|	|	|	|	84
|	|	|	|	|	|	|	69
|	|	|	|	|	|	67
|	|	|	|	|	|	|	60
|	|	|	59
|	|	|	|	58
|	|	|	|	|	|	43
|	|	|	|	|	42
|	|	27
|	|	|	22
|	|	|	|	|	12
|	|	|	|	11

Preorder Traversal
383 335 27 22 11 12 59 58 42 43 172 123 67 60 69 91 84 87 94 135 124 167 170 211 198 178 229 226 324 315 281 276 305 313 327 362 336 368 367 364 373 370 368 886 777 386 492 421 393 413 403 399 426 421 429 456 434 649 540 530 526 505 537 539 567 545 582 584 586 690 651 676 763 736 729 750 739 754 793 782 784 788 862 802 846 814 808 857 873 862 915 895 926 919 925 929 980 956 932 996 

Answer Tree
|	|	|	|	|	|	996
|	|	|	|	|	980
|	|	|	|	|	|	956
|	|	|	|	|	|	|	932
|	|	|	|	929
|	|	|	926
|	|	|	|	|	925
|	|	|	|	919
|	|	915
|	|	|	895
|	886
|	|	|	|	|	873
|	|	|	|	|	|	862
|	|	|	|	862
|	|	|	|	|	|	|	857
|	|	|	|	|	|	846
|	|	|	|	|	|	|	814
|	|	|	|	|	|	|	|	808
|	|	|	|	|	802
|	|	|	793
|	|	|	|	|	|	788
|	|	|	|	|	784
|	|	|	|	782
|	|	777
|	|	|	|	|	|	|	763
|	|	|	|	|	|	|	|	|	|	754
|	|	|	|	|	|	|	|	|	750
|	|	|	|	|	|	|	|	|	|	739
|	|	|	|	|	|	|	|	736
|	|	|	|	|	|	|	|	|	729
|	|	|	|	|	|	690
|	|	|	|	|	|	|	|	676
|	|	|	|	|	|	|	651
|	|	|	|	|	649
|	|	|	|	|	|	|	|	|	|	586
|	|	|	|	|	|	|	|	|	584
|	|	|	|	|	|	|	|	582
|	|	|	|	|	|	|	567
|	|	|	|	|	|	|	|	545
|	|	|	|	|	|	540
|	|	|	|	|	|	|	|	|	539
|	|	|	|	|	|	|	|	537
|	|	|	|	|	|	|	530
|	|	|	|	|	|	|	|	526
|	|	|	|	|	|	|	|	|	505
|	|	|	|	492
|	|	|	|	|	|	|	|	456
|	|	|	|	|	|	|	|	|	434
|	|	|	|	|	|	|	429
|	|	|	|	|	|	426
|	|	|	|	|	|	|	421
|	|	|	|	|	421
|	|	|	|	|	|	|	413
|	|	|	|	|	|	|	|	403
|	|	|	|	|	|	|	|	|	399
|	|	|	|	|	|	393
|	|	|	386
383
|	|	|	|	373
|	|	|	|	|	370
|	|	|	|	|	|	368
|	|	|	368
|	|	|	|	367
|	|	|	|	|	364
|	|	362
|	|	|	336
|	335
|	|	|	|	|	|	|	|	327
|	|	|	|	|	|	|	324
|	|	|	|	|	|	|	|	315
|	|	|	|	|	|	|	|	|	|	|	313
|	|	|	|	|	|	|	|	|	|	305
|	|	|	|	|	|	|	|	|	281
|	|	|	|	|	|	|	|	|	|	276
|	|	|	|	|	|	229
|	|	|	|	|	|	|	226
|	|	|	|	|	211
|	|	|	|	|	|	198
|	|	|	|	|	|	|	178
|	|	|	|	172
|	|	|	|	|	|	|	|	170
|	|	|	|	|	|	|	167
|	|	|	|	|	|	135
|	|	|	|	|	|	|	124
|	|	|	|	|	123
|	|	|	|	|	|	|	|	|	94
|	|	|	|	|	|	|	|	91
|	|	|	|	|	|	|	|	|	|	87
|	|	|	|	|	|	|	|	|	84
|	|	|	|	|	|	|	69
|	|	|	|	|	|	67
|	|	|	|	|	|	|	60
|	|	|	59
|	|	|	|	58
|	|	|	|	|	|	43
|	|	|	|	|	42
|	|	27
|	|	|	22
|	|	|	|	|	12
|	|	|	|	11
https://ideone.com/2RJPNA
preorder traversal to tree
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!