Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <conio.h>
- using namespace std;
- struct TreeNode
- {
- int key;
- int value;
- TreeNode *pLeft, *pRight;
- };
- typedef TreeNode* TREE;
- void CreateTree(TREE &Root)
- {
- Root = NULL;
- }
- int InsertNode(TREE &Root, int key)
- {
- if (Root)
- {
- if (Root->key == key)
- {
- Root->value++;
- return 0;
- }
- if (Root->key > key) return InsertNode(Root->pLeft, key);
- return InsertNode(Root->pRight, key);
- }
- TreeNode *p = new TreeNode;
- if (p == NULL) return -1;
- p->pLeft = p->pRight = NULL;
- p->key = key;
- p->value = 1;
- Root = p;
- return 1;
- }
- void NLR(TREE Root)
- {
- if (Root)
- {
- cout << Root->key << endl;
- NLR(Root->pLeft);
- NLR(Root->pRight);
- }
- }
- void LNR(TREE Root)
- {
- if (Root)
- {
- LNR(Root->pLeft);
- cout << Root->key << endl;
- LNR(Root->pRight);
- }
- }
- void LRN(TREE Root)
- {
- if (Root)
- {
- LRN(Root->pLeft);
- LRN(Root->pRight);
- cout << Root->key << endl;
- }
- }
- int SearchNode(TREE Root, int key)
- {
- if (Root)
- {
- if (Root->key == key)
- return 1;
- if (Root->key > key) return SearchNode(Root->pLeft, key);
- return SearchNode(Root->pRight, key);
- }
- return 0;
- }
- void DeleteTree(TREE &Root)
- {
- if (Root)
- {
- DeleteTree(Root->pLeft);
- DeleteTree(Root->pRight);
- delete Root;
- }
- Root = NULL;
- }
- void CopyTree(TREE Root1, TREE &Root2)
- {
- if (Root1)
- {
- TreeNode * p = new TreeNode;
- if (p == NULL) exit(1);
- p->pLeft = p->pRight = NULL;
- p->key = Root1->key;
- p->value = Root1->value;
- Root2 = p;
- CopyTree(Root1->pLeft, Root2->pLeft);
- CopyTree(Root1->pRight, Root2->pRight);
- }
- }
- void Output(TREE R)
- {
- if (R)
- {
- Output(R->pRight);
- cout << R->key << "\tXuat hien: " << R->value << endl;
- Output(R->pLeft);
- }
- }
- int Height(TREE Root)
- {
- if (!Root)
- return 0;
- int a = Height(Root->pLeft);
- int b = Height(Root->pRight);
- if (a > b) return (a + 1);
- else return (b + 1);
- }
- int DemNode(TREE Root)
- {
- if (Root == NULL)
- return 0;
- return (1 + DemNode(Root->pLeft) + DemNode(Root->pRight));
- }
- void DemLa(TREE Root, int &count)
- {
- if (Root)
- {
- if (Root->pLeft == NULL && Root->pRight == NULL) count++;
- DemLa(Root->pLeft, count);
- DemLa(Root->pRight, count);
- }
- }
- void DemNode1CayCon(TREE Root, int &count)
- {
- if (Root)
- {
- if (Root->pLeft != Root->pRight && (Root->pRight == NULL || Root->pLeft == NULL)) count++;
- DemNode1CayCon(Root->pLeft, count);
- DemNode1CayCon(Root->pRight, count);
- }
- }
- void DemNode2CayCon(TREE Root, int &count)
- {
- if (Root)
- {
- if (Root->pRight != NULL && Root->pLeft != NULL) count++;
- DemNode2CayCon(Root->pLeft, count);
- DemNode2CayCon(Root->pRight, count);
- }
- }
- void DemNode_Muc(TREE Root, int muc, int &count)
- {
- if (Root)
- {
- if (Height(Root) == muc) count++;
- DemNode_Muc(Root->pLeft, muc, count);
- DemNode_Muc(Root->pRight, muc, count);
- }
- }
- int SNT(int n)
- {
- if (n < 2) return 0;
- for (int i = 2; i * i <= n; i++)
- if (n % i == 0) return 0;
- return 1;
- }
- void Dem_SNT(TREE Root, int &count)
- {
- if (Root)
- {
- if (SNT(Root->key)) count++;
- Dem_SNT(Root, count);
- Dem_SNT(Root, count);
- }
- }
- void MackDeletion(TREE &Root)
- {
- TreeNode *p = Root;
- if (Root->pLeft == NULL && Root->pRight == NULL)
- {
- Root = NULL;
- delete p;
- return;
- }
- if (Root->pLeft == NULL)
- {
- Root = p->pRight;
- delete p;
- return;
- }
- if (Root->pRight == NULL)
- {
- Root = p->pLeft;
- delete p;
- return;
- }
- TreeNode *pPtr = Root->pRight;
- while (pPtr->pLeft) pPtr = pPtr->pLeft;
- pPtr->pLeft = p->pLeft;
- Root = p->pRight;
- delete p;
- }
- int Deletenode(TREE &Root, int x)
- {
- if (Root)
- {
- if (Root->key == x)
- {
- MackDeletion(Root);
- return 1;
- }
- if (Root->key > x) return Deletenode(Root->pLeft, x);
- return Deletenode(Root->pRight, x);
- }
- return 0;
- }
- void Input(TREE &Root)
- {
- int x;
- do
- {
- cout << "Nhap x = 0 de thoat nhap: x = ";
- cin >> x;
- if (x == 0) break;
- InsertNode(Root, x);
- } while (1);
- }
- void DuyetTheoMuc(TREE &Root)
- {
- TREE p = Root;
- queue<TREE> q;
- if (Root == NULL) return;
- q.push(p);
- while (!q.empty())
- {
- p = q.front();
- q.pop();
- cout << p->key << "\t";
- if (p->pLeft) q.push(p->pLeft);
- if (p->pRight) q.push(p->pRight);
- }
- }
- void menu()
- {
- system("cls");
- cout << "1.\t Duyet cay" << endl;
- cout << "2.\t Chen Node" << endl;
- cout << "3.\t Xoa Node" << endl;
- cout << "4.\t Dem Node" << endl;
- cout << "5.\t So lan xuat hien khi chen" << endl;
- cout << "6.\t Chieu cao cay" << endl;
- cout << "7.\t Copy cay" << endl;
- cout << "8.\t Xoa cay" << endl;
- cout << "9.\t Tim Node" << endl;
- cout << "10.\t Nhap cay" << endl;
- cout << "0.\t Thoat" << endl;
- cout << "Lua Chon: ";
- }
- void main()
- {
- TREE Root;
- CreateTree(Root);
- int x;
- int Value;
- int dem = 0;
- do
- {
- menu();
- cin >> x;
- switch (x)
- {
- case 1:
- system("cls");
- cout << "LNR:\n";
- LNR(Root);
- getch();
- system("cls");
- cout << "LRN:\n";
- LRN(Root);
- getch();
- system("cls");
- cout << "NLR:\n";
- NLR(Root);
- getch();
- break;
- case 2:
- system("cls");
- cout << "Nhap gia tri chen: ";
- cin >> Value;
- InsertNode(Root, Value);
- getch();
- break;
- case 3:
- system("cls");
- cout << "Nhap gia tri xoa: ";
- cin >> Value;
- Deletenode(Root, Value);
- getch();
- break;
- case 4:
- system("cls");
- cout << "So node: " << DemNode(Root) << endl;
- dem = 0;
- DemLa(Root, dem);
- cout << "So node la: " << dem << endl;
- dem = 0;
- DemNode1CayCon(Root, dem);
- cout << "So node 1 cay con: " << dem << endl;
- dem = 0;
- DemNode2CayCon(Root, dem);
- cout << "So node 2 cay con: " << dem << endl;
- getch();
- break;
- case 5:
- system("cls");
- Output(Root);
- getch();
- break;
- case 6:
- system("cls");
- cout << "Chieu cao cay: " << Height(Root) << endl;
- getch();
- break;
- case 7:
- system("cls");
- TREE Root2;
- CreateTree(Root2);
- CopyTree(Root, Root2);
- LNR(Root2);
- DeleteTree(Root2);
- getch();
- break;
- case 8:
- system("cls");
- DeleteTree(Root);
- getch();
- break;
- case 9:
- system("cls");
- cout << "Nhap gia tri can tim: ";
- cin >> Value;
- if (SearchNode(Root, Value)) cout << "Co gia tri " << Value << " trong cay\n";
- else cout << "Khong co gia tri " << Value << " trong cay\n";
- getch();
- break;
- case 10:
- system("cls");
- Input(Root);
- break;
- }
- } while (x != 0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement