fork download 
  1. /* coding by Leonardone @ NEETSDKASU */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. typedef struct _node {
  6. 	struct _node *left;
  7. 	struct _node *right;
  8. 	int value;
  9. } Node, *LPNode;
  10.  
  11. LPNode newNode(int value);
  12. void releaseNode(LPNode node);
  13. LPNode addNode(LPNode root, LPNode node);
  14. int nodeDepth(LPNode node);
  15. void calcDepth(LPNode node);
  16. LPNode rotateR(LPNode node);
  17. LPNode rotateL(LPNode node);
  18.  
  19. int iMax(int a, int b);
  20.  
  21. void seek(LPNode node) {
  22. 	if (node == NULL) {
  23. 		return;
  24. 	}
  25. 	printf("depth=%d, value=%d, left=%d, right=%d\n"
  26. 		, nodeDepth(node), node->value
  27. 		, nodeDepth(node->left), nodeDepth(node->right));
  28. 	printf("L[%d][%d]\n", nodeDepth(node), node->value);
  29. 	seek(node->left);
  30. 	printf("R[%d][%d]\n", nodeDepth(node), node->value);
  31. 	seek(node->right);
  32. }
  33.  
  34. void n2bt(LPNode node, int *(*p), int i) {
  35. 	if (node == NULL || p == NULL) {
  36. 		return;
  37. 	}
  38. 	p[i] = &node->value;
  39. 	n2bt(node->left, p, (i << 1) + 1);
  40. 	n2bt(node->right, p, (i << 1) + 2);
  41. }
  42.  
  43. void space(int n) {
  44. 	while (n-- > 0) {
  45. 		putchar(' ');
  46. 	}
  47. }
  48.  
  49. void printTree(LPNode node) {
  50. 	int *(*a);
  51. 	int i, j, k;
  52. 	if (node == NULL) {
  53. 		return;
  54. 	}
  55. 	puts("----------------------------------");
  56. 	a = (int*(*))calloc(1 << nodeDepth(node), sizeof(int*));
  57. 	n2bt(node, a, 0);
  58. 	k = 0;
  59. 	for (i = 0; i < nodeDepth(node); i++) {
  60. 		space(2 * (nodeDepth(node) - i));
  61. 		for (j = 0; j < (1 << i); j++) {
  62. 			if (a[k] != NULL) {
  63. 				printf("%2d", *a[k]);
  64. 			} else {
  65. 				printf("--");
  66. 			}
  67. 			space(2 * (nodeDepth(node) - i));
  68. 			k++;
  69. 		}
  70. 		putchar('\n');
  71. 	}
  72. 	free(a);
  73. }
  74.  
  75. int main(void) {
  76.  
  77. 	LPNode root = NULL;
  78.  
  79. 	root = addNode(root, newNode(5)); printTree(root);
  80. 	root = addNode(root, newNode(6)); printTree(root);
  81. 	root = addNode(root, newNode(9)); printTree(root);
  82. 	root = addNode(root, newNode(13)); printTree(root);
  83. 	root = addNode(root, newNode(11)); printTree(root);
  84. 	root = addNode(root, newNode(19)); printTree(root);
  85. 	root = addNode(root, newNode(7)); printTree(root);
  86. 	root = addNode(root, newNode(10)); printTree(root);
  87. 	root = addNode(root, newNode(8)); printTree(root);
  88. 	root = addNode(root, newNode(14)); printTree(root);
  89. 	root = addNode(root, newNode(4)); printTree(root);
  90. 	root = addNode(root, newNode(3)); printTree(root);
  91. 	root = addNode(root, newNode(16)); printTree(root);
  92. 	root = addNode(root, newNode(15)); printTree(root);
  93. 	root = addNode(root, newNode(2)); printTree(root);
  94. 	root = addNode(root, newNode(12)); printTree(root);
  95.  
  96. 	puts("----------------------------------");
  97.  
  98. 	seek(root);
  99.  
  100. 	releaseNode(root);
  101.  
  102. 	return 0;
  103. }
  104.  
  105.  
  106. int iMax(int a, int b) {
  107. 	return (a > b) ? a : b;
  108. }
  109.  
  110. LPNode newNode(int value) {
  111. 	LPNode node = (LPNode)malloc(sizeof(Node));
  112. 	node->left = NULL;
  113. 	node->right = NULL;
  114. 	node->value = value;
  115. 	return node;
  116. }
  117.  
  118. void releaseNode(LPNode node) {
  119. 	if (node == NULL) {
  120. 		return;
  121. 	}
  122. 	if (node->left != NULL) {
  123. 		releaseNode(node->left);
  124. 		node->left = NULL;
  125. 	}
  126. 	if (node->right != NULL) {
  127. 		releaseNode(node->right);
  128. 		node->right = NULL;
  129. 	}
  130. 	free(node);
  131. }
  132.  
  133. int nodeDepth(LPNode node) {
  134. 	if (node != NULL) {
  135. 		return iMax(nodeDepth(node->left), nodeDepth(node->right)) + 1;
  136. 	} else {
  137. 		return 0;
  138. 	}
  139. }
  140.  
  141. LPNode rotateR(LPNode node) {
  142. 	LPNode temp1, temp2;
  143. 	if (node == NULL || node->right == NULL) {
  144. 		return node;
  145. 	}
  146. 	temp1 = node->right;
  147. 	if (nodeDepth(temp1->left) > nodeDepth(temp1->right)) {
  148. 		temp2 = temp1->left;
  149. 		node->right = temp2->left;
  150. 		temp1->left = temp2->right;
  151. 		temp2->left = node;
  152. 		temp2->right = temp1;
  153. 		return temp2;
  154. 	} else {
  155. 		node->right = temp1->left;
  156. 		temp1->left = node;
  157. 		return temp1;
  158. 	}
  159. }
  160.  
  161. LPNode rotateL(LPNode node) {
  162. 	LPNode temp1, temp2;
  163. 	if (node == NULL || node->left == NULL) {
  164. 		return node;
  165. 	}
  166. 	temp1 = node->left;
  167. 	if (nodeDepth(temp1->left) > nodeDepth(temp1->right)) {
  168. 		node->left = temp1->right;
  169. 		temp1->right = node;
  170. 		return temp1;
  171. 	} else {
  172. 		temp2 = temp1->right;
  173. 		temp1->right = temp2->left;
  174. 		node->left = temp2->right;
  175. 		temp2->left = temp1;
  176. 		temp2->right = node;
  177. 		return temp2;
  178. 	}
  179. }
  180.  
  181. LPNode addNode(LPNode root, LPNode node) {
  182. 	LPNode temp;
  183. 	int diff, dl, dr;
  184. 	if (root == NULL) {
  185. 		return node;
  186. 	}
  187. 	if (node == NULL) {
  188. 		return root;
  189. 	}
  190. 	if (node->value <= root->value) {
  191. 		root->left = addNode(root->left, node);
  192. 	} else {
  193. 		root->right = addNode(root->right, node);
  194. 	}
  195. 	dl = nodeDepth(root->left);
  196. 	dr = nodeDepth(root->right);
  197. 	diff = dl - dr;
  198. 	if (diff < -1) {
  199. 		root = rotateR(root);
  200. 	} else if (diff > 1) {
  201. 		root = rotateL(root);
  202. 	}
  203. 	return root;
  204. }
  205.  
  206.  
  207.  
  208.  
