SHARE
TWEET

Untitled

a guest Jun 20th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // TreeHeader.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
  2. //
  3.  
  4. #include "pch.h"
  5. #define _CRT_SECURE_NO_WARNINGS
  6. #define MAX_OFFSET_SIZE 100
  7. #define OFFSET_BETWEEN_ONE_PARENT_SIBLINGS 15
  8. #define OFFSET_BETWEEN_SIBLINGS 30
  9. #define OFFSET_DELTA 15
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12.  
  13.  
  14. struct Tnode {
  15.     int value;
  16.     int id;
  17.     Tnode* leftSibling;
  18.     Tnode* rightSibling;
  19.     Tnode* leftChild;
  20.     Tnode* parent;
  21. };
  22.  
  23. Tnode* findLastChild(Tnode* parent) {
  24.     Tnode* child = parent->leftChild;
  25.     while (child->rightSibling != NULL)
  26.     {
  27.         child = child->rightSibling;
  28.     }
  29.     return child;
  30. }
  31.  
  32.  
  33. void findNodeWithId(Tnode* firstNode, int id, Tnode** resultNode) {
  34.     if (firstNode != NULL)
  35.     {
  36.         if (firstNode->id == id)
  37.         {
  38.             *resultNode = firstNode;
  39.  
  40.         }
  41.     }
  42.     Tnode* thisNode = firstNode->leftChild;
  43.     if (thisNode != NULL) {
  44.         while (thisNode != NULL) {
  45.             findNodeWithId(thisNode, id, resultNode);
  46.             thisNode = thisNode->rightSibling;
  47.         }
  48.     }
  49.  
  50. }
  51.  
  52. struct Tnode* addNodeToTree(Tnode* root, int parentId, int value, int id) {
  53.  
  54.     if (parentId == -1) {
  55.         struct Tnode* node = (struct Tnode*)malloc(sizeof(struct Tnode));
  56.         node->value = value;
  57.         node->id =id;
  58.         node->parent = NULL;
  59.         node->rightSibling = NULL;
  60.         node->leftSibling = NULL;
  61.         node->leftChild = NULL;
  62.         return node;
  63.     }
  64.     else {
  65.         Tnode* parent = NULL;
  66.         Tnode** resultS = &parent;
  67.         findNodeWithId(root, parentId, resultS);
  68.         struct Tnode* child = (struct Tnode*)malloc(sizeof(struct Tnode));
  69.         if (parent->leftChild!=NULL)
  70.         {
  71.             Tnode* lastChild = findLastChild(parent);
  72.             lastChild->rightSibling = child;
  73.             child->leftSibling = lastChild;
  74.             child->parent = parent;
  75.             child->value = value;
  76.             child->leftChild = NULL;
  77.             child->rightSibling = NULL;
  78.             child->id = id;
  79.             return child;
  80.         }
  81.         else {
  82.             parent->leftChild = child;
  83.             child->value = value;
  84.             child->id = id;
  85.             child->leftSibling = NULL;
  86.             child->parent = parent;
  87.             child->leftChild = NULL;
  88.             child->rightSibling = NULL;
  89.             return child;
  90.         }
  91.  
  92.     }
  93.  
  94.  
  95. }
  96.  
  97.  
  98. int findDegree(Tnode* node) {
  99.     int degree = 0;
  100.     Tnode* currentNode = node->leftChild;
  101.     while (currentNode != NULL)
  102.     {
  103.         currentNode = currentNode->rightSibling;
  104.         ++degree;
  105.  
  106.     }
  107.     return degree;
  108. }
  109.  
  110.  
  111. void deleteLeaf(Tnode* node) {
  112.     if (node->parent != NULL)
  113.     {
  114.         if (node->parent->leftChild == node && node->rightSibling != NULL) {
  115.             node->parent->leftChild = node->rightSibling;
  116.         }
  117.         if (node->parent->leftChild == node && node->rightSibling == NULL) {
  118.             node->parent->leftChild = NULL;
  119.         }
  120.     }
  121.     if (node->rightSibling != NULL)
  122.     {
  123.         node->rightSibling->leftSibling = NULL;
  124.     }
  125.  
  126.     if (node->leftSibling != NULL && node->rightSibling != NULL)
  127.     {
  128.         node->leftSibling->rightSibling = node->rightSibling;
  129.         node->leftSibling = node->rightSibling->leftSibling;
  130.     }
  131.     if (node->leftSibling != NULL && node->rightSibling == NULL)
  132.     {
  133.         node->leftSibling->rightSibling = NULL;
  134.     }
  135.     free(node);
  136.  
  137. }
  138.  
  139.  
  140.  
  141.  
  142. void deleteNode(Tnode* node) {
  143.     if (node->parent != NULL)
  144.     {
  145.         if (node->parent->leftChild == node && node->rightSibling != NULL) {
  146.             node->parent->leftChild = node->rightSibling;
  147.         }
  148.         if (node->parent->leftChild == node && node->rightSibling == NULL) {
  149.             node->parent->leftChild = NULL;
  150.         }
  151.     }
  152.     if (node->leftSibling != NULL && node->rightSibling != NULL)
  153.     {
  154.         node->leftSibling->rightSibling = node->rightSibling;
  155.         node->leftSibling = node->rightSibling->leftSibling;
  156.     }
  157.     if (node->leftSibling != NULL && node->rightSibling == NULL)
  158.     {
  159.         node->leftSibling->rightSibling = NULL;
  160.     }
  161.     if (node->rightSibling != NULL)
  162.     {
  163.         node->rightSibling->leftSibling = NULL;
  164.     }
  165.     if (node->leftChild == NULL) {
  166.         if (node->rightSibling != NULL) {
  167.             deleteNode(node->rightSibling);
  168.             node->rightSibling = NULL;
  169.         }
  170.        
  171.         free(node);
  172.     }
  173.     else
  174.     {
  175.         if (node->rightSibling != NULL) {
  176.             deleteNode(node->rightSibling);
  177.         }
  178.         deleteNode(node->leftChild);
  179.        
  180.         free(node);
  181.     }
  182.    
  183.  
  184. }
  185.  
  186. char* makeOffsetStr(int offset) {
  187.     char arr[512];
  188.     _itoa(offset, arr, 10);
  189.     char result[1024];
  190.     snprintf(result, sizeof  result, "%s%s%s", "%", arr, "s");
  191.     return result;
  192. }
  193.  
  194.  
  195.  
  196. void traverseTree(Tnode* root) {
  197.     Tnode* thisNode = root->leftChild;
  198.     if (thisNode != NULL) {
  199.         while (thisNode != NULL) {
  200.             printf("%d\n", thisNode->id);
  201.             traverseTree(thisNode);
  202.             thisNode = thisNode->rightSibling;
  203.         }
  204.     }
  205.  
  206. }
  207.  
  208.  
  209. void printTree(Tnode* root,int offset,int offsetDelta) {
  210.     int thisOffset = offset;
  211.     if (root->id == 0) {
  212.         thisOffset += offsetDelta;
  213.         printf(makeOffsetStr(offset), "");
  214.         printf("%s%d%s%d%s\n", "(", root->id, ":", root->value, ")");
  215.     }
  216.     Tnode* thisNode = root->leftChild;
  217.     if (thisNode != NULL) {
  218.         while (thisNode != NULL) {
  219.             printf(makeOffsetStr(thisOffset), "");
  220.             printf("%s%d%s%d%s\n","(", thisNode->id,":",thisNode->value,")");
  221.             printTree(thisNode,thisOffset +offsetDelta, offsetDelta);
  222.             thisNode = thisNode->rightSibling;
  223.         }
  224.     }
  225.  
  226. }
  227.  
  228.  
  229.  
  230.  
  231. int isNodeALeaf(Tnode* node) {
  232.     if (node->leftChild!=NULL)
  233.     {
  234.         return 0;
  235.     }
  236.     else {
  237.         return 1;
  238.     }
  239. }
  240.  
  241.  
  242. void menu() {
  243.     printf("---MENU-------\n");
  244.     printf("a - add node\n");
  245.     printf("v - view tree \n");
  246.     printf("d - del node\n");
  247.     printf("f - find node degree \n");
  248.     printf("q - exit      \n");
  249. }
  250.  
  251. int main()
  252. {
  253.     int id = 0;
  254.     Tnode* root =NULL;
  255.     Tnode* result = NULL;
  256.    
  257.     //++id;
  258.     menu();
  259.     while (1) {
  260.         char typ;
  261.         printf("type command\n");
  262.         scanf(" %c", &typ);
  263.         switch (typ) {
  264.             int val;
  265.         case 'a':
  266.             int value;
  267.             printf("type parent id and value, if you want to add root type -1 and value:\n");
  268.             scanf("%d%d", &val, &value);
  269.            
  270.             if (val == -1) {
  271.                 root = addNodeToTree(NULL, val, value, id);
  272.             }
  273.             else {
  274.                 addNodeToTree(root, val, value, id);
  275.             }
  276.             ++id;
  277.            
  278.             break;
  279.         case 'v':
  280.             printf("each vertex is in format (id:value)\n");
  281.             printTree(root, 0, OFFSET_DELTA);
  282.             break;
  283.         case 'd':
  284.             printf("type node id:\n");
  285.             scanf("%d", &val);
  286.             findNodeWithId(root, val, &result);
  287.             if (isNodeALeaf(result)) {
  288.                 deleteLeaf(result);
  289.             }
  290.             else {
  291.                 deleteNode(result);
  292.             }
  293.             break;
  294.         case 'f':
  295.             printf("type node id\n");
  296.             scanf("%d", &val);
  297.             findNodeWithId(root, val, &result);
  298.             printf("%d\n",findDegree(result));
  299.             break;
  300.         case 'q':
  301.             exit(0);
  302.             break;
  303.         case '?':
  304.             menu();
  305.             break;
  306.         default:
  307.             printf("Wrong value\n");
  308.             break;
  309.         }
  310.     }
  311.    
  312. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top