SHARE
TWEET

Binary tree V1.0

DarkDevourer Feb 27th, 2020 (edited) 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #include <math.h>
  5.  
  6. struct bi_tree // Структура элемента бинарного дерева
  7. {
  8.     struct tree *left; //Указатель на левый узел
  9.     int key; //Ключ в узле дерева
  10.     struct tree *right; //Указатель на правый узел
  11. }bi_tree, *ptr, *ptr1, *root; //Название структуры, два указателя и указатель на корень
  12.  
  13. void TreeCreation(int *tree_exists); //Создание бинарного дерева
  14.  
  15. void ElementSearch(int *tree_exists); //Поиск конкретного ключа
  16.  
  17. void AddingElement(int *tree_exists); //Добавление узла
  18.  
  19. void Bypass(struct bi_tree *root1); //Прямой обход дерева
  20.  
  21. void SearchMax(int *tree_exists); //Поиск наибольшего элемента
  22.  
  23. void DeleteElement(int *tree_exists); //Удаление узла дерева без дочерних узлов
  24.  
  25. void printTree(struct bi_tree *treePtr, int s);
  26.  
  27. void main()
  28. {
  29.     int chs;
  30.     int tree_exists = 0; //Флаг, сообщающий о наличии или отсутствии дерева. 0 - дерева нет, 1 - дерево есть
  31.     while (1) //Цикл меню
  32.     {
  33.         printf("Choose function.\n1 - create tree.\n2 - searching key.\n3 - adding new element.\n4 - direct bypass.\n5 - searching max element\n6 - delete one element without any descendants.\n7 - print tree.\n0 - exit.\n");
  34.         scanf("%d", &chs); //Ввод клавиши действия
  35.         switch (chs)
  36.         {
  37.         case 1: //Создание бинарного дерева
  38.         {
  39.             TreeCreation(&tree_exists);
  40.             break;
  41.         }
  42.         case 2: //Поиск конкретного ключа
  43.         {
  44.             ElementSearch(&tree_exists);
  45.             break;
  46.         }
  47.         case 3: //Добавление узла
  48.         {
  49.             AddingElement(&tree_exists);
  50.             break;
  51.         }
  52.         case 4: //Прямой обход дерева
  53.         {
  54.             if (tree_exists == 1) //Если дерево создано - выполнить обход
  55.             {
  56.                 Bypass(root);
  57.                 printf("\n");
  58.                 break;
  59.             }
  60.             else if (tree_exists == 0) //Если дерево не создано - сообщить об этом
  61.             {
  62.                 printf("Binary tree doesn't exist. Please create it.");
  63.             }
  64.         }
  65.         case 5: //Поиск наибольшего элемента
  66.         {
  67.             SearchMax(&tree_exists);
  68.             break;
  69.         }
  70.         case 6: //Удаление узла дерева без дочерних узлов
  71.         {
  72.             DeleteElement(&tree_exists);
  73.             break;
  74.         }
  75.         case 7:
  76.         {
  77.             if (tree_exists == 1) //Если дерево создано - выполнить обход
  78.             {
  79.                 int s = 0;
  80.                 printf("\n\n\n\n\n\nTree:\n");
  81.                 printTree(root, s);
  82.                 break;
  83.             }
  84.             else if (tree_exists == 0) //Если дерево не создано - сообщить об этом
  85.             {
  86.                 printf("Binary tree doesn't exist. Please create it.");
  87.             }
  88.         }
  89.         case 0: //Выход из программы
  90.         {
  91.             printf("Exiting program.\n"); //Выход из программы
  92.             break;
  93.         }
  94.         default: //Если выбранной команды не существует
  95.         {
  96.             printf("This feature doesn't exist. Please try again.\n");
  97.             break;
  98.         }
  99.         }
  100.         if (chs == 0)
  101.             break;
  102.     }
  103. }
  104.  
  105.  
  106. void TreeCreation(int *tree_exists) //Создание бинарного дерева
  107. {
  108.     FILE *in;
  109.     int i;
  110.     int temp;
  111.     if (*tree_exists == 1) //Если дерево существует - об этом сообщается
  112.     {
  113.         printf("Tree is already created. Please delete it before.\n");
  114.     }
  115.     else //Иначе
  116.     {
  117.         in = fopen("C:\\test\\SiAODlab5Input.txt", "rt"); //Открываем файл с целочисленной числовой последовательностью в режиме чтения
  118.         if (in == NULL) //Если файл открыть не удалось - выводится сообщение об этом
  119.         {
  120.             printf("Initial file wasn't opened.\n");
  121.             return -1;
  122.         }
  123.         root = malloc(sizeof(struct bi_tree)); //Выделение памяти под корень
  124.         root->left = NULL; //Обнуление указателя на левый потомок
  125.         root->right = NULL; //Обнуление указателя на правый потомок
  126.         fscanf(in, "%d", &temp); //Ввод ключа узла дерева в переменную временного хранения
  127.         root->key = temp; //Запись ключа в узел
  128.         for (i = 1; i < 25; i++) //Создание остальных 24 элементов дерева
  129.         {
  130.             ptr = malloc(sizeof(struct bi_tree)); //Выделение памяти под узел
  131.             ptr->left = NULL; //Обнуление указателя на левый потомок
  132.             ptr->right = NULL; //Обнуление указателя на правый потомок
  133.             fscanf(in, "%d", &temp); //Ввод ключа узла дерева в переменную временного хранения
  134.             ptr->key = temp; //Запись ключа в узел
  135.             ptr1 = root; //Переходим к корню дерева
  136.             while (1)
  137.             {
  138.                 if (ptr1->key > ptr->key) //Ключ просматриваемого узла больше ключа добавляемого узла? Если да:
  139.                 {
  140.                     if (ptr1->left == NULL) //Если левый потомок не существует (проверяется путем проверки равности NULL указателя на левый потомок)
  141.                     {
  142.                         ptr1->left = ptr; //Добавляемый узел становится левым потомком просматриваемого сейчас узла
  143.                         break;
  144.                     }
  145.                     else //Иначе
  146.                     {
  147.                         ptr1 = ptr1->left; //Переходим в левый потомок
  148.                     }
  149.                 }
  150.                 else if (ptr1->key < ptr->key) //Если нет: ключ просматриваемого узла меньше ключа добавляемого узла? Если да:
  151.                 {
  152.                     if (ptr1->right == NULL) //Если правый потомок не существует (проверяется путем проверки равности NULL указателя на правый потомок)
  153.                     {
  154.                         ptr1->right = ptr; //Добавляемый узел становится правым потомком просматриваемого сейчас узла
  155.                         break;
  156.                     }
  157.                     else //Иначе
  158.                     {
  159.                         ptr1 = ptr1->right; //Переходим в правый потомок
  160.                     }
  161.                 }
  162.             }
  163.         }
  164.         printf("Binary tree was successfully created.\n"); //Вывод сообщения об успешном создании дерева
  165.         *tree_exists = 1; //Флаг мпереходит в состояние 1
  166.         fclose(in); //Закрытие файла
  167.     }
  168. }
  169.  
  170. void ElementSearch(int *tree_exists) //Поиск конкретного ключа
  171. {
  172.     int skey;
  173.     int search = 0;
  174.     if (*tree_exists == 0) //Если дерево не создано - сообщаем об этом
  175.     {
  176.         printf("Binary tree doesn't exist. Please create it.");
  177.     }
  178.     else //Иначе
  179.     {
  180.         printf("Enter the key for searching.\n");
  181.         scanf("%d", &skey); //Вводим искомый ключ
  182.         ptr = root; //Переходим к корню дерева
  183.         while (1)
  184.         {
  185.             if (skey == ptr->key) //Если ключ найден - выводим сообщение об этом, на какой стороне относительно корня находится ключ, и информацию о ево потомках
  186.             {
  187.                 printf("Key %d was found. It is on the", skey);
  188.                 if (skey < root->key)
  189.                 {
  190.                     printf(" left ");
  191.                 }
  192.                 else
  193.                 {
  194.                     printf(" right ");
  195.                 }
  196.                 printf("of the root.");
  197.                 printf(" Left descendant is");
  198.                 if (ptr->left == NULL)
  199.                 {
  200.                     printf(" not exist "); //Если левого потомка нет - выводим сообщение об этом
  201.                 }
  202.                 else
  203.                 {
  204.                     ptr1 = ptr->left;
  205.                     printf(" %d ", ptr1->key); //Иначе - выводим его ключ
  206.                 }
  207.                 printf("and right descendant is");
  208.                 if (ptr->right == NULL)
  209.                 {
  210.                     printf(" not exist.\n"); //Если правого потомка нет - выводим сообщение об этом
  211.                 }
  212.                 else
  213.                 {
  214.                     ptr1 = ptr->right;
  215.                     printf(" %d.\n", ptr1->key); //Иначе - выводим его ключ
  216.                 }
  217.                 search = 1;
  218.                 break;
  219.             }
  220.             else if (skey < ptr->key) //Если ключ меньше проверяемого узла, переходим в левый потомок
  221.             {
  222.                 if (ptr->left != NULL)
  223.                     (ptr = ptr->left);
  224.                 else
  225.                     break;
  226.  
  227.             }
  228.             else if (skey > ptr->key) //Если ключ больше проверяемого узла, переходим в правый потомок
  229.             {
  230.                 if (ptr->right != NULL)
  231.                     (ptr = ptr->right);
  232.                 else
  233.                     break;
  234.             }
  235.         }
  236.         if (search == 0)
  237.         {
  238.             printf("Key wasn't found. It's not an element of tree.\n");
  239.         }
  240.     }
  241. }
  242.  
  243. void AddingElement(int *tree_exists) //Добавления узла
  244. {
  245.     int new;
  246.     if (*tree_exists == 0) //Если дерево не создано - сообщаем об этом
  247.     {
  248.         printf("Binary tree doesn't exist. Please create it.");
  249.     }
  250.     else //Иначе
  251.     {
  252.         printf("Enter new element.\n");
  253.         scanf("%d", &new); //Вводим значение ключа нового узла
  254.         ptr = malloc(sizeof(struct bi_tree)); //Выделение памяти под узел
  255.         ptr->left = NULL; //Обнуление указателя на левый потомок
  256.         ptr->right = NULL; //Обнуление указателя на правый потомок
  257.         ptr->key = new; //Запись данных в узел
  258.         ptr1 = root; //Переходим к корню дерева
  259.         while (1)
  260.         {
  261.             if (ptr->key > ptr1->key) //Ключ просматриваемого узла больше ключа добавляемого узла? Если да:
  262.             {
  263.                 if (ptr1->right == NULL) //Если левый потомок не существует (проверяется путем проверки равности NULL указателя на левый потомок)
  264.                 {
  265.                     ptr1->right = ptr; //Добавляемый узел становится левым потомком просматриваемого сейчас узла
  266.                     printf("Element was successfully added.\n");
  267.                     break;
  268.                 }
  269.                 else //Иначе
  270.                     ptr1 = ptr1->right; //Переходим в левый потомок
  271.             }
  272.             else if (ptr->key < ptr1->key) //Ключ просматриваемого узла меньше ключа добавляемого узла? Если да:
  273.             {
  274.                 if (ptr1->left == NULL) //Если правый потомок не существует (проверяется путем проверки равности NULL указателя на правый потомок)
  275.                 {
  276.                     ptr1->left = ptr; //Добавляемый узел становится правым потомком просматриваемого сейчас узла
  277.                     printf("Element was successfully added.\n");
  278.                     break;
  279.                 }
  280.                 else //Иначе
  281.                     ptr1 = ptr1->left; //Переходим в правый потомок
  282.             }
  283.             else if (ptr1->key == ptr->key) //Если найден такой же ключ - вывод сообщение об этом
  284.             {
  285.                 printf("This element is already part of tree. Add another element.\n");
  286.                 break;
  287.             }
  288.         }
  289.     }
  290. }
  291.  
  292. void Bypass(struct bi_tree* root1) //Прямой обход дерева
  293. {
  294.     if (root1) //Начиная с корня, проходим по всем узлам
  295.     {
  296.         printf("%d ", root1->key); //Выводим ключ текущего проверяемого узла
  297.         Bypass(root1->left); //Проходим через все левые поддеревья данного узла
  298.         Bypass(root1->right); //Проходим через все правые поддеревья данного узла
  299.     }
  300. }
  301.  
  302. void SearchMax(int *tree_exists)  //Поиск наибольшего элемента
  303. {
  304.     if (*tree_exists == 0) //Если дерево не создано - сообщаем об этом
  305.     {
  306.         printf("Binary tree doesn't exist. Please create it.");
  307.     }
  308.     else
  309.     {
  310.         ptr = root; //Переходим к корню дерева
  311.         while (1)
  312.         {
  313.             if (ptr->right != NULL) //До тех пор, пока указатель на правого потомка не станет равен NULL, переходим в правого потомка.
  314.                 ptr = ptr->right;
  315.             else //Узел с указателем на правого потомка, равным NULL, и будет наибольшим элементом дерева
  316.             {
  317.                 printf("Max element of binary tree is %d.\n", ptr->key);
  318.                 break;
  319.             }
  320.         }
  321.     }
  322. }
  323.  
  324. void DeleteElement(int *tree_exists) //Удаление узла дерева без дочерних узлов
  325. {
  326.     if (*tree_exists == 0) //Если дерево не создано - сообщаем об этом
  327.     {
  328.         printf("Binary tree doesn't exist. Please create it.");
  329.     }
  330.     else
  331.     {
  332.         int l_r = 0;
  333.         if (root->left == NULL && root->right == NULL) //Если потомки у корня отсутствуют - удаляем его и,как следствие, дерево
  334.         {
  335.             printf("Root was the last element of the tree. Tree was deleted.\n");
  336.             *tree_exists = 0; //Флаг существования дерева переводим в 0
  337.             ptr = NULL;
  338.             ptr1 = NULL;
  339.             free(root);
  340.         }
  341.         else
  342.         {
  343.             ptr = root;
  344.             while (1)
  345.             {
  346.                 if (ptr->left != NULL) //Перемещаемся в левый потомок в случае его наличия
  347.                 {
  348.                     ptr1 = ptr;
  349.                     ptr = ptr1->left;
  350.                     l_r = 0;
  351.                 }
  352.                 else if (ptr->right != NULL) //В случае наличия правого потомка и отсутствия левого потомка, перемещаемся в потомок потомок
  353.                 {
  354.                     ptr1 = ptr;
  355.                     ptr = ptr1->right;
  356.                     l_r = 1;
  357.                 }
  358.                 else
  359.                     break;
  360.             }
  361.             if (l_r == 0) //Если удаляемый узел - левый потомок своего предка, очищаем указатель на левый потомок предка и удаляем узел
  362.             {
  363.                 ptr1->left = NULL;
  364.                 free(ptr);
  365.                 printf("Element was successfully deleted.\n");
  366.             }
  367.             else //Если удаляемый узел - правый потомок своего предка, очищаем указатель на правый потомок предка и удаляем узел
  368.             {
  369.                 ptr1->right = NULL;
  370.                 free(ptr);
  371.                 printf("Element was successfully deleted.\n");
  372.             }
  373.         }
  374.     }
  375. }
  376.  
  377. void printTree(struct bi_tree *treePtr, int s)
  378. {
  379.     int i;
  380.     if (treePtr != NULL)
  381.     {
  382.         printTree(treePtr->right, s + 3);
  383.         for (i = 0; i < s; i++)
  384.         {
  385.             printf(" ");
  386.         }
  387.         printf("%3d\n", treePtr->key);
  388.         printTree(treePtr->left, s + 3);
  389.     }
  390. }
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