Вывод бинарного дерева - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Нужно написать программу, которая будет выводить дерево на экран. Заготовка есть, дерево уже выводится, но нету стрелочек, которые бы облегчали восприятие дерева(как на картинке)... Может, у кого еще есть код печати красивого дерева на Си, очень сильно поможет. Пожалуйста, очень сильно можете.
Листинг программы 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. struct treeNode
  6. {
  7.     struct treeNode *leftPtr;
  8.     int data;
  9.     struct treeNode *rightPtr;
  10. };
  11.  
  12. typedef struct treeNode TREENODE;
  13. typedef TREENODE *TREENODEPTR;
  14.  
  15. void insertNode(TREENODEPTR *, int);
  16. void printTree(TREENODEPTR, int);
  17.  
  18. main()
  19. {
  20.     int i, item;
  21.     TREENODEPTR rootPtr = NULL;
  22.     srand(time(NULL));
  23.     
  24.     printf("The numbers being placed in the tree are:\n");
  25.     
  26.     for(i=1;i<=10;i++)
  27.     {
  28.         item = rand() % 100;
  29.         printf("%3d", item);
  30.         insertNode(&rootPtr, item);
  31.     }
  32.  
  33.     int p=0;
  34.     printf("\n\n\n\n\n\nTree:\n");
  35.     printTree(rootPtr,p);
  36.     
  37.     return 0;
  38. }
  39.  
  40. void insertNode (TREENODEPTR *treePtr, int value)
  41. {
  42.     if (*treePtr == NULL)
  43.     {
  44.         *treePtr = malloc(sizeof(TREENODE));
  45.         if (*treePtr != NULL)
  46.         {
  47.             (*treePtr)->data = value;
  48.             (*treePtr)->leftPtr = NULL;
  49.             (*treePtr)->rightPtr = NULL;
  50.         }
  51.         else
  52.             printf("Not inserted");
  53.     }
  54.     else
  55.         if(value < (*treePtr)->data)
  56.             insertNode(&((*treePtr)->leftPtr), value);
  57.         else
  58.             if(value > (*treePtr)->data)
  59.             insertNode(&((*treePtr)->rightPtr), value);
  60.         else
  61.             printf("dup");  
  62. }
  63.  
  64. void printTree(TREENODEPTR treePtr, int p)
  65. {
  66.     int i;
  67.         if(treePtr != NULL)
  68.     {
  69.         printTree(treePtr->rightPtr,p+3);
  70.         for(i=0;i<p;i++)
  71.         {
  72.             printf(" ");
  73.         }
  74.         printf("%3d\n", treePtr->data);
  75.         printTree(treePtr->leftPtr,p+3);
  76.     }
  77. }

Решение задачи: «Вывод бинарного дерева»

