fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct Node* Node;
  5. struct Node {
  6.    int value;
  7.    Node left;
  8.    Node right;
  9. };
  10.  
  11. typedef struct Tree* Tree;
  12. struct Tree {
  13.    Node root;
  14. };
  15.  
  16. typedef struct StackNode* StackNode;
  17. struct StackNode {
  18.    void* value;
  19.    StackNode next;
  20. };
  21.  
  22. typedef struct Stack* Stack;
  23. struct Stack {
  24.    StackNode root;
  25. };
  26.  
  27. typedef struct DumpState* DumpState;
  28. struct DumpState {
  29.    int state;
  30.    Node node;
  31.    int indent;
  32. };
  33.  
  34. void Stack_push(Stack stack, void* value) {
  35.    StackNode node = malloc(sizeof(struct StackNode));
  36.    node->value = value;
  37.    node->next = stack->root;
  38.    stack->root = node;
  39. }
  40.  
  41. void* Stack_pop(Stack stack) {
  42.    void* value;
  43.    StackNode node;
  44.    if (stack->root == NULL) {
  45.       return NULL;
  46.    } else {
  47.       node = stack->root;
  48.       stack->root = node->next;
  49.       value = node->value;
  50.       free(node);
  51.       return value;
  52.    }
  53. }
  54.  
  55. void Tree_add(Tree tree, int value) {
  56.    Node n;
  57.    Node p;
  58.  
  59.    n = malloc(sizeof(struct Node));
  60.    n->value = value;
  61.    n->left = NULL;
  62.    n->right = NULL;
  63.  
  64.    if (tree->root == NULL) {
  65.       tree->root = n;
  66.    } else {
  67.       p = tree->root;
  68.       while (1) {
  69.          if (value < p->value) {
  70.             if (p->left == NULL) {
  71.                p->left = n;
  72.                break;
  73.             } else {
  74.                p = p->left;
  75.             }
  76.          } else {
  77.             if (p->right == NULL) {
  78.                p->right = n;
  79.                break;
  80.             } else {
  81.                p = p->right;
  82.             }
  83.          }
  84.       }
  85.    }
  86. }
  87.  
  88. void Tree_dump(Tree tree) {
  89.    Stack stack;
  90.    DumpState ds;
  91.    DumpState ds2;
  92.    const int right = 0;
  93.    const int left = 1;
  94.    int state;
  95.    Node node;
  96.    int indent;
  97.    int indent2;
  98.    int i;
  99.  
  100.    if (tree->root == NULL) {
  101.       return;
  102.    }
  103.    stack = malloc(sizeof(struct Stack));
  104.    ds = malloc(sizeof(struct DumpState));
  105.    ds->state = right;
  106.    ds->node = tree->root;
  107.    ds->indent = 0;
  108.    Stack_push(stack, ds);
  109.    while (stack->root != NULL) {
  110.       ds = Stack_pop(stack);
  111.       state = ds->state;
  112.       node = ds->node;
  113.       indent = ds->indent;
  114.       if (state == right) {
  115.          indent2 = indent;
  116.          do {
  117.             ds2 = malloc(sizeof(struct DumpState));
  118.             ds2->state = left;
  119.             ds2->node = node;
  120.             ds2->indent = indent2;
  121.             Stack_push(stack, ds2);
  122.             indent2 = indent2 + 1;
  123.             node = node->right;
  124.          } while (node != NULL);
  125.       } else if (state == left) {
  126.          for (i = 0; i < indent; i++) {
  127.             printf("　");
  128.          }
  129.          printf("%d\n", node->value);
  130.          if (node->left != NULL) {
  131.             ds2 = malloc(sizeof(struct DumpState));
  132.             ds2->state = right;
  133.             ds2->node = node->left;
  134.             ds2->indent = indent + 1;
  135.             Stack_push(stack, ds2);            
  136.          }
  137.       }
  138.       free(ds);
  139.    }
  140.    free(stack);
  141. }
  142.  
  143. int main(void) {
  144.    Tree tree = malloc(sizeof(struct Tree));
  145.    Tree_add(tree, 3);
  146.    Tree_add(tree, 1);
  147.    Tree_add(tree, 5);
  148.    Tree_add(tree, 0);
  149.    Tree_add(tree, 2);
  150.    Tree_add(tree, 4);
  151.    Tree_add(tree, 6);
  152.    Tree_dump(tree);
  153.    return EXIT_SUCCESS;
  154. }
  155.  
Success #stdin #stdout 0.01s 1808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
　　6
　5
　　4
3
　　2
　1
　　0
https://ideone.com/RDNCac
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!