API tools faq
paste
Advertisement
haopoka

BinaryTree

haopoka
Apr 28th, 2020
375
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.35 KB | None | 0 0
raw download clone embed print report
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct Node
  5. {
  6.     int data;
  7.     Node* pLeft;
  8.     Node* pRight;
  9. };
  10. typedef Node* TREE;
  11.  
  12. void createTREE(TREE& root)
  13. {
  14.     root=NULL;
  15. }
  16.  
  17. Node* createNode(int x)
  18. {
  19.     Node* p= new Node;
  20.     p->data=x;
  21.     p->pLeft = p->pRight = NULL;
  22.     return p;
  23. }
  24.  
  25. void InsertNode(TREE& root, int x);
  26. //1. Nhap gia tri trong cay
  27. void Input(TREE& root);
  28. //2. Xuat gia tri NLR
  29. void Output_NLR(TREE root);
  30. //3. Xuat gia tri LNR
  31. void Output_LNR(TREE root);
  32. //4. Xuat gia tri LRN
  33. void Output_LRN(TREE root);
  34. //5. Tinh tong gia tri cac nut trong cay.
  35. int SumAllNodes(TREE root);
  36. //6. Tinh tong gia tri cac nut la trong cay.
  37. int SumAllLeaves(TREE root);
  38. //7. Tim gia tri lon nhat trong cay.
  39. int TreeMaxNumber(TREE root);
  40. //8. Tinh chieu cao cua cay.
  41. int TreeHeight(TREE root);
  42. //9. In ra cac nut o muc k cua cay theo LNR.
  43. void OutputLNR_levelK(TREE root, int k);
  44. //10. Tinh tong cac nut o muc k cua cay.
  45. int Sum_KthLevel_Nodes(TREE root, int k);
  46. //11. Dem so luong nut trong cay.
  47. int HowManyNodes(TREE root);
  48. //12. Dem so luong nut la trong cay.
  49. int HowManyLeaves(TREE root);
  50. //13. Dem so luong nut co dung 1 con trong cay.
  51. int HaveOneChild(TREE root);
  52. //14. Xuat ra gia tri va muc cua cac nut trong cay theo thu tu LNR.
  53. void Output_NodeAndIndex_LNR(TREE root, int level);
  54. //15. In ra muc cua nut co gia tri k. Neu khong co, xuat thong bao Khong co nut k.
  55. int GetLevel(TREE root, int data, int level);
  56. //17. Xoa mot node co gia tri k trong cay nhi phan.
  57. int LeftMostValue(TREE root);
  58. TREE DeleteNode(TREE& root, int k);
  59.  
  60. int main()
  61. {
  62.     TREE root;
  63.     int choice, k;
  64.     createTREE(root);
  65.     cout    << "\n1. Nhap gia tri trong cay.\n"
  66.             << "2. Xuat gia tri trong cay theo thu tu NLR.\n"
  67.             << "3. Xuat gia tri trong cay theo thu tu LNR.\n"
  68.             << "4. Xuat gia tri trong cay theo thu tu LRN.\n"
  69.             << "5. Tinh tong gia tri cac nut trong cay.\n"
  70.             << "6. Tinh tong gia tri cac nut la trong cay.\n"
  71.             << "7. Tim gia tri lon nhat trong cay.\n"
  72.             << "8. Tinh chieu cao cua cay.\n"
  73.             << "9. In ra cac nut o muc k cua cay theo LNR.\n"
  74.             << "10. Tinh tong cac nut o muc k cua cay.\n"
  75.             << "11. Dem so luong nut trong cay.\n"
  76.             << "12. Dem so luong nut la trong cay.\n"
  77.             << "13. Dem so luong nut co dung 1 con trong cay.\n"
  78.             << "14. Xuat ra gia tri va muc cua cac nut trong cay theo thu tu LNR.\n"
  79.             << "15. In ra muc cua nut co gia tri k. Neu khong co, xuat thong bao Khong co nut k.\n"
  80.             << "16. Tim nut chua gia tri k va xuat ra muc, chieu cao, bac tai nut do. k la mot gia tri thuoc cay nhi phan.\n"
  81.             << "17. Xoa mot node co gia tri k trong cay nhi phan.\n";
  82.     do
  83.     {
  84.         cout << "\nNhap lua chon: ";
  85.         cin>>choice;
  86.         switch(choice)
  87.         {
  88.         case 1:
  89.             Input(root);
  90.             break;
  91.         case 2:
  92.             cout << "\nNLR: ";
  93.             Output_NLR(root);
  94.             break;
  95.         case 3:
  96.             cout << "\nLNR: ";
  97.             Output_LNR(root);
  98.             break;
  99.         case 4:
  100.             cout << "\nLRN: ";
  101.             Output_LRN(root);
  102.             break;
  103.         case 5:
  104.             cout<< "\nTong cac nut trong cay: " << SumAllNodes(root) << endl;
  105.             break;
  106.         case 6:
  107.             cout<< "\nTong cac nut la trong cay: " << SumAllLeaves(root) << endl;
  108.             break;
  109.         case 7:
  110.             cout << "\nGia tri Node lon nhat trong cay la: " << TreeMaxNumber(root) << endl;
  111.             break;
  112.         case 8:
  113.             cout << "\nChieu cao cua cay: " << TreeHeight(root) <<endl;
  114.             break;
  115.         case 9:
  116.             cout<<"\nNhap vao muc k: ";
  117.             cin>>k;
  118.             cout << "\nNode tai level k la: ";
  119.             OutputLNR_levelK(root, k);
  120.             break;
  121.         case 10:
  122.             cout<<"\nNhap vao muc k: ";
  123.             cin>>k;
  124.             if(k > TreeHeight(root) || k < 1)
  125.                 cout << "\nKhong ton tai muc " << k <<" nay trong cay." <<endl;
  126.             else
  127.                 cout << "\nTong cac Node tai muc " << k << " la: " << Sum_KthLevel_Nodes(root, k) << endl;
  128.             break;
  129.         case 11:
  130.             cout << "\nSo luong node trong cay: " << HowManyNodes(root) <<endl;
  131.             break;
  132.         case 12:
  133.             cout << "\nSo luong node la trong cay: " << HowManyLeaves(root) <<endl;
  134.             break;
  135.         case 13:
  136.             cout << "\nSo luong node chi co dung 1 con: " << HaveOneChild(root) << endl;
  137.             break;
  138.         case 14:
  139.             cout << "\nGia tri va muc trong toan bo cay: \n";
  140.             Output_NodeAndIndex_LNR(root,1);
  141.             break;
  142.         case 15:
  143.             cout<< "\nNhap vao gia tri k: ";
  144.             cin>>k;
  145.             if(GetLevel(root,k,1) == 0)
  146.                 cout<< "\nKhong co gia tri " << k <<endl;
  147.             else
  148.                 cout <<"\nGia tri " << k << " nam o muc " << GetLevel(root,k,1) - 1 << endl;
  149.             break;
  150.         case 16:
  151.             cout<< "\nNhap vao gia tri k: ";
  152.             cin>>k;
  153.             cout << "\nGia tri " << k << " vua nhap nam o \n\t- Muc: " << GetLevel(root,k,1) - 1 << endl;
  154.             cout << "\t- Chieu cao: " << GetLevel(root,k,1) <<"\n\t- Bac: " << GetLevel(root,k,1) << endl;
  155.             break;
  156.         case 17:
  157.             cout<< "\nNhap vao gia tri k muon xoa: ";
  158.             cin>>k;
  159.             *root = *DeleteNode(root, k);
  160.             break;
  161.         default:
  162.             break;
  163.         }
  164.     } while(choice>=1 && choice<=17);
  165.     return 0;
  166. }
  167.  
  168.  
  169. void InsertNode(TREE& root, int x)
  170. {
  171.     Node* p = createNode(x);
  172.     if(root==NULL)
  173.         root = p;
  174.     else
  175.     {
  176.         if(x == root->data)
  177.             return;
  178.         else
  179.         {
  180.             if(x < (root->data))
  181.                 InsertNode(root->pLeft,x);
  182.             else
  183.                 InsertNode(root->pRight,x);
  184.         }
  185.     }
  186. }
  187.  
  188. //1. Nhap gia tri trong cay
  189. void Input(TREE& root)
  190. {
  191.     int x;
  192.     do
  193.     {
  194.         cout << "\nNhap vao gia tri Node (nhap 0 de ngung lai): ";
  195.         cin >> x;
  196.         if(x>0)
  197.             InsertNode(root,x);
  198.     } while(x>0);
  199. }
  200. //2. Xuat gia tri NLR
  201. void Output_NLR(TREE root)
  202. {
  203.     if(root != NULL)
  204.     {
  205.         cout << root->data << "\t";
  206.         Output_NLR(root->pLeft);
  207.         Output_NLR(root->pRight);
  208.     }
  209. }
  210.  
  211. //3. Xuat gia tri LNR
  212. void Output_LNR(TREE root)
  213. {
  214.     if(root != NULL)
  215.     {
  216.         Output_LNR(root->pLeft);
  217.         cout << root->data << "\t";
  218.         Output_LNR(root->pRight);
  219.     }
  220. }
  221.  
  222. //4. Xuat gia tri LRN
  223. void Output_LRN(TREE root)
  224. {
  225.     if(root != NULL)
  226.     {
  227.         Output_LRN(root->pLeft);
  228.         Output_LRN(root->pRight);
  229.         cout << root->data << "\t";
  230.     }
  231. }
  232.  
  233. //5. Tinh tong gia tri cac nut trong cay.
  234. int SumAllNodes(TREE root)
  235. {
  236.     if(root == NULL)
  237.         return 0;
  238.     return (root->data + SumAllNodes(root->pLeft) + SumAllNodes(root->pRight));
  239. }
  240.  
  241. //6. Tinh tong gia tri cac nut la trong cay.
  242. int SumAllLeaves(TREE root)
  243. {
  244.     if(root == NULL)
  245.         return 0;
  246.     if(root->pLeft == NULL && root->pRight == NULL)
  247.         return root->data;
  248.     return SumAllLeaves(root->pLeft) + SumAllLeaves(root->pRight);
  249. }
  250.  
  251. //7. Tim gia tri lon nhat trong cay.
  252. int TreeMaxNumber(TREE root)
  253. {
  254.     if(root == NULL)
  255.         return 0;
  256.     int res = root->data;
  257.     int lres = TreeMaxNumber(root->pLeft);
  258.     int rres = TreeMaxNumber(root->pRight);
  259.     if (lres > res)
  260.         res = lres;
  261.     if (rres > res)
  262.         res = rres;
  263.     return res;
  264. }
  265.  
  266. //8. Tinh chieu cao cua cay.
  267. int TreeHeight(TREE root)
  268. {
  269.     if(root == NULL)
  270.         return 0;
  271.     int left = TreeHeight(root->pLeft);
  272.     int right = TreeHeight(root->pRight);
  273.     int res = (left > right) ? left : right;
  274.     return 1 + res;
  275. }
  276.  
  277. //9. In ra cac nut o muc k cua cay theo LNR.
  278. void OutputLNR_levelK(TREE root, int k)
  279. {
  280.     if(k > TreeHeight(root))
  281.     {
  282.         cout<<"\nKhong ton tai muc " << k <<" cua cay.\n";
  283.         return;
  284.     }
  285.     if(k < 1)
  286.         return;
  287.     if(k==1)
  288.         cout << root->data << " ";
  289.     OutputLNR_levelK(root->pLeft, k-1);
  290.     OutputLNR_levelK(root->pRight, k-1);
  291. }
  292.  
  293. //10. Tinh tong cac nut o muc k cua cay.
  294. int Sum_KthLevel_Nodes(TREE root, int k)
  295. {
  296.     if(k > TreeHeight(root)||k < 1)
  297.     {
  298.         return 0;
  299.     }
  300.     if(k == 1)
  301.         return root->data;
  302.     return Sum_KthLevel_Nodes(root->pRight,k-1) + Sum_KthLevel_Nodes(root->pLeft, k-1);
  303. }
  304.  
  305. //11. Dem so luong nut trong cay.
  306. int HowManyNodes(TREE root)
  307. {
  308.     if(root == NULL)
  309.         return 0;
  310.     return 1 + HowManyNodes(root->pLeft) + HowManyNodes(root->pRight);
  311. }
  312.  
  313. //12. Dem so luong nut la trong cay.
  314. int HowManyLeaves(TREE root)
  315. {
  316.     if(root == NULL)
  317.         return 0;
  318.     if(root->pLeft == NULL && root->pRight == NULL)
  319.         return 1;
  320.     if(root->pLeft == NULL && root->pRight != NULL)
  321.         return 0 + HowManyLeaves(root->pRight);
  322.     if(root->pLeft != NULL && root->pRight == NULL)
  323.         return 0 + HowManyLeaves(root->pLeft);
  324.     return 0 + HowManyLeaves(root->pLeft) + HowManyLeaves(root->pRight);
  325. }
  326.  
  327. //13. Dem so luong nut co dung 1 con trong cay.
  328. int HaveOneChild(TREE root)
  329. {
  330.     if(root == NULL)
  331.         return 0;
  332.     if(root->pLeft == NULL && root->pRight != NULL)
  333.         return 1 + HaveOneChild(root->pRight);
  334.     if(root->pLeft != NULL && root->pRight == NULL)
  335.         return 1 + HaveOneChild(root->pLeft);
  336.     return 0 + HaveOneChild(root->pLeft) + HaveOneChild(root->pRight);
  337. }
  338.  
  339.  
  340.  
  341. //14. Xuat ra gia tri va muc cua cac nut trong cay theo thu tu LNR.
  342. void Output_NodeAndIndex_LNR(TREE root, int level)
  343. {
  344.     if(root != NULL)
  345.     {
  346.         Output_NodeAndIndex_LNR(root->pLeft, level+1);
  347.         cout << root->data << "\t" << level << endl;
  348.         Output_NodeAndIndex_LNR(root->pRight, level +1);
  349.     }
  350. }
  351.  
  352. //15. In ra muc cua nut co gia tri k. Neu khong co, xuat thong bao Khong co nut k.
  353. int GetLevel(TREE root, int data, int level)
  354. {
  355.     if(root == NULL)
  356.         return 0;
  357.     if(root->data == data)
  358.         return level;
  359.     int left = GetLevel(root->pLeft, data, level+1);
  360.     if(left != 0)
  361.         return left;
  362.     int right = GetLevel(root->pRight, data, level+1);
  363.     return right;
  364. }
  365.  
  366. void MakeNewTree_NLR(TREE& root, TREE p)
  367. {
  368.     if(p != NULL)
  369.     {
  370.         cout <<"\nMake new tree " << p->data;
  371.         InsertNode(root, p->data);
  372.         MakeNewTree_NLR(root, p->pLeft);
  373.         MakeNewTree_NLR(root, p->pRight);
  374.     }
  375. }
  376.  
  377. int LeftMostValue(TREE root)
  378. {
  379.     while ( root->pLeft != NULL )
  380.         root = root->pLeft;
  381.     return root->data;
  382. }
  383.  
  384. //17. Xoa mot node co gia tri k trong cay nhi phan.
  385. TREE DeleteNode(TREE& root, int k)
  386. {
  387.     if(root == NULL)
  388.         return root;
  389.     if(k < root->data)
  390.         root->pLeft = DeleteNode(root->pLeft, k);
  391.     else if(k > root->data)
  392.         root->pRight = DeleteNode(root->pRight, k);
  393.     else
  394.     {
  395.         if(root->pLeft == NULL)
  396.         {
  397.             TREE newRoot = root->pRight;
  398.             root = createNode(0);
  399.             return newRoot;
  400.         }
  401.         if(root->pRight == NULL)
  402.         {
  403.             TREE newRoot = root->pLeft;
  404.             root = createNode(0);
  405.             return newRoot;
  406.         }
  407.         root->data = LeftMostValue(root->pRight);
  408.         root->pRight = DeleteNode(root->pRight, root->data);
  409.     }
  410.     return root;
  411. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!