fork download
copy 
  1. /*
  2.  * Tree Sort
  3.  *
  4.  */
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <math.h>
  8.  
  9. #define SIZE (100)
  10.  
  11. struct _tree {
  12. 	struct _tree *less;
  13. 	struct _tree *more;
  14. 	int value;
  15. };
  16.  
  17. typedef struct _tree TREE;
  18.  
  19. TREE *addTreeValue(TREE *tree, int value);
  20. TREE *addTreeValues(TREE *tree, int *array, int offset, int size);
  21. TREE *newTree(int value);
  22. void releaseTree(TREE *tree);
  23. int getTreeSize(TREE *tree);
  24. int getTreeValues(TREE *tree, int *array, int offset, int size);
  25.  
  26. int main(void) {
  27. 	int  list[SIZE];
  28. 	int  i;
  29. 	int  c;
  30. 	TREE *tree;
  31.  
  32. 	for (i = 0; i < 20; i++)
  33. 		list[i] = rand() % 200;
  34.  
  35. 	tree = addTreeValues(NULL, list, 0, 20);
  36.  
  37. 	c = getTreeSize(tree);
  38.  
  39. 	if (c > SIZE) {
  40. 		c = SIZE;
  41. 	}
  42.  
  43. 	getTreeValues(tree, list, 0, c);
  44.  
  45. 	for (i = 0; i < c; i++) {
  46. 		printf("%d: %d\n", i, list[i]);
  47. 	}
  48.  
  49. 	releaseTree(tree);
  50.  
  51. 	return 0;
  52. }
  53.  
  54. TREE *addTreeValue(TREE *tree, int value) {
  55. 	if (tree == NULL) {
  56. 		return newTree(value);
  57. 	}
  58. 	if (tree->value < value) {
  59. 		tree->more = addTreeValue(tree->more, value);
  60. 	} else {
  61. 		tree->less = addTreeValue(tree->less, value);
  62. 	}
  63. 	return tree;
  64. }
  65.  
  66. TREE *addTreeValues(TREE *tree, int *array, int offset, int size) {
  67. 	int i;
  68. 	array += offset;
  69. 	for (i = 0 ; i < size; i++) {
  70. 		tree = addTreeValue(tree, *array);
  71. 		array++;
  72. 	}
  73. 	return tree;
  74. }
  75.  
  76. TREE *newTree(int value) {
  77. 	TREE *tree;
  78. 	tree = (TREE *)calloc(1, sizeof(TREE));
  79. 	tree->less = NULL;
  80. 	tree->more = NULL;
  81. 	tree->value = value;
  82. 	return tree;
  83. }
  84.  
  85. void releaseTree(TREE *tree) {
  86. 	if (tree == NULL) {
  87. 		return;
  88. 	}
  89. 	releaseTree(tree->less);
  90. 	releaseTree(tree->more);
  91. 	free(tree);
  92. }
  93.  
  94. int getTreeSize(TREE *tree) {
  95. 	int count = 1;
  96. 	if (tree == NULL) {
  97. 		return 0;
  98. 	}
  99. 	count += getTreeSize(tree->less);
  100. 	count += getTreeSize(tree->more);
  101. 	return count;
  102. }
  103.  
  104. int getTreeValues(TREE *tree, int *array, int offset, int size) {
  105. 	int count = 0;
  106. 	if ((tree == NULL) || (array == NULL)) {
  107. 		return 0;
  108. 	}
  109. 	count += getTreeValues(tree->less, array, offset, size);
  110. 	if (count >= size) {
  111. 		return count;
  112. 	}
  113. 	*(array + offset + count) = tree->value;
  114. 	count++;
  115. 	if (count >= size) {
  116. 		return count;
  117. 	}
  118. 	count += getTreeValues(tree->more, array, offset + count, size - count);
  119. 	return count;
  120. }
  121.  
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0: 21
1: 26
2: 27
3: 49
4: 59
5: 86
6: 90
7: 92
8: 115
9: 126
10: 135
11: 136
12: 140
13: 162
14: 163
15: 172
16: 177
17: 183
18: 186
19: 193
https://ideone.com/HLTirP
language:
C (gcc 8.3)
created:
11 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!