fork(1) download
copy 
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <ctime>
  4. #include <cstdlib>
  5. #include <stdio.h>
  6. using namespace std;
  7.  
  8. #define SIZE 70000
  9.  
  10. typedef struct node{
  11. 	int data;
  12. 	node *left;
  13. 	node *right;
  14. 	node *parent;
  15. } node;
  16.  
  17. struct node * CreateTree(void){
  18. 	struct node *root;
  19.  
  20. 	root = (struct node *)malloc(sizeof(struct node));
  21. 	root->data = NULL;
  22. 	root->parent = NULL;
  23. 	root->left = NULL;
  24. 	root->right = NULL;
  25. 	return root;
  26. }
  27.  
  28. struct node * CreateNode(int data){
  29. 	struct node *p = (struct node *)malloc(sizeof(struct node));
  30.  
  31. 	p->data = data;
  32. 	p->left = NULL;
  33. 	p->right = NULL;
  34. 	p->parent = NULL;
  35. 	return p;
  36. }
  37.  
  38. void TreeDestroy(struct node *root){
  39. 	if(root){
  40. 		TreeDestroy(root->left);
  41. 		TreeDestroy(root->right);
  42. 		free(root);
  43. 	}
  44. }
  45.  
  46. void TreeInsert(struct node *root, struct node *z){
  47. 	struct node *y = NULL;
  48. 	struct node *x = root;
  49.  
  50. 	while(x != NULL){
  51. 		y = x;
  52. 		if(z->data < x->data)
  53. 			x = x->left;
  54. 		else
  55. 			x = x->right;
  56. 	}
  57. 	z->parent = y;
  58. 	if(y == NULL)
  59. 		root = z;
  60. 	else{
  61. 		if(z->data < y->data)
  62. 			y->left = z;
  63. 		else
  64. 			y->right = z;
  65. 	}
  66. }
  67.  
  68. void genOrderedSeq(int *array){
  69. 	for(int i = 0; i < SIZE; i++)
  70. 		array[i] = i;
  71. }
  72.  
  73. void genRandSeq(int *array){
  74. 	std::srand(std::time(0));
  75. 	for(int i = 0; i < SIZE; i++)
  76. 		array[i] = std::rand();
  77. }
  78.  
  79. //Генерация инвертированной последовательности (по убыванию)
  80. void genInvertedSeq(int *array){
  81. 	for(int i = SIZE; i > 0; i--)
  82. 		array[SIZE-i] = i;
  83. }
  84.  
  85. /*Высота дерева*/
  86. int height(struct node *p){
  87.         struct node *temp = p;
  88.         int h1 = 0,h2 = 0;
  89.  
  90.         if(p == NULL) return 0;
  91.         if(p->left){h1=height(p->left);}
  92.         if(p->right){h2=height(p->right);}
  93.         return(std::max(h1,h2)+1);
  94. }
  95.  
  96. int main(){
  97. 	int seq[SIZE];
  98. 	struct node *tree;
  99. 	struct node *tmp;
  100.  
  101. 	/*Случайная последовательность*/
  102. 	genRandSeq(seq);
  103. 	std::cout << "*** Random Sequence ***" << std::endl;
  104. 	tree = CreateTree();
  105. 		for(int i = 0; i < SIZE; i++){
  106. 			tmp = CreateNode(seq[i]);
  107. 			TreeInsert(tree, tmp);
  108. 		}
  109. 	TreeDestroy(tree);
  110.  
  111. 	/*Упорядоченная последовательность*/
  112. 	genOrderedSeq(seq);
  113. 	std::cout << "*** Ordered Sequence ***" << std::endl;
  114. 	tree = CreateTree();
  115. 		for(int i = 0; i < SIZE; i++){
  116. 			tmp = CreateNode(seq[i]);
  117. 			TreeInsert(tree, tmp);
  118. 		}
  119. 	printf("tree height: %d", height(tree));
  120. 	TreeDestroy(tree);
  121.  
  122. 	/*Инвертированная последовательность*/
  123. 	genInvertedSeq(seq);
  124. 	std::cout << "*** Inverted Sequence ***" << std::endl;
  125. 	tree = CreateTree();
  126. 		for(int i = 0; i < SIZE; i++){
  127. 			tmp = CreateNode(seq[i]);
  128. 			TreeInsert(tree, tmp);
  129. 		}
  130. 	printf("tree height: %d", height(tree));
  131. 	TreeDestroy(tree);
  132.  
  133. }
Time limit exceeded #stdin #stdout 5s 5200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
*** Random Sequence ***
*** Ordered Sequence ***
https://ideone.com/kpJezs
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!