SHARE
TWEET

Printf arvore

Gibua May 22nd, 2019 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. typedef struct Node Node;
  6.  
  7. struct Node{
  8.   Node * esq, * dir;
  9.   int chave;
  10. };
  11.  
  12. Node *make_empty(Node *t)
  13. {
  14.   if (t != NULL)
  15.   {
  16.     make_empty(t->esq);
  17.     make_empty(t->dir);
  18.     free(t);
  19.   }
  20.  
  21.   return NULL;
  22. }
  23.  
  24. Node *find_min(Node *t)
  25. {
  26.   if (t == NULL)
  27.   {
  28.     return NULL;
  29.   }
  30.   else if (t->esq == NULL)
  31.   {
  32.     return t;
  33.   }
  34.   else
  35.   {
  36.     return find_min(t->esq);
  37.   }
  38. }
  39.  
  40. Node *find_max(Node *t)
  41. {
  42.   if (t == NULL)
  43.   {
  44.     return NULL;
  45.   }
  46.   else if (t->dir == NULL)
  47.   {
  48.     return t;
  49.   }
  50.   else
  51.   {
  52.     return find_max(t->dir);
  53.   }
  54. }
  55.  
  56. Node *find(int elem, Node *t)
  57. {
  58.   if (t == NULL)
  59.   {
  60.     return NULL;
  61.   }
  62.  
  63.   if (elem < t->chave)
  64.   {
  65.     return find(elem, t->esq);
  66.   }
  67.   else if (elem > t->chave)
  68.   {
  69.     return find(elem, t->dir);
  70.   }
  71.   else
  72.   {
  73.     return t;
  74.   }
  75. }
  76.  
  77. //Insert i into the Node t, duplicate will be discarded
  78. //Return a pointer to the resulting Node.                
  79. Node * insert(int value, Node * t)
  80. {
  81.   Node * new_node;
  82.  
  83.   if (t == NULL)
  84.   {
  85.     new_node = (Node *) malloc (sizeof (Node));
  86.     if (new_node == NULL)
  87.     {
  88.       return t;
  89.     }
  90.    
  91.     new_node->chave = value;
  92.    
  93.     new_node->esq = new_node->dir = NULL;
  94.     return new_node;
  95.   }
  96.  
  97.   if (value < t->chave)
  98.   {
  99.     t->esq = insert(value, t->esq);
  100.   }
  101.   else if (value > t->chave)
  102.   {
  103.     t->dir = insert(value, t->dir);
  104.   }
  105.   else
  106.   {
  107.     //duplicate, ignore it
  108.     return t;
  109.   }
  110.   return t;
  111. }
  112.  
  113. Node * delete(int value, Node * t)
  114. {
  115.   //Deletes node from the Node
  116.   // Return a pointer to the resulting Node
  117.   Node * x;
  118.   Node *tmp_cell;
  119.  
  120.   if (t==NULL) return NULL;
  121.  
  122.   if (value < t->chave)
  123.   {
  124.     t->esq = delete(value, t->esq);
  125.   }
  126.   else if (value > t->chave)
  127.   {
  128.     t->dir = delete(value, t->dir);
  129.   }
  130.   else if (t->esq && t->dir)
  131.   {
  132.     tmp_cell = find_min(t->dir);
  133.     t->chave = tmp_cell->chave;
  134.     t->dir = delete(t->chave, t->dir);
  135.   }
  136.   else
  137.   {
  138.     tmp_cell = t;
  139.     if (t->esq == NULL)
  140.     t = t->dir;
  141.     else if (t->dir == NULL)
  142.     t = t->esq;
  143.     free(tmp_cell);
  144.   }
  145.  
  146.   return t;
  147. }
  148.  
  149.  
  150. //printing Node in ascii
  151.  
  152. typedef struct asciinode_struct asciinode;
  153.  
  154. struct asciinode_struct
  155. {
  156.   asciinode * esq, * dir;
  157.  
  158.   //length of the edge from this node to its children
  159.   int edge_length;
  160.  
  161.   int height;      
  162.  
  163.   int lablen;
  164.  
  165.   //-1=I am esq, 0=I am root, 1=dir  
  166.   int parent_dir;  
  167.  
  168.   //max supported unit32 in dec, 10 digits max
  169.   char label[11];  
  170. };
  171.  
  172.  
  173. #define MAX_HEIGHT 1000
  174. int lprofile[MAX_HEIGHT];
  175. int rprofile[MAX_HEIGHT];
  176. #define INFINITY (1<<20)
  177.  
  178. //adjust gap between esq and dir nodes
  179. int gap = 3;  
  180.  
  181. //used for printing next node in the same level,
  182. //this is the x coordinate of the next char printed
  183. int print_next;    
  184.  
  185. int MIN (int X, int Y)  
  186. {
  187.   return ((X) < (Y)) ? (X) : (Y);
  188. }
  189.  
  190. int MAX (int X, int Y)  
  191. {
  192.   return ((X) > (Y)) ? (X) : (Y);
  193. }
  194.  
  195. asciinode * build_ascii_Node_recursive(Node * t)
  196. {
  197.   asciinode * node;
  198.  
  199.   if (t == NULL) return NULL;
  200.  
  201.   node = malloc(sizeof(asciinode));
  202.   node->esq = build_ascii_Node_recursive(t->esq);
  203.   node->dir = build_ascii_Node_recursive(t->dir);
  204.  
  205.   if (node->esq != NULL)
  206.   {
  207.     node->esq->parent_dir = -1;
  208.   }
  209.  
  210.   if (node->dir != NULL)
  211.   {
  212.     node->dir->parent_dir = 1;
  213.   }
  214.  
  215.   sprintf(node->label, "%d", t->chave);
  216.   node->lablen = strlen(node->label);
  217.  
  218.   return node;
  219. }
  220.  
  221.  
  222. //Copy the Node into the ascii node structre
  223. asciinode * build_ascii_Node(Node * t)
  224. {
  225.   asciinode *node;
  226.   if (t == NULL) return NULL;
  227.   node = build_ascii_Node_recursive(t);
  228.   node->parent_dir = 0;
  229.   return node;
  230. }
  231.  
  232. //Free all the nodes of the given Node
  233. void free_ascii_Node(asciinode *node)
  234. {
  235.   if (node == NULL) return;
  236.   free_ascii_Node(node->esq);
  237.   free_ascii_Node(node->dir);
  238.   free(node);
  239. }
  240.  
  241. //The following function fills in the lprofile array for the given Node.
  242. //It assumes that the center of the label of the root of this Node
  243. //is located at a position (x,y).  It assumes that the edge_length
  244. //fields have been computed for this Node.
  245. void compute_lprofile(asciinode *node, int x, int y)
  246. {
  247.   int i, isesq;
  248.   if (node == NULL) return;
  249.   isesq = (node->parent_dir == -1);
  250.   lprofile[y] = MIN(lprofile[y], x-((node->lablen-isesq)/2));
  251.   if (node->esq != NULL)
  252.   {
  253.     for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++)
  254.     {
  255.       lprofile[y+i] = MIN(lprofile[y+i], x-i);
  256.     }
  257.   }
  258.   compute_lprofile(node->esq, x-node->edge_length-1, y+node->edge_length+1);
  259.   compute_lprofile(node->dir, x+node->edge_length+1, y+node->edge_length+1);
  260. }
  261.  
  262. void compute_rprofile(asciinode *node, int x, int y)
  263. {
  264.   int i, notesq;
  265.   if (node == NULL) return;
  266.   notesq = (node->parent_dir != -1);
  267.   rprofile[y] = MAX(rprofile[y], x+((node->lablen-notesq)/2));
  268.   if (node->dir != NULL)
  269.   {
  270.     for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++)
  271.     {
  272.       rprofile[y+i] = MAX(rprofile[y+i], x+i);
  273.     }
  274.   }
  275.   compute_rprofile(node->esq, x-node->edge_length-1, y+node->edge_length+1);
  276.   compute_rprofile(node->dir, x+node->edge_length+1, y+node->edge_length+1);
  277. }
  278.  
  279. //This function fills in the edge_length and
  280. //height fields of the specified Node
  281. void compute_edge_lengths(asciinode *node)
  282. {
  283.   int h, hmin, i, delta;
  284.   if (node == NULL) return;
  285.   compute_edge_lengths(node->esq);
  286.   compute_edge_lengths(node->dir);
  287.  
  288.   /* first fill in the edge_length of node */
  289.   if (node->dir == NULL && node->esq == NULL)
  290.   {
  291.     node->edge_length = 0;
  292.   }
  293.   else
  294.   {
  295.     if (node->esq != NULL)
  296.     {
  297.       for (i=0; i<node->esq->height && i < MAX_HEIGHT; i++)
  298.       {
  299.         rprofile[i] = -INFINITY;
  300.       }
  301.       compute_rprofile(node->esq, 0, 0);
  302.       hmin = node->esq->height;
  303.     }
  304.     else
  305.     {
  306.       hmin = 0;
  307.     }
  308.     if (node->dir != NULL)
  309.     {
  310.       for (i=0; i<node->dir->height && i < MAX_HEIGHT; i++)
  311.       {
  312.         lprofile[i] = INFINITY;
  313.       }
  314.       compute_lprofile(node->dir, 0, 0);
  315.       hmin = MIN(node->dir->height, hmin);
  316.     }
  317.     else
  318.     {
  319.       hmin = 0;
  320.     }
  321.     delta = 4;
  322.     for (i=0; i<hmin; i++)
  323.     {
  324.       delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
  325.     }
  326.    
  327.     //If the node has two children of height 1, then we allow the
  328.     //two leaves to be within 1, instead of 2
  329.     if (((node->esq != NULL && node->esq->height == 1) ||
  330.     (node->dir != NULL && node->dir->height == 1))&&delta>4)
  331.     {
  332.       delta--;
  333.     }
  334.    
  335.     node->edge_length = ((delta+1)/2) - 1;
  336.   }
  337.  
  338.   //now fill in the height of node
  339.   h = 1;
  340.   if (node->esq != NULL)
  341.   {
  342.     h = MAX(node->esq->height + node->edge_length + 1, h);
  343.   }
  344.   if (node->dir != NULL)
  345.   {
  346.     h = MAX(node->dir->height + node->edge_length + 1, h);
  347.   }
  348.   node->height = h;
  349. }
  350.  
  351. //This function prints the given level of the given Node, assuming
  352. //that the node has the given x cordinate.
  353. void print_level(asciinode *node, int x, int level)
  354. {
  355.   int i, isesq;
  356.   if (node == NULL) return;
  357.   isesq = (node->parent_dir == -1);
  358.   if (level == 0)
  359.   {
  360.     for (i=0; i<(x-print_next-((node->lablen-isesq)/2)); i++)
  361.     {
  362.       printf(" ");
  363.     }
  364.     print_next += i;
  365.     printf("%s", node->label);
  366.     print_next += node->lablen;
  367.   }
  368.   else if (node->edge_length >= level)
  369.   {
  370.     if (node->esq != NULL)
  371.     {
  372.       for (i=0; i<(x-print_next-(level)); i++)
  373.       {
  374.         printf(" ");
  375.       }
  376.       print_next += i;
  377.       printf("/");
  378.       print_next++;
  379.     }
  380.     if (node->dir != NULL)
  381.     {
  382.       for (i=0; i<(x-print_next+(level)); i++)
  383.       {
  384.         printf(" ");
  385.       }
  386.       print_next += i;
  387.       printf("\\");
  388.       print_next++;
  389.     }
  390.   }
  391.   else
  392.   {
  393.     print_level(node->esq,
  394.       x-node->edge_length-1,
  395.       level-node->edge_length-1);
  396.       print_level(node->dir,
  397.         x+node->edge_length+1,
  398.         level-node->edge_length-1);
  399.       }
  400.     }
  401.    
  402.     //prints ascii Node for given Node structure
  403.     void print_ascii_Node(Node * t)
  404.     {
  405.       asciinode *proot;
  406.       int xmin, i;
  407.       if (t == NULL) return;
  408.       proot = build_ascii_Node(t);
  409.       compute_edge_lengths(proot);
  410.       for (i=0; i<proot->height && i < MAX_HEIGHT; i++)
  411.       {
  412.         lprofile[i] = INFINITY;
  413.       }
  414.       compute_lprofile(proot, 0, 0);
  415.       xmin = 0;
  416.       for (i = 0; i < proot->height && i < MAX_HEIGHT; i++)
  417.       {
  418.         xmin = MIN(xmin, lprofile[i]);
  419.       }
  420.       for (i = 0; i < proot->height; i++)
  421.       {
  422.         print_next = 0;
  423.         print_level(proot, -xmin, i);
  424.         printf("\n");
  425.       }
  426.       if (proot->height >= MAX_HEIGHT)
  427.       {
  428.         printf("(This Node is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT);
  429.       }
  430.       free_ascii_Node(proot);
  431.     }
  432.  
  433. void BTfromFile(Node** raiz){
  434.   FILE* arq = fopen("C:\\Users\\Alunos\\Downloads\\BT.txt", "r");
  435.   if(arq==NULL) {printf(" Problema ao abrir arquivo!"); return;}
  436.   else{
  437.     int chave;
  438.     char buffer;
  439.     while(1){
  440.       fscanf(arq, "%d, ", &chave);
  441.       insert(chave, raiz);
  442.       if(feof(arq)){
  443.         break;
  444.       }
  445.     }
  446.   }
  447.   fclose(arq);
  448. }
  449.    
  450.     //driver routine
  451.     int main()
  452.     {
  453.       //A sample use of these functions.  Start with the empty Node
  454.       //insert some stuff into it, and then delete it
  455.       Node * root;
  456.       int i;
  457.       root = NULL;    
  458.      
  459.       make_empty(root);
  460.      
  461.       BTfromFile(&root);
  462.      
  463.       /*printf("\nAfter inserting chave 10..\n");
  464.       root = insert(10, root);
  465.       print_ascii_Node(root);
  466.      
  467.       printf("\nAfter inserting chave 5..\n");
  468.       root = insert(5, root);
  469.       print_ascii_Node(root);
  470.      
  471.       printf("\nAfter inserting chave 15..\n");
  472.       root = insert(15, root);
  473.       print_ascii_Node(root);
  474.      
  475.       printf("\nAfter inserting chaves 9, 13..\n");
  476.       root = insert(9, root);
  477.       root = insert(13, root);
  478.       print_ascii_Node(root);
  479.      
  480.       printf("\nAfter inserting chaves 2, 6, 12, 14, ..\n");
  481.       root = insert(2, root);
  482.       root = insert(6, root);
  483.       root = insert(12, root);
  484.       root = insert(14, root);
  485.       print_ascii_Node(root);
  486.      
  487.      
  488.       printf("\n\nAfter deleting a node (14) with no child..\n");
  489.       root = delete(14, root);
  490.       print_ascii_Node(root);
  491.      
  492.       printf("\n\nAfter deleting a node (13) with esq child..\n");
  493.       root = delete(13, root);
  494.       print_ascii_Node(root);
  495.      
  496.       printf("\n\nAfter deleting a node (5) with esq and dir children..\n");
  497.       root = delete(5, root);
  498.       print_ascii_Node(root);
  499.      
  500.       printf("\n\nAfter deleting a node (10, root node) with esq and dir children..\n");
  501.       root = delete(10, root);*/
  502.       print_ascii_Node(root);
  503.      
  504.       make_empty(root);
  505.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top