Success #stdin #stdout 0s 2144KB
comments (?)
stdin 
Standard input is empty
stdout 
----------------------------------
   5  
----------------------------------
     5    
  --   6  
----------------------------------
     6    
   5   9  
----------------------------------
       6      
     5     9    
  --  --  --  13  
----------------------------------
       6      
     5    11    
  --  --   9  13  
----------------------------------
      11      
     6    13    
   5   9  --  19  
----------------------------------
        11        
       6      13      
     5     9    --    19    
  --  --   7  --  --  --  --  --  
----------------------------------
        11        
       6      13      
     5     9    --    19    
  --  --   7  10  --  --  --  --  
----------------------------------
        11        
       7      13      
     6     9    --    19    
   5  --   8  10  --  --  --  --  
----------------------------------
        11        
       7      14      
     6     9    13    19    
   5  --   8  10  --  --  --  --  
----------------------------------
        11        
       7      14      
     5     9    13    19    
   4   6   8  10  --  --  --  --  
----------------------------------
         7        
       5      11      
     4     6     9    14    
   3  --  --  --   8  10  13  19  
----------------------------------
           7          
         5        11        
       4       6       9      14      
     3    --    --    --     8    10    13    19    
  --  --  --  --  --  --  --  --  --  --  --  --  --  --  16  --  
----------------------------------
           7          
         5        11        
       4       6       9      14      
     3    --    --    --     8    10    13    16    
  --  --  --  --  --  --  --  --  --  --  --  --  --  --  15  19  
----------------------------------
           7          
         5        11        
       3       6       9      14      
     2     4    --    --     8    10    13    16    
  --  --  --  --  --  --  --  --  --  --  --  --  --  --  15  19  
----------------------------------
           7          
         5        11        
       3       6       9      14      
     2     4    --    --     8    10    13    16    
  --  --  --  --  --  --  --  --  --  --  --  --  12  --  15  19  
----------------------------------
depth=5, value=7, left=3, right=4
L[5][7]
depth=3, value=5, left=2, right=1
L[3][5]
depth=2, value=3, left=1, right=1
L[2][3]
depth=1, value=2, left=0, right=0
L[1][2]
R[1][2]
R[2][3]
depth=1, value=4, left=0, right=0
L[1][4]
R[1][4]
R[3][5]
depth=1, value=6, left=0, right=0
L[1][6]
R[1][6]
R[5][7]
depth=4, value=11, left=2, right=3
L[4][11]
depth=2, value=9, left=1, right=1
L[2][9]
depth=1, value=8, left=0, right=0
L[1][8]
R[1][8]
R[2][9]
depth=1, value=10, left=0, right=0
L[1][10]
R[1][10]
R[4][11]
depth=3, value=14, left=2, right=2
L[3][14]
depth=2, value=13, left=1, right=0
L[2][13]
depth=1, value=12, left=0, right=0
L[1][12]
R[1][12]
R[2][13]
R[3][14]
depth=2, value=16, left=1, right=1
L[2][16]
depth=1, value=15, left=0, right=0
L[1][15]
R[1][15]
R[2][16]
depth=1, value=19, left=0, right=0
L[1][19]
R[1][19]
https://ideone.com/R3d3sj
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!