fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAX_HEIGHT 1000
  6. int lprofile[MAX_HEIGHT];
  7. int rprofile[MAX_HEIGHT];
  8. #define INFINITY (1<<20)
  9.  
  10. typedef int ELEMENT;
  11.  
  12. typedef struct BSTNode_struct BSTNode;
  13.  
  14. struct BSTNode_struct {
  15.     BSTNode *ptLeft, *ptRight;
  16.  
  17.     //length of the edge from this node to its children
  18.     int edge_length;
  19.  
  20.     int height;
  21.  
  22.     ELEMENT element;
  23.  
  24.     //-1=I am left, 0=I am root, 1=right
  25.     int parent_dir;
  26.  
  27.     //max supported unit32 in dec, 10 digits max
  28.     char label[11];
  29. };
  30.  
  31. typedef struct Tree Tree;
  32.  
  33. struct Tree {
  34.     Tree *left, *right;
  35.     int element;
  36. };
  37.  
  38. Tree *find_min(Tree *t) {
  39.     if (t == NULL) {
  40.         return NULL;
  41.     }
  42.     else if (t->left == NULL) {
  43.         return t;
  44.     }
  45.     else {
  46.         return find_min(t->left);
  47.     }
  48. }
  49.  
  50. Tree *find_max(Tree *t) {
  51.     if (t == NULL) {
  52.         return NULL;
  53.     }
  54.     else if (t->right == NULL) {
  55.         return t;
  56.     }
  57.     else {
  58.         return find_max(t->right);
  59.     }
  60. }
  61.  
  62. Tree *find(int elem, Tree *t) {
  63.     if (t == NULL) {
  64.         return NULL;
  65.     }
  66.  
  67.     if (elem < t->element) {
  68.         return find(elem, t->left);
  69.     }
  70.     else if (elem > t->element) {
  71.         return find(elem, t->right);
  72.     }
  73.     else {
  74.         return t;
  75.     }
  76. }
  77.  
  78. //Insert i into the tree t, duplicate will be discarded
  79. //Return a pointer to the resulting tree.
  80. Tree *insert(int value, Tree *t) {
  81.     Tree *new_node;
  82.  
  83.     if (t == NULL) {
  84.         new_node = (Tree *) malloc(sizeof(Tree));
  85.         if (new_node == NULL) {
  86.             return t;
  87.         }
  88.  
  89.         new_node->element = value;
  90.  
  91.         new_node->left = new_node->right = NULL;
  92.         return new_node;
  93.     }
  94.  
  95.     if (value < t->element) {
  96.         t->left = insert(value, t->left);
  97.     }
  98.     else if (value > t->element) {
  99.         t->right = insert(value, t->right);
  100.     }
  101.     else {
  102.         //duplicate, ignore it
  103.         return t;
  104.     }
  105.     return t;
  106. }
  107.  
  108.  
  109. //adjust gap between left and right nodes
  110. int gap = 3;
  111.  
  112. //used for printing next node in the same level,
  113. //this is the x coordinate of the next char printed
  114. int print_next;
  115.  
  116. int MIN(int X, int Y) {
  117.     return ((X) < (Y)) ? (X) : (Y);
  118. }
  119.  
  120. int MAX(int X, int Y) {
  121.     return ((X) > (Y)) ? (X) : (Y);
  122. }
  123.  
  124. BSTNode *build_ascii_tree_recursive(Tree *t) {
  125.     BSTNode *node;
  126.  
  127.     if (t == NULL) return NULL;
  128.  
  129.     node = malloc(sizeof(BSTNode));
  130.     node->ptLeft = build_ascii_tree_recursive(t->left);
  131.     node->ptRight = build_ascii_tree_recursive(t->right);
  132.  
  133.     if (node->ptLeft != NULL) {
  134.         node->ptLeft->parent_dir = -1;
  135.     }
  136.  
  137.     if (node->ptRight != NULL) {
  138.         node->ptRight->parent_dir = 1;
  139.     }
  140.  
  141.     sprintf(node->label, "%d", t->element);
  142.     node->element = strlen(node->label);
  143.  
  144.     return node;
  145. }
  146.  
  147.  
  148. //Copy the tree into the ascii node structre
  149. BSTNode *build_ascii_tree(Tree *t) {
  150.     BSTNode *node;
  151.     if (t == NULL) return NULL;
  152.     node = build_ascii_tree_recursive(t);
  153.     node->parent_dir = 0;
  154.     return node;
  155. }
  156.  
  157. //Free all the nodes of the given tree
  158. void free_ascii_tree(BSTNode *node) {
  159.     if (node == NULL) return;
  160.     free_ascii_tree(node->ptLeft);
  161.     free_ascii_tree(node->ptRight);
  162.     free(node);
  163. }
  164.  
  165. //The following function fills in the lprofile array for the given tree.
  166. //It assumes that the center of the label of the root of this tree
  167. //is located at a position (x,y).  It assumes that the edge_length
  168. //fields have been computed for this tree.
  169. void compute_lprofile(BSTNode *node, int x, int y) {
  170.     int i, isleft;
  171.     if (node == NULL) return;
  172.     isleft = (node->parent_dir == -1);
  173.     lprofile[y] = MIN(lprofile[y], x - ((node->element - isleft) / 2));
  174.     if (node->ptLeft != NULL) {
  175.         for (i = 1; i <= node->edge_length && y + i < MAX_HEIGHT; i++) {
  176.             lprofile[y + i] = MIN(lprofile[y + i], x - i);
  177.         }
  178.     }
  179.     compute_lprofile(node->ptLeft, x - node->edge_length - 1, y + node->edge_length + 1);
  180.     compute_lprofile(node->ptRight, x + node->edge_length + 1, y + node->edge_length + 1);
  181. }
  182.  
  183. void compute_rprofile(BSTNode *node, int x, int y) {
  184.     int i, notleft;
  185.     if (node == NULL) return;
  186.     notleft = (node->parent_dir != -1);
  187.     rprofile[y] = MAX(rprofile[y], x + ((node->element - notleft) / 2));
  188.     if (node->ptRight != NULL) {
  189.         for (i = 1; i <= node->edge_length && y + i < MAX_HEIGHT; i++) {
  190.             rprofile[y + i] = MAX(rprofile[y + i], x + i);
  191.         }
  192.     }
  193.     compute_rprofile(node->ptLeft, x - node->edge_length - 1, y + node->edge_length + 1);
  194.     compute_rprofile(node->ptRight, x + node->edge_length + 1, y + node->edge_length + 1);
  195. }
  196.  
  197. //This function fills in the edge_length and
  198. //height fields of the specified tree
  199. void filledge(BSTNode *node) {
  200.     int h, hmin, i, delta;
  201.     if (node == NULL) return;
  202.     filledge(node->ptLeft);
  203.     filledge(node->ptRight);
  204.  
  205.     /* first fill in the edge_length of node */
  206.     if (node->ptRight == NULL && node->ptLeft == NULL) {
  207.         node->edge_length = 0;
  208.     }
  209.     else {
  210.         if (node->ptLeft != NULL) {
  211.             for (i = 0; i < node->ptLeft->height && i < MAX_HEIGHT; i++) {
  212.                 rprofile[i] = -INFINITY;
  213.             }
  214.             compute_rprofile(node->ptLeft, 0, 0);
  215.             hmin = node->ptLeft->height;
  216.         }
  217.         else {
  218.             hmin = 0;
  219.         }
  220.         if (node->ptRight != NULL) {
  221.             for (i = 0; i < node->ptRight->height && i < MAX_HEIGHT; i++) {
  222.                 lprofile[i] = INFINITY;
  223.             }
  224.             compute_lprofile(node->ptRight, 0, 0);
  225.             hmin = MIN(node->ptRight->height, hmin);
  226.         }
  227.         else {
  228.             hmin = 0;
  229.         }
  230.         delta = 4;
  231.         for (i = 0; i < hmin; i++) {
  232.             delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
  233.         }
  234.  
  235.         //If the node has two children of height 1, then we allow the
  236.         //two leaves to be within 1, instead of 2
  237.         if (((node->ptLeft != NULL && node->ptLeft->height == 1) ||
  238.              (node->ptRight != NULL && node->ptRight->height == 1)) && delta > 4) {
  239.             delta--;
  240.         }
  241.  
  242.         node->edge_length = ((delta + 1) / 2) - 1;
  243.     }
  244.  
  245.     //now fill in the height of node
  246.     h = 1;
  247.     if (node->ptLeft != NULL) {
  248.         h = MAX(node->ptLeft->height + node->edge_length + 1, h);
  249.     }
  250.     if (node->ptRight != NULL) {
  251.         h = MAX(node->ptRight->height + node->edge_length + 1, h);
  252.     }
  253.     node->height = h;
  254. }
  255.  
  256. //This function prints the given level of the given tree, assuming
  257. //that the node has the given x cordinate.
  258. void printLevel(BSTNode *node, int x, int level) {
  259.     int i, isleft;
  260.     if (node == NULL) return;
  261.     isleft = (node->parent_dir == -1);
  262.     if (level == 0) {
  263.         for (i = 0; i < (x - print_next - ((node->element - isleft) / 2)); i++) {
  264.             printf(" ");
  265.         }
  266.         print_next += i;
  267.         printf("%s", node->label);
  268.         print_next += node->element;
  269.     }
  270.     else if (node->edge_length >= level) {
  271.         if (node->ptLeft != NULL) {
  272.             for (i = 0; i < (x - print_next - (level)); i++) {
  273.                 printf(" ");
  274.             }
  275.             print_next += i;
  276.             printf("/");
  277.             print_next++;
  278.         }
  279.         if (node->ptRight != NULL) {
  280.             for (i = 0; i < (x - print_next + (level)); i++) {
  281.                 printf(" ");
  282.             }
  283.             print_next += i;
  284.             printf("\\");
  285.             print_next++;
  286.         }
  287.     }
  288.     else {
  289.         printLevel(node->ptLeft,
  290.                    x - node->edge_length - 1,
  291.                    level - node->edge_length - 1);
  292.         printLevel(node->ptRight,
  293.                    x + node->edge_length + 1,
  294.                    level - node->edge_length - 1);
  295.     }
  296. }
  297.  
  298. //prints ascii tree for given Tree structure
  299. void printElements(Tree *t) {
  300.     BSTNode *proot;
  301.     int xmin, i;
  302.     if (t == NULL) return;
  303.     proot = build_ascii_tree(t);
  304.     filledge(proot);
  305.     for (i = 0; i < proot->height && i < MAX_HEIGHT; i++) {
  306.         lprofile[i] = INFINITY;
  307.     }
  308.     compute_lprofile(proot, 0, 0);
  309.     xmin = 0;
  310.     for (i = 0; i < proot->height && i < MAX_HEIGHT; i++) {
  311.         xmin = MIN(xmin, lprofile[i]);
  312.     }
  313.     for (i = 0; i < proot->height; i++) {
  314.         print_next = 0;
  315.         printLevel(proot, -xmin, i);
  316.         printf("\n");
  317.     }
  318.     if (proot->height >= MAX_HEIGHT) {
  319.         printf("(This tree is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT);
  320.     }
  321.     free_ascii_tree(proot);
  322. }
  323.  
  324.  
  325. //driver
  326. int main() {
  327.     //A sample use of these functions.  Start with the empty tree
  328.     //insert some stuff into it, and then delete it
  329.     Tree *root;
  330.     int i;
  331.     root = NULL;
  332.  
  333. //    make_empty(root);
  334.  
  335.     printf("\nAfter inserting element 10..\n");
  336.     root = insert(10, root);
  337.     printElements(root);
  338.  
  339.     printf("\nAfter inserting element 5..\n");
  340.     root = insert(5, root);
  341.     printElements(root);
  342.  
  343.     printf("\nAfter inserting element 20..\n");
  344.     root = insert(20, root);
  345.     printElements(root);
  346.  
  347.     printf("\nAfter inserting elements 7, 14, 28..\n");
  348.     root = insert(7, root);
  349.     root = insert(14, root);
  350.     root = insert(28, root);
  351.     printElements(root);
  352.  
  353.     printf("\nAfter inserting element 3.\n");
  354.     root = insert(3, root);
  355.  
  356.  ;
  357.     printElements(root);
  358.     return 0;
  359.  
  360. }
Success #stdin #stdout 0s 2256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
After inserting element 10..
10

After inserting element 5..
 10
 /
5

After inserting element 20..
 10
 / \
5  20

After inserting elements 7, 14, 28..
   10
   / \
  /   \
 /     \
5      20
 \     / \
  7   /   \
     14   28

After inserting element 3.
     10
     / \
    /   \
   /     \
  5      20
 / \     / \
3   7   /   \
       14   28
https://ideone.com/Gz6gE8
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!