Advertisement
ltdpaste

Continue Binary Tree

Jun 1st, 2019
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. typedef struct Node
  7. {
  8.     int data;
  9.     struct Node* pLeft;
  10.     struct Node* pRight;
  11. }NODE;
  12. typedef NODE* TREE;
  13.  
  14. void Init(TREE& t)
  15. {
  16.     t = NULL;
  17. }
  18.  
  19. bool is_Empty(TREE t)
  20. {
  21.     if (t == NULL)
  22.         return true;
  23.     return false;
  24. }
  25.  
  26. NODE* GetNode(int value)
  27. {
  28.     NODE* p = new NODE;
  29.     if (p == NULL)
  30.         return NULL;
  31.     p->data = value;
  32.     p->pLeft = p->pRight = NULL;
  33.     return p;
  34. }
  35.  
  36. void InsertNode(TREE& t, NODE *p)
  37. {
  38.     if (t == NULL)
  39.     {
  40.         t = p;
  41.     }
  42.     else
  43.     {
  44.         if (t->data > p->data)
  45.         {
  46.             InsertNode(t->pLeft, p);
  47.         }          
  48.         else
  49.         {
  50.             InsertNode(t->pRight, p);
  51.         }
  52.     }
  53. }
  54.  
  55. NODE* SearchNode(TREE t, int value)
  56. {
  57.     if (t == NULL)
  58.     {
  59.         return NULL;
  60.     }
  61.     if (t->data == value)
  62.         return t;
  63.     else
  64.     {
  65.         if (t->data > value)
  66.             return SearchNode(t->pLeft, value);
  67.         else
  68.         {
  69.             return SearchNode(t->pRight, value);
  70.         }
  71.     }
  72. }
  73.  
  74. void ReplaceNode(TREE &p , TREE &q)
  75. {
  76.     if (p->pLeft == NULL)
  77.     {
  78.         ReplaceNode(p, q->pLeft);
  79.     }
  80.     else
  81.     {
  82.         p->data = q->data;
  83.         p = q;
  84.         q = q->pRight;
  85.     }
  86. }
  87. void DeleteNode(TREE& t, int value)
  88. {
  89.     if (t == NULL)
  90.         return;
  91.     if (t->data > value)
  92.         DeleteNode(t->pLeft, value);
  93.     if (t->data < value)
  94.         DeleteNode(t->pRight, value);
  95.     else
  96.     {
  97.         NODE* p = t;
  98.         if (t->pLeft == NULL)
  99.             t = t->pRight;
  100.         else
  101.         {
  102.             if (t->pRight == NULL)
  103.                 t = t->pLeft;
  104.             else
  105.             {
  106.                 NODE* q = t->pRight;
  107.                 ReplaceNode(p, q); 
  108.             }
  109.         }
  110.     }
  111. }
  112.  
  113. void Input(const char* fileinp, TREE& t)
  114. {
  115.     ifstream inp;
  116.     inp.open(fileinp);
  117.     if (!inp.is_open())
  118.     {
  119.         cout << "ERROR: Can not open the file to read data.";
  120.     }
  121.     else
  122.     {
  123.         int x;
  124.         while (inp >> x)
  125.         {
  126.             InsertNode(t, GetNode(x));
  127.         }
  128.     }
  129. }
  130.  
  131. void LNR_to_array(TREE t, int a[], int &i)
  132. {
  133.     if (t != NULL)
  134.     {
  135.         LNR_to_array(t->pLeft, a, i);
  136.         a[i] = t->data;
  137.         i++;
  138.         LNR_to_array(t->pRight, a, i);
  139.     }
  140. }
  141.  
  142. void Output(const char* fileout, TREE t)
  143. {
  144.     ofstream out;
  145.     out.open(fileout);
  146.     if (!out.is_open())
  147.     {
  148.         cout << "ERROR: Can not open the file to write data.";
  149.     }
  150.     else
  151.     {
  152.         int a[100];
  153.         int i = 0;
  154.         LNR_to_array(t, a, i);
  155.         for (int j = 0; j < i; j++)
  156.         {
  157.             if (j != i - 1)
  158.                 out << a[j] << " ";
  159.             else
  160.             {
  161.                 out << a[j];
  162.             }
  163.         }
  164.     }
  165. }
  166. int main()
  167. {
  168.     TREE t;
  169.     Init(t);
  170.     Input("data.txt", t);
  171.     Output("output.txt", t);
  172.     cout << SearchNode(t, 86)->data;
  173.     return 0;
  174. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement