fork download
copy 
  1. /* Author: Leonardone @ NEETSDKASU */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5.  
  6. typedef enum _bool { False, True = !False } Bool, *LPBool;
  7. typedef enum _color { Black, Red } Color, *LPColor;
  8.  
  9. typedef struct _node {
  10. 	Color color;
  11. 	struct _node *left;
  12. 	struct _node *right;
  13. 	int key;
  14. } Node, *LPNode;
  15.  
  16. typedef struct _tree{
  17. 	LPNode root;
  18. } Tree, *LPTree;
  19.  
  20. LPTree initTree(LPTree tree);
  21. LPTree addTreeValue(LPTree tree, int value);
  22. Bool isRed(LPNode node);
  23. void turnColor(LPNode node);
  24. LPNode newNode(int key);
  25. LPNode addNode(LPNode node, LPNode newnode);
  26. LPNode checkRight(LPNode node);
  27. LPNode checkLeft(LPNode node);
  28.  
  29. void printCharString(char c, int n);
  30. void printNode(LPNode node, int depth, char c);
  31. void printTree(LPTree tree);
  32.  
  33. int main(void) {
  34.  
  35. 	Tree tree;
  36. 	int i;
  37.  
  38. 	srand(time(NULL));
  39.  
  40. 	initTree(&tree);
  41.  
  42. 	for (i = 1; i < 55; i++) {
  43. 		addTreeValue(&tree, rand() % 100);
  44. 	}
  45.  
  46. 	printTree(&tree);
  47.  
  48. 	return 0;
  49. }
  50.  
  51. void printCharString(char c, int n) {
  52. 	while (n-- > 0) {
  53. 		putchar(c);
  54. 	}
  55. }
  56.  
  57. void printNode(LPNode node, int depth, char c) {
  58. 	if (node == NULL) {
  59. 		//printCharString(' ', depth * 5);
  60. 		//puts("null");
  61. 		return;
  62. 	}
  63. 	printNode(node->right, depth + 1, '/');
  64. 	printCharString(' ', depth * 5);
  65. 	putchar(c);
  66. 	putchar(isRed(node) ? 'R' : 'B');
  67. 	printf("%02d\n", node->key);
  68. 	printNode(node->left, depth + 1, '\\');
  69. }
  70.  
  71. void printTree(LPTree tree) {
  72. 	if (tree == NULL) {
  73. 		puts("NULL");
  74. 	}
  75. 	printNode(tree->root, 0, '-');
  76. }
  77.  
  78. LPTree initTree(LPTree tree) {
  79. 	if (tree != NULL) {
  80. 		tree->root = NULL;
  81. 	}
  82. 	return tree;
  83. }
  84.  
  85. LPTree addTreeValue(LPTree tree, int value) {
  86. 	if (tree != NULL) {
  87. 		tree->root = addNode(tree->root, newNode(value));
  88. 		if (tree->root->color == Red) {
  89. 			tree->root->color = Black;
  90. 		}
  91. 	}
  92. 	return tree;
  93. }
  94.  
  95. Bool isRed(LPNode node) {
  96. 	return (node != NULL && node->color == Red) ? True : False;
  97. }
  98.  
  99. void turnColor(LPNode node) {
  100. 	if (node != NULL) {
  101. 		node->color = (node->color == Red) ? Black : Red;
  102. 	}
  103. }
  104.  
  105. LPNode newNode(int key) {
  106. 	LPNode node = (LPNode)malloc(sizeof(Node));
  107. 	if (node != NULL) {
  108. 		node->color = Red;
  109. 		node->left = NULL;
  110. 		node->right = NULL;
  111. 		node->key = key;
  112. 	}
  113. 	return node;
  114. }
  115.  
  116. LPNode checkRight(LPNode node) {
  117. 	LPNode temp1, temp2;
  118. 	if (node == NULL || isRed(node) || !isRed(node->right)) {
  119. 		return node;
  120. 	}
  121. 	temp1 = node->right;
  122. 	if (isRed(temp1->right)) {
  123. 		turnColor(node);
  124. 		turnColor(temp1);
  125. 		if (isRed(node->left)) {
  126. 			turnColor(node->left);
  127. 		} else {
  128. 			node->right = temp1->left;
  129. 			temp1->left = node;
  130. 			return temp1;
  131. 		}
  132. 	} else if (isRed(temp1->left)) {
  133. 		turnColor(node);
  134. 		if (isRed(node->left)) {
  135. 			turnColor(temp1);
  136. 			turnColor(node->left);
  137. 		} else {
  138. 			temp2 = temp1->left;
  139. 			turnColor(temp2);
  140. 			node->right = temp2->left;
  141. 			temp1->left = temp2->right;
  142. 			temp2->left = node;
  143. 			temp2->right = temp1;
  144. 			return temp2;
  145. 		}
  146. 	}
  147. 	return node;
  148. }
  149.  
  150. LPNode checkLeft(LPNode node) {
  151. 	LPNode temp1, temp2;
  152. 	if (node == NULL || isRed(node) || !isRed(node->left)) {
  153. 		return node;
  154. 	}
  155. 	temp1 = node->left;
  156. 	if (isRed(temp1->left)) {
  157. 		turnColor(node);
  158. 		turnColor(temp1);
  159. 		if (isRed(node->right)) {
  160. 			turnColor(node->right);
  161. 		} else {
  162. 			node->left = temp1->right;
  163. 			temp1->right = node;
  164. 			return temp1;
  165. 		}
  166. 	} else if (isRed(temp1->right)) {
  167. 		turnColor(node);
  168. 		if (isRed(node->right)) {
  169. 			turnColor(temp1);
  170. 			turnColor(node->right);
  171. 		} else {
  172. 			temp2 = temp1->right;
  173. 			turnColor(temp2);
  174. 			node->left = temp2->right;
  175. 			temp1->right = temp2->left;
  176. 			temp2->right = node;
  177. 			temp2->left = temp1;
  178. 			return temp2;
  179. 		}
  180. 	}
  181. 	return node;
  182. }
  183.  
  184. LPNode addNode(LPNode node, LPNode newnode) {
  185. 	if (node == NULL) {
  186. 		return newnode;
  187. 	}
  188. 	if (newnode == NULL) {
  189. 		return node;
  190. 	}
  191. 	if (newnode->key > node->key) {
  192. 		node->right = addNode(node->right, newnode);
  193. 		node = checkRight(node);
  194. 	} else {
  195. 		node->left = addNode(node->left, newnode);
  196. 		node = checkLeft(node);
  197. 	}
  198. 	return node;
  199. } 
  200.  
Success #stdin #stdout 0s 2184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
                    /B99
               /B98
                    \B98
          /R97
                         /B97
                    /R96
                              /R95
                         \B92
                              \R90
               \B87
                         /B83
                              \R83
                    \R81
                              /R81
                         \B77
                              \R77
     /B72
                    /B71
               /B66
                         /R66
                    \B64
                         \R63
          \R61
                    /B61
               \B60
                         /B59
                    \R57
                              /R56
                         \B55
                              \R55
-B54
               /B54
                    \R54
          /B53
                    /R53
               \B50
                    \R50
     \B47
                         /R46
                    /B42
               /B39
                         /R37
                    \B36
          \R34
                         /B34
                    /R30
                              /R21
                         \B18
                              \R16
               \B13
                              /R08
                         /B06
                    \R04
                         \B00
https://ideone.com/eVSwA3
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!