textual
Листинг программы 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. struct treeNode
  6. {
  7.     struct treeNode *leftPtr;
  8.     int data;
  9.     struct treeNode *rightPtr;
  10. };
  11.  
  12. typedef struct treeNode TREENODE;
  13. typedef TREENODE *TREENODEPTR;
  14.  
  15. void insertNode(TREENODEPTR *, int);
  16. void inOrder(TREENODEPTR);
  17. void printTree(TREENODEPTR, int);
  18. //void printTree2(TREENODEPTR);
  19.  
  20. main()
  21. {
  22.     int i, item;
  23.     TREENODEPTR rootPtr = NULL;
  24.     srand(time(NULL));
  25.     
  26.     printf("The numbers being placed in the tree are:\n");
  27.     
  28.     for(i=1;i<=10;i++)
  29.     {
  30.         item = rand() % 100;
  31.         printf("%3d", item);
  32.         insertNode(&rootPtr, item);
  33.     }
  34.     
  35.     //printf("\n\n\nInorder:");
  36.     //inOrder(rootPtr);
  37.     
  38.     int p=0;
  39.     printf("\n\n\n\n\n\nTree:\n");
  40.     //printTree(rootPtr,p);
  41.     //printf("\n\n\n\n\n\nTree:\n");
  42.     //printTree2(rootPtr);
  43.     
  44.     return 0;
  45. }
  46.  
  47. void insertNode (TREENODEPTR *treePtr, int value)
  48. {
  49.     if (*treePtr == NULL)
  50.     {
  51.         *treePtr = malloc(sizeof(TREENODE));
  52.         if (*treePtr != NULL)
  53.         {
  54.             (*treePtr)->data = value;
  55.             (*treePtr)->leftPtr = NULL;
  56.             (*treePtr)->rightPtr = NULL;
  57.         }
  58.         else
  59.             printf("Not inserted");
  60.     }
  61.     else
  62.         if(value < (*treePtr)->data)
  63.             insertNode(&((*treePtr)->leftPtr), value);
  64.         else
  65.             if(value > (*treePtr)->data)
  66.             insertNode(&((*treePtr)->rightPtr), value);
  67.         else
  68.             printf("dup");  
  69. }
  70.  
  71. void inOrder(TREENODEPTR treePtr)
  72. {
  73.     if(treePtr != NULL)
  74.     {
  75.         inOrder(treePtr->leftPtr);
  76.         printf("%3d", treePtr->data);
  77.         inOrder(treePtr->rightPtr);
  78.     }
  79. }
  80.  
  81. /*void printTree(TREENODEPTR treePtr, int p)
  82. {
  83.     int i;
  84.         if(treePtr != NULL)
  85.     {
  86.         printTree(treePtr->rightPtr,p+3);
  87.         for(i=0;i<p;i++)
  88.         {
  89.             printf(" ");
  90.         }
  91.         printf("%3d\n", treePtr->data);
  92.         printTree(treePtr->leftPtr,p+3);
  93.     }
  94. }*/
  95.  
  96. /*void printTree2(TREENODEPTR treePtr)
  97. {
  98.     int i=0, z=0;
  99.     if(treePtr != NULL)
  100.     {
  101.         i++;
  102.         printTree2(treePtr->leftPtr);
  103.         for(z=0;z<i;z++)
  104.         {
  105.             printf(" ");
  106.         }
  107.         printf("%3d\n", treePtr->data);
  108.         printTree2(treePtr->rightPtr);
  109.         i--;
  110.     }*/
  111.     
  112.     
  113. void showLine(char* c, int p, int s) {
  114.     int t=s, i; for(i=0; i<p; i++) {printf(t&1 ? "|  " : "   "); t/=2;} printf(c);
  115. }
  116. void showTree(TREENODEPTR wood, int p, int s) { // string s = string("")) {
  117.     if (wood == NULL) return;
  118.     printf("%d", wood->data); printf("\n");
  119.     
  120.     if (wood->leftPtr != NULL) {
  121.         showLine("|\n", p, s); showLine("L: ", p, s);
  122.         showTree(wood->leftPtr, p+1, s + ((wood->rightPtr == NULL ? 0 : 1)<<p)); 
  123.     }
  124.     if (wood->rightPtr != NULL) {        
  125.         showLine("|\n", p, s); showLine("R: ", p, s);
  126.         showTree(wood->rightPtr, p+1, s);
  127.     }
  128. }

Объяснение кода листинга программы

В этом коде реализована функция showTree, которая позволяет выводить бинарное дерево в отступе. Вот список действий, которые она выполняет:

  1. Если переданный ей указатель на узел дерева равен NULL, функция просто возвращает управление.
  2. Функция выводит значение узла (data) и переходит к следующему узлу.
  3. Если у текущего узла есть левое поддерево (leftPtr), функция сначала выводит горизонтальную линию, затем символ L: и координаты этой линии, затем вызывает себя для левого поддерева.
  4. Если у текущего узла есть правое поддерево (rightPtr), функция выводит горизонтальную линию, затем символ R: и координаты этой линии, затем вызывает себя для правого поддерева.
  5. Если у текущего узла нет ни левого, ни правого поддерева, функция просто переходит к следующему узлу. Список функций, используемых в коде:
  6. insertNode: Вставляет новый узел в дерево. Если дерево пусто, новый узел становится корнем. Если узел с таким значением уже существует, вставка не происходит.
  7. inOrder: Обход дерева в порядке возрастания. Рекурсивная функция.
  8. printTree: Выводит дерево в отступе. Рекурсивная функция.
  9. showLine: Выводит горизонтальную линию и символы L: и R: с отступами.
  10. showTree: Выводит дерево в отстуде. Рекурсивная функция. Список переменных, используемых в коде:
  11. main: главная функция программы
  12. i, item: используются для итерации по массиву чисел, которые нужно вставить в дерево
  13. rootPtr: указатель на корень дерева
  14. srand, time(NULL): используются для инициализации генератора случайных чисел
  15. treeNode, TREENODE, treeNodePTR, TREENODEPTR: типы данных и указатели на структуру узла дерева
  16. insertNode, inOrder, printTree, showTree: функции, используемые для работы с деревом
  17. p, item, wood: используются в функции showTree для итерации по дереву и вывода значений узлов.

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.364 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы