Advertisement
huutho_96

Cây BST

Jun 18th, 2016
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <conio.h>
  4.  
  5. using namespace std;
  6. struct TreeNode
  7. {
  8.     int key;
  9.     int value;
  10.     TreeNode *pLeft, *pRight;
  11. };
  12. typedef TreeNode* TREE;
  13. void CreateTree(TREE &Root)
  14. {
  15.     Root = NULL;
  16. }
  17. int InsertNode(TREE &Root, int key)
  18. {
  19.     if (Root)
  20.     {
  21.         if (Root->key == key)
  22.         {
  23.             Root->value++;
  24.             return 0;
  25.         }
  26.         if (Root->key > key) return InsertNode(Root->pLeft, key);
  27.         return InsertNode(Root->pRight, key);
  28.     }
  29.     TreeNode *p = new TreeNode;
  30.     if (p == NULL) return -1;
  31.     p->pLeft = p->pRight = NULL;
  32.     p->key = key;
  33.     p->value = 1;
  34.     Root = p;
  35.     return 1;
  36. }
  37. void NLR(TREE Root)
  38. {
  39.     if (Root)
  40.     {
  41.         cout << Root->key << endl;
  42.         NLR(Root->pLeft);
  43.         NLR(Root->pRight);
  44.     }
  45. }
  46. void LNR(TREE Root)
  47. {
  48.     if (Root)
  49.     {
  50.         LNR(Root->pLeft);
  51.         cout << Root->key << endl;
  52.         LNR(Root->pRight);
  53.     }
  54. }
  55. void LRN(TREE Root)
  56. {
  57.     if (Root)
  58.     {
  59.         LRN(Root->pLeft);
  60.         LRN(Root->pRight);
  61.         cout << Root->key << endl;
  62.     }
  63. }
  64. int SearchNode(TREE Root, int key)
  65. {
  66.     if (Root)
  67.     {
  68.         if (Root->key == key)
  69.             return 1;
  70.         if (Root->key > key) return SearchNode(Root->pLeft, key);
  71.         return SearchNode(Root->pRight, key);
  72.     }
  73.     return 0;
  74. }
  75. void DeleteTree(TREE &Root)
  76. {
  77.     if (Root)
  78.     {
  79.         DeleteTree(Root->pLeft);
  80.         DeleteTree(Root->pRight);
  81.         delete Root;
  82.     }
  83.     Root = NULL;
  84. }
  85. void CopyTree(TREE Root1, TREE &Root2)
  86. {
  87.     if (Root1)
  88.     {
  89.         TreeNode * p = new TreeNode;
  90.         if (p == NULL) exit(1);
  91.         p->pLeft = p->pRight = NULL;
  92.         p->key = Root1->key;
  93.         p->value = Root1->value;
  94.         Root2 = p;
  95.         CopyTree(Root1->pLeft, Root2->pLeft);
  96.         CopyTree(Root1->pRight, Root2->pRight);
  97.     }
  98. }
  99. void Output(TREE R)
  100. {
  101.     if (R)
  102.     {
  103.         Output(R->pRight);
  104.         cout << R->key << "\tXuat hien: " << R->value << endl;
  105.         Output(R->pLeft);
  106.     }
  107. }
  108. int Height(TREE Root)
  109. {
  110.     if (!Root)
  111.         return 0;
  112.     int a = Height(Root->pLeft);
  113.     int b = Height(Root->pRight);
  114.     if (a > b) return (a + 1);
  115.     else return (b + 1);
  116. }
  117. int DemNode(TREE Root)
  118. {
  119.     if (Root == NULL)
  120.         return 0;
  121.     return (1 + DemNode(Root->pLeft) + DemNode(Root->pRight));
  122. }
  123. void DemLa(TREE Root, int &count)
  124. {
  125.     if (Root)
  126.     {
  127.         if (Root->pLeft == NULL && Root->pRight == NULL) count++;
  128.         DemLa(Root->pLeft, count);
  129.         DemLa(Root->pRight, count);
  130.     }
  131. }
  132. void DemNode1CayCon(TREE Root, int &count)
  133. {
  134.     if (Root)
  135.     {
  136.         if (Root->pLeft != Root->pRight && (Root->pRight == NULL || Root->pLeft == NULL)) count++;
  137.         DemNode1CayCon(Root->pLeft, count);
  138.         DemNode1CayCon(Root->pRight, count);
  139.     }
  140. }
  141. void DemNode2CayCon(TREE Root, int &count)
  142. {
  143.     if (Root)
  144.     {
  145.         if (Root->pRight != NULL && Root->pLeft != NULL) count++;
  146.         DemNode2CayCon(Root->pLeft, count);
  147.         DemNode2CayCon(Root->pRight, count);
  148.     }
  149. }
  150. void DemNode_Muc(TREE Root, int muc, int &count)
  151. {
  152.     if (Root)
  153.     {
  154.         if (Height(Root) == muc) count++;
  155.         DemNode_Muc(Root->pLeft, muc, count);
  156.         DemNode_Muc(Root->pRight, muc, count);
  157.     }
  158. }
  159. int SNT(int n)
  160. {
  161.     if (n < 2) return 0;
  162.     for (int i = 2; i * i <= n; i++)
  163.         if (n % i == 0) return 0;
  164.     return 1;
  165. }
  166. void Dem_SNT(TREE Root, int &count)
  167. {
  168.     if (Root)
  169.     {
  170.         if (SNT(Root->key)) count++;
  171.         Dem_SNT(Root, count);
  172.         Dem_SNT(Root, count);
  173.     }
  174. }
  175. void MackDeletion(TREE &Root)
  176. {
  177.     TreeNode *p = Root;
  178.     if (Root->pLeft == NULL && Root->pRight == NULL)
  179.     {
  180.         Root = NULL;
  181.         delete p;
  182.         return;
  183.     }
  184.     if (Root->pLeft == NULL)
  185.     {
  186.         Root = p->pRight;
  187.         delete p;
  188.         return;
  189.     }
  190.     if (Root->pRight == NULL)
  191.     {
  192.         Root = p->pLeft;
  193.         delete p;
  194.         return;
  195.     }
  196.     TreeNode *pPtr = Root->pRight;
  197.     while (pPtr->pLeft) pPtr = pPtr->pLeft;
  198.     pPtr->pLeft = p->pLeft;
  199.     Root = p->pRight;
  200.     delete p;
  201.  
  202. }
  203. int Deletenode(TREE &Root, int x)
  204. {
  205.     if (Root)
  206.     {
  207.         if (Root->key == x)
  208.         {
  209.             MackDeletion(Root);
  210.             return 1;
  211.         }
  212.         if (Root->key > x) return Deletenode(Root->pLeft, x);
  213.         return Deletenode(Root->pRight, x);
  214.     }
  215.     return 0;
  216. }
  217. void Input(TREE &Root)
  218. {
  219.     int x;
  220.     do
  221.     {
  222.         cout << "Nhap x = 0 de thoat nhap:  x = ";
  223.         cin >> x;
  224.         if (x == 0) break;
  225.         InsertNode(Root, x);
  226.     } while (1);
  227. }
  228. void DuyetTheoMuc(TREE &Root)
  229. {
  230.     TREE p = Root;
  231.     queue<TREE> q;
  232.     if (Root == NULL) return;
  233.     q.push(p);
  234.     while (!q.empty())
  235.     {
  236.         p = q.front();
  237.         q.pop();
  238.         cout << p->key << "\t";
  239.         if (p->pLeft) q.push(p->pLeft);
  240.         if (p->pRight) q.push(p->pRight);
  241.     }
  242. }
  243.  
  244. void menu()
  245. {
  246.     system("cls");
  247.     cout << "1.\t Duyet cay" << endl;
  248.     cout << "2.\t Chen Node" << endl;
  249.     cout << "3.\t Xoa Node" << endl;
  250.     cout << "4.\t Dem Node" << endl;
  251.     cout << "5.\t So lan xuat hien khi chen" << endl;
  252.     cout << "6.\t Chieu cao cay" << endl;
  253.     cout << "7.\t Copy cay" << endl;
  254.     cout << "8.\t Xoa cay" << endl;
  255.     cout << "9.\t Tim Node" << endl;
  256.     cout << "10.\t Nhap cay" << endl;
  257.     cout << "0.\t Thoat" << endl;
  258.     cout << "Lua Chon: ";
  259. }
  260. void main()
  261. {
  262.     TREE Root;
  263.     CreateTree(Root);
  264.     int x;
  265.     int Value;
  266.     int dem = 0;
  267.     do
  268.     {
  269.         menu();
  270.         cin >> x;
  271.         switch (x)
  272.         {
  273.         case 1:
  274.             system("cls");
  275.             cout << "LNR:\n";
  276.             LNR(Root);
  277.             getch();
  278.             system("cls");
  279.             cout << "LRN:\n";
  280.             LRN(Root);
  281.             getch();
  282.             system("cls");
  283.             cout << "NLR:\n";
  284.             NLR(Root);
  285.             getch();
  286.             break;
  287.         case 2:
  288.             system("cls");
  289.             cout << "Nhap gia tri chen: ";
  290.             cin >> Value;
  291.             InsertNode(Root, Value);
  292.             getch();
  293.             break;
  294.         case 3:
  295.             system("cls");
  296.             cout << "Nhap gia tri xoa: ";
  297.             cin >> Value;
  298.             Deletenode(Root, Value);
  299.             getch();
  300.             break;
  301.         case 4:
  302.             system("cls");
  303.             cout << "So node: " << DemNode(Root) << endl;
  304.             dem = 0;
  305.             DemLa(Root, dem);
  306.             cout << "So node la: " << dem << endl;
  307.             dem = 0;
  308.             DemNode1CayCon(Root, dem);
  309.             cout << "So node 1 cay con: " << dem << endl;
  310.             dem = 0;
  311.             DemNode2CayCon(Root, dem);
  312.             cout << "So node 2 cay con: " << dem << endl;
  313.             getch();
  314.             break;
  315.         case 5:
  316.             system("cls");
  317.             Output(Root);
  318.             getch();
  319.             break;
  320.         case 6:
  321.             system("cls");
  322.             cout << "Chieu cao cay: " << Height(Root) << endl;
  323.             getch();
  324.             break;
  325.         case 7:
  326.             system("cls");
  327.             TREE Root2;
  328.             CreateTree(Root2);
  329.             CopyTree(Root, Root2);
  330.             LNR(Root2);
  331.             DeleteTree(Root2);
  332.             getch();
  333.             break;
  334.         case 8:
  335.             system("cls");
  336.             DeleteTree(Root);
  337.             getch();
  338.             break;
  339.         case 9:
  340.             system("cls");
  341.             cout << "Nhap gia tri can tim: ";
  342.             cin >> Value;
  343.             if (SearchNode(Root, Value)) cout << "Co gia tri " << Value << " trong cay\n";
  344.             else cout << "Khong co gia tri " << Value << " trong cay\n";
  345.             getch();
  346.             break;
  347.         case 10:
  348.             system("cls");
  349.             Input(Root);
  350.             break;
  351.         }
  352.     } while (x != 0);
  353. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement