fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct nodeType *node;
  5. struct nodeType {
  6.     int value;
  7. 	node left;
  8. 	node right;
  9. };
  10.  
  11. node node_new(int value, node left, node right) {
  12. 	node n = malloc(sizeof(struct nodeType));
  13. 	n->value = value;
  14. 	n->left = left;
  15. 	n->right = right;
  16. 	return n;
  17. }
  18.  
  19. void node_dump(node n, int c) {
  20. 	int i;
  21. 	if (n == NULL) {
  22. 		return;
  23. 	}
  24. 	node_dump(n->right, c + 1);
  25. 	for (i = 0; i < c; i++) {
  26. 		printf("  ");
  27. 	}
  28. 	printf("%d\n", n->value);
  29. 	node_dump(n->left, c + 1);
  30. }
  31.  
  32. node rightRotate1(node a) {
  33. 	node b = a->left;
  34. 	a->left = b->right;
  35. 	b->right = a;
  36. 	return b;
  37. }
  38.  
  39. node rightRotate2(node a) {
  40. 	node e = a->left->right;
  41. 	a->left->right = e->left;
  42. 	e->left = a->left;
  43. 	a->left = e->right;
  44. 	e->right = a;
  45. 	return e;
  46. }
  47.  
  48. void rightRotate1Test(void) {
  49. 	node e = node_new(3, NULL, NULL);
  50. 	node d = node_new(1, NULL, NULL);
  51. 	node b = node_new(2, d, e);
  52. 	node c = node_new(5, NULL, NULL);
  53. 	node a = node_new(4, b, c);
  54.  
  55. 	printf("右へ一重回転\n");
  56. 	printf("  回転前\n");
  57. 	node_dump(a, 1);
  58. 	printf("\n");
  59. 	b = rightRotate1(a);
  60. 	printf("  回転後\n");
  61. 	node_dump(b, 1);
  62. 	printf("\n");
  63. }
  64.  
  65. void rightRotate2Test(void) {
  66. 	node g = node_new(5, NULL, NULL);
  67. 	node f = node_new(3, NULL, NULL);
  68. 	node e = node_new(4, f, g);
  69. 	node d = node_new(1, NULL, NULL);
  70. 	node b = node_new(2, d, e);
  71. 	node c = node_new(7, NULL, NULL);
  72. 	node a = node_new(6, b, c);
  73.  
  74. 	printf("右へ二重回転\n");
  75. 	printf("  回転前\n");
  76. 	node_dump(a, 1);
  77. 	printf("\n");
  78. 	e = rightRotate2(a);
  79. 	printf("  回転後\n");
  80. 	node_dump(e, 1);
  81. 	printf("\n");
  82. }
  83.  
  84. int main(void) {
  85. 	rightRotate1Test();
  86. 	rightRotate2Test();
  87.  
  88. 	return EXIT_SUCCESS;
  89. }
Success #stdin #stdout 0.02s 1852KB
comments (?)
stdin 
Standard input is empty
stdout 
右へ一重回転
  回転前
    5
  4
      3
    2
      1

  回転後
      5
    4
      3
  2
    1

右へ二重回転
  回転前
    7
  6
        5
      4
        3
    2
      1

  回転後
      7
    6
      5
  4
      3
    2
      1
https://ideone.com/yAWgFX
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!