Skip to content

Instantly share code, notes, and snippets.

@NhanAZ

NhanAZ/ShareCodeForMyBro.cpp

Last active June 11, 2024 03:09
Show Gist options
  • Save NhanAZ/cb163b94164c10cc05990406e7b17b90 to your computer and use it in GitHub Desktop.
Save NhanAZ/cb163b94164c10cc05990406e7b17b90 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ShareCodeForMyBro.cpp
/*Viet Chuong Trinh Demo Cay Nhi Phan Tim Kiem Thao Tac Tren Day So Nguyen
Ho Ten : Nguyen Thanh Nhan
ma SV : 2310010023
De 1:
a. Xay Dung Tac Vu Dem So Nut La Nut La Co Noi Dung Chia Het Cho X
b. Xay Dung Tac Vu In Noi Dung Cua Cac Nut Co Toi Thieu 1 Nhanh Con Va
Co Gia Tri Trong Doan [x, y], In Thu Tu Duyet Truoc (NLR)
De 2:
a. Xay Dung Tac Vu Dem So Nut La Nut Nhanh Co Noi Dung Khong Chia Het Cho X
b. Xay Dung Tac Vu In Noi Dung Cua Cac Nut Co 2 Nhanh Con Va
Co Gia Tri Khong Nam Trong Doan [x, y], In Thu Tu Duyet Sau (LRN)
BAI LAM: DE 1
*/
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <dos.h>
#include <stdlib.h>
#include <math.h>
//#include <alloc.h>
#include <windows.h>
//==============================
struct tree {
int key; //Luu Noi Dung
struct tree *pleft, *pright; //Luu DC Nut Goc Nhanh Con Trai Va Phai
};
typedef struct tree *TREE; //DN KDL Con TRo Cau Truc
//==============================
//Khai Bao Cac Prototype
void Initialize(TREE *root);
TREE Getnode();
int Empty(TREE *root);
int InsertTree(TREE &T, int x);
TREE SearchT(TREE T, int x);
void TaoCay(TREE &T);
void NLR(TREE root);
void LNR(TREE root);
void LRN(TREE root);
int DelNodeTree(TREE &T, int x);
void FindMinRight(TREE &p, TREE &q);
int DelNodeTree1(TREE &T, int x);
void FindMaxLeft(TREE &p, TREE &q);
void TaoCay(TREE &T);
void RemoveTree(TREE &T);
//========== Dem / In Thoa DK ========
//===================================
//Dem So Nut Trong Cay La Nut La (DK C)
int Count(TREE root);
//Dem So Nut Trong Cay Co Toi Thieu 1 Nhanh Con (Bac >= 1 : DK B)
int Count1(TREE root);
//Dem So Nut Trong Cay Chia Het Cho X (Dieu Kien F)
int Count2(TREE root, int x);
//Dem So Nut Trong Cay >= X, <= Y (Dieu Kien F)
int Count3(TREE root, int x, int y);
//In Noi Dung Cac Nut La
void In(TREE root);
//In NDung Cac Nut Trong Cay Co Toi Thieu 1 Nhanh Con (Bac >= 1: DK B)
void In1(TREE root);
//In Noi Dung Cac Nut Trong Cay Chia Het Cho X (Dieu Kien F)
void In2(TREE root, int x);
//Dem So Nut Trong Cay >= X, <= Y (Dieu Kien F)
void In3(TREE root, int x, int y);
int Dem_Nut_La_Chia_Het_Cho_x(TREE root, int x);
void In_Nut_Bac_Lon_Hon_1_Doan_XY_NLR(TREE root, int x, int y);
//..............
//===========================
//Chuong Trinh Chinh viet Theo Dang Hien Thi DS Cac Chuc nang Chon Chon Lua
int main() {
//clrscr(); //Xoa MH
system("cls"); //Xoa MH
int x, y;
TREE root;
int chon, d;
Initialize(&root);
float s;
do {
//clrscr(); //Xoa MH
system("cls"); //Xoa MH
printf("\n\tCHUONG TRINH DEMO CAY NHI PHAN TIM KIEM !");
printf("\n\tCac Chuc nang trong Chuong Trinh !");
printf("\n\t1 : Khoi Tao !");
printf("\n\t2. : Kiem Tra Cay Rong !");
printf("\n\t3 : Tao Cay !");
printf("\n\t4 : Duyet Cay Heo Thu Tu Truoc (NLR) !");
printf("\n\t5 : Duyet Cay Heo Thu Tu Giua (LNR) !");
printf("\n\t6 : Duyet Cay Heo Thu Tu Sau (LNR) !");
printf("\n\t7 : Them 1 Phan Tu Vao Cay !");
printf("\n\t---- Xoa 1 PTu Trong Cay ---- ");
printf("\n\t8 : Nut Thay The Thuoc Nhanh Con Phai (TH Co 2 Nhanh Con) !");
printf("\n\t9 : Nut Thay The Thuoc Nhanh Con Trai (TH Co 2 Nhanh Con) !");
printf("\n\t10 : Tim Kiem !");
printf("\n\t11 : In - Dem So Nut Trong Cay La Nut La (Bac = 0) !");
printf("\n\t12 : In - Dem So Nut Trong Cay La Nut Nhanh (Bac >= 1) !");
printf("\n\t13 : In - Dem So Nut Trong Cay Co 2 Nhanh Con (Bac = 2) !");
printf("\n\t14 : .... !");
printf("\n\t15 : .... !");
printf("\n\t16 : .... !");
printf("\n\t17 : Dem So Nut La Chia Het Cho x !");
printf("\n\t18 : In Noi Dung Cac Nut Co Bac >= 1 Trong Doan [x, y] Theo Thu Tu Duyet Truoc (NLR) !");
printf("\n\t...............");
printf("\n\t0 : Thoat Khoi Chuong Trinh !");
printf("\n\tBan Chon Chuc nang Nao ? ");
scanf("%d", &chon);
switch (chon) {
case 1: {
printf("\n\tKhoi Tao Cay !");
Initialize(&root);
printf("\n\tCay Da Duoc Khoi Tao !");
getch();
break;
}
case 2: {
printf("\n\tKiem Tra DS Rong !");
if (Empty(&root) == 1)
printf("\n\tCay Rong !");
else
printf("\n\tCay Khong Rong !");
getch();
break;
}
case 3: {
printf("\n\tTao Cay Ban Dau !");
printf("\n\tNhap Noi Dung Cac Phan Tu !");
TaoCay(root);
break;
}
case 31: {
printf("\n\tTao Cay Ban Dau !");
printf("\n\tNhap Noi Dung Cac Phan Tu !");
// nhapCay1 (&root);
break;
}
case 4: {
printf("\n\tDuyet Cay Theo Thu Tu Truoc (NLR) !\n\t");
NLR(root);
getch();
break;
}
case 5: {
printf("\n\tDuyet Cay Theo Thu Tu Giua (LNR) !\n\t");
LNR(root);
getch();
break;
}
case 6: {
printf("\n\tDuyet Cay Theo Thu Tu Sau (LRN) !\n\t");
LRN(root);
getch();
break;
}
case 7: {
printf("\n\tThem 1 Phan Tu Vao Cay !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tNhap Noi Dung X Cua Nut Can Them : ");
scanf("%d", &x);
InsertTree(root, x);
printf("\n\tCay Sau Khi Them (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
break;
}
case 8: {
printf("\n\tXoa 1 Phan Tu Trong Cay !");
printf("\n\t--- Khi Xoa Nut Co 2 Nhanh Con: Nut Thay The Thuoc Nhanh Phai --- !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tNhap Noi Dung X Cua Nut Can Xoa : ");
scanf("%d", &x);
y = DelNodeTree(root, x);
printf("\n\tCay Sau Khi Xoa (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
break;
}
case 9: {
printf("\n\tXoa 1 Phan Tu Trong Cay !");
printf("\n\t--- Khi Xoa Nut Co 2 Nhanh Con: Nut Thay The Thuoc Nhanh Trai --- !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tNhap Noi Dung X Cua Nut Can Xoa : ");
scanf("%d", &x);
y = DelNodeTree1(root, x);
printf("\n\tCay Sau Khi Xoa (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
break;
}
case 10: {
printf("\n\tDem - In Cac NUT LA Trong Cay !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tDanh Sach Cac Nut La !\n\t");
In1(root);
getch();
d = Count(root);
printf("\n\tTong So Nut La Trong Cay: \'%3d Nut\' !", d);
getch();
break;
}
case 11: {
printf("\n\tDem - In So Nut Trong Cay Co Toi Thieu 1 Nhanh Con (Bac >= 1) !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tDanh Sach Cac Nut Co Toi Thieu 1 Nhanh Con !\n\t");
In1(root);
getch();
d = Count1(root);
printf("\n\tTong So Nut Co Toi Thieu 1 Nhanh Con Trong Cay : \'%3d Nut\' !", d);
getch();
break;
}
case 12: {
printf("\n\tDem - In Dem So Nut Trong Cay Chia Het Cho X !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tNhap Noi Dung DK X : ");
scanf("%d", &x);
printf("\n\tDanh Sach Cac Chia Het Cho \'%d'\ !\n\t", x);
In2(root, x);
getch();
d = Count2(root, x);
printf("\n\tTong So Nut Chia Het : \'%d\' !", d);
getch();
break;
}
case 13: {
printf("\n\tDem - In So Nut Trong Doan [X, Y] !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tNhap Noi Dung DK X & Y : ");
scanf("%d%d", &x, &y);
printf("\n\tDanh Sach Cac Nut Trong Doan [%d; %d] !\n\t", x, y);
In3(root, x, y);
getch();
d = Count3(root, x, y);
printf("\n\tTong So Nut Chia Het : \'%d\' !", d);
getch();
break;
}
case 14: {
printf("\n\tHuy Cay !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
RemoveTree(root);
printf("\n\tHuy Cay Thanh Cong !");
getch();
break;
}
case 17: {
printf("\n\tDem So Nut La Chia Het Cho x !");
printf("\n\tCay Hien Tai (Duyet Giua : LNR) !\n\t");
LNR(root);
getch();
printf("\n\tNhap Gia Tri x: ");
scanf("%d", &x);
int soNutLa = Dem_Nut_La_Chia_Het_Cho_x(root, x);
printf("\n\tSo Nut La Chia Het Cho %d: %d", x, soNutLa);
getch();
break;
}
case 18: {
printf("\n\tIn Noi Dung Cac Nut Co Bac >= 1 Trong Doan [x, y] Theo Thu Tu Duyet Truoc (NLR)");
printf("\n\tNhap Gia Tri x: ");
scanf("%d", &x);
printf("\n\tNhap Gia Tri y: ");
scanf("%d", &y);
printf("\n\tCac Nut Co Bac >= 1 Trong Doan [%d, %d] Theo Thu Tu Duyet Truoc (NLR): ", x, y);
In_Nut_Bac_Lon_Hon_1_Doan_XY_NLR(root, x, y);
printf("\n");
getch();
break;
}
}//KT Sweitch
} while (chon > 0);
getch();
return 0;
}//KT CTrinh Chinh
//===========================
//Cai Dat Cac Prototype Da KB O tren
//===================================
//==========Khoi Tao ================
void Initialize(TREE *root) {
*root = NULL;
}
//=========Cap Phat VN ==============
TREE Getnode() {
TREE T;
T = (TREE) malloc(sizeof(struct tree));
T->pleft = T->pright = NULL;
return T;
}
//===========Kiem Tra Rong===========
int Empty(TREE *root) {
if (*root == NULL)
return 1; //Rong
return 0; //K.Rong
}
//======In Noi Dung Theo Thu Tu Duyet Truoc ======
void NLR(TREE root) {
if (root) //if (root != NULL)
{ //Xu Ly Noi Dung Nut Goc; Xu Ly Nut Goc;
printf("%4d", root->key); //(1)
NLR(root->pleft); //(2)
NLR(root->pright); //(3)
}
}
//======In Noi Dung Theo Thu Tu Duyet Giua ======
void LNR(TREE root) {
if (root) //if (root != NULL)
{
LNR(root->pleft); //(2)
//Xu Ly Noi Dung Nut Goc; Xu Ly Nut Goc;
printf("%4d", root->key); //(1)
LNR(root->pright); //(3)
}
}
//======In Noi Dung Theo Thu Tu Duyet Sau ======
void LRN(TREE root) {
if (root) //if (root != NULL)
{
LRN(root->pleft); //(2)
LRN(root->pright); //(3)
//Xu Ly Noi Dung Nut Goc; Xu Ly Nut Goc;
printf("%4d", root->key); //(1)
}
}
//=========Tim Kiem Ptu Co Noi Dung X ==========
TREE SearchT(TREE T, int x) {
if (T) {
if (T->key == x) return T;
if (T->key > x)
return SearchT(T->pleft, x);
else
return SearchT(T->pright, x);
}
return NULL;
}
//=========Them 1 PTu Vao Nut La ===============
int InsertTree(TREE &T, int x) {
if (T) //if (T != NULL)
{
if (T->key == x) {
printf("\n\tTrung Khong Them Dc !");
return 0; //Trung, Khong Them Dc
}
if (T->key > x) //Goi De Quy Nhanh Trai
return InsertTree(T->pleft, x);
else //Goi De Quy Nhanh Phai
return InsertTree(T->pright, x);
}
T = Getnode();
T->key = x;
T->pleft = T->pright = NULL;
return 1; //Thanh Cong
}
//===========xoa 1 Nut Trong Cay ====
//===================================
//--- Xac Dinh Nut Trai Nhat (Be Nhat) Thuoc Nhanh Phai ---
void FindMinRight(TREE &p, TREE &q) {
if (q->pleft != NULL)
FindMinRight(p, q->pleft);
else {
p->key = q->key;
p = q;
q = q->pright;
}
}
//===================================
//--- Xac Dinh Nut Phai Nhat (Lon Nhat) Thuoc Nhanh Trai ---
void FindMaxLeft(TREE &p, TREE &q) {
if (q->pright != NULL)
FindMaxLeft(p, q->pright);
else {
p->key = q->key;
p = q;
q = q->pleft;
}
}
//===================================
//---- TH Co 2 Nhanh Con ----
//---- Nut Thay The La Nut Be Nhat (Trai Nhat) Thuoc Nhanh Con Phai ----
//===================================
int DelNodeTree(TREE &T, int x) {
TREE p, q;
if (T == NULL) return 0;
if (T->key > x)
return DelNodeTree(T->pleft, x);
if (T->key < x)
return DelNodeTree(T->pright, x);
else //T -> key = x
{
p = T;
if (T->pleft == NULL)
T = T->pright;
else {
if (T->pright == NULL)
T = T->pleft;
else {
q = T->pright;
FindMinRight(p, q);
}
free(p);
}
}
}
//===================================
//---- TH Co 2 Nhanh Con ----
//---- Nut Thay The La Nut Phai Nhat (Lon Nhat) Thuoc Nhanh Con Trai ----
//===================================
int DelNodeTree1(TREE &T, int x) {
TREE p, q;
if (T == NULL) return 0;
if (T->key > x)
return DelNodeTree(T->pleft, x);
if (T->key < x)
return DelNodeTree(T->pright, x);
else //T -> key = x
{
p = T;
if (T->pleft == NULL)
T = T->pright;
else {
if (T->pright == NULL)
T = T->pleft;
else {
q = T->pleft;
FindMaxLeft(p, q);
}
free(p);
}
}
}
//===================================
void TaoCay(TREE &T) {
int n, x;
Initialize(&T);
printf("\n\tNhap So Phan Tu Trong Cay : ");
scanf("%d", &n);
printf("\n\tNhap Noi Dung Cac Nut Trong Cay !\n");
for (int i = 1; i <= n; i++) {
printf("\tNhap Noi Dung X Nut Can Them : ");
scanf("%d", &x);
InsertTree(T, x);
}
}
//===================================
//Huy Cay
void RemoveTree(TREE &T) {
if (T) {
RemoveTree(T);
RemoveTree(T);
delete (T);
}
}
//-------- Dem So Nut / In So Nut Thoa DK --------
//--- a. Co Hai Nhanh Con (Bac = 2)
//--- If ((root -> pleft != NULL) && (root -> pright != NULL))
//--- b. Co Toi Thieu 1 Nhanh Con (Bac >= 1)
//--- //--- If ((root -> pleft != NULL) || (root -> pright != NULL))
//--- c. Khong Nhanh Con (Bac = 0 : Nut La)
//--- If ((root -> pleft == NULL) && (root -> pright == NULL))
//--- d. Co Duy Nhat 1 Nhanh Con (Bac = 1)
//--- If (((root -> pleft != NULL) && (root -> pright == NULL)) ||
//--- If ((root -> pleft == NULL) && (root -> pright != NULL)))
//---
//--- e. Co noi dung thoai dieu kien (Gia tri Chan, gia tri Le)
//--- Gia Tri Chan
//--- If (root -> key % 2 == 0)
//--- Gia Tri Le
//--- If (root -> key % 2 != 0)
//--- f. Co noi dung thoai dieu kien (Chia het Cho X, > X, < X, Gia tri Chan, gia tri Le, �)
//--- - Chia het Cho X
//--- If (root -> key % x == 0)
//--- - Lon Hon X
//--- If (root -> key > x)
//--- - Nho Hon X
//--- If (root -> key < x)
//---
//=============== MAU 1 : DEM ================
/*
int Count (TREE root)
{
if (root) //if (root != NULL)
{
If DK a, b, c, d, e
return 1 + Count (root -> pleft) + Count (root -> pright);
return Count (root -> pleft) + Count (root -> pright);
}
return 0;
}
//-------------------------------
int Count1 (TREE root)
{ int d = 0;
if (root) //if (root != NULL)
{
If DK a, b, c, d, e
d = d + 1;
d = d + Count1 (root -> pleft) + Count1 (root -> pright);
}
return d;
}
//=============== MAU 2 : DEM ================
//------ Dieu Kien f ------
int Count2 (TREE root, int/data x)
{
if (root) //if (root != NULL)
{
If DK f
return 1 + Count2 (root -> pleft, x) + Count2 (root -> pright, x);
return Count2 (root -> pleft, x) + Count2 (root -> pright, x);
}
return 0;
}
//-------------------------------
int Count3 (TREE root, int/data x)
{
if (root) //if (root != NULL)
{ int d = 0;
If DK f
d = d + 1;
d = d + Count3 (root -> pleft, x) + Count3 (root -> pright, x);
}
return d;
}
*/
//===================================
//Dem So Nut Trong Cay La Nut La (DK C)
int Count(TREE root) {
if (root) //if (root != NULL)
{
if ((root->pleft == NULL) && (root->pright == NULL))
return 1 + Count(root->pleft) + Count(root->pright);
return Count(root->pleft) + Count(root->pright);
}
return 0;
}
//===================================
//Dem So Nut Trong Cay Co Toi Thieu 1 Nhanh Con (Bac >= 1 : DK B)
int Count1(TREE root) {
int d = 0;
if (root) //if (root != NULL)
{
if (((root->pleft != NULL) && (root->pright == NULL)) || ((root->pleft == NULL) && (root->pright != NULL)))
d = d + 1;
d = d + Count1(root->pleft) + Count1(root->pright);
}
return d;
}
//===================================
//Dem So Nut Trong Cay Chia Het Cho X (Dieu Kien F)
int Count2(TREE root, int x) {
if (root) //if (root != NULL)
{
if (root->key % x == 0)
return 1 + Count2(root->pleft, x) + Count2(root->pright, x);
return Count2(root->pleft, x) + Count2(root->pright, x);
}
return 0;
}
//===================================
//Dem So Nut Trong Cay >= X, <= Y (Dieu Kien F)
int Count3(TREE root, int x, int y) {
int d = 0;
if (root) //if (root != NULL)
{
int d = 0;
if ((root->key >= x) && (root->key <= y))
d = d + 1;
d = d + Count3(root->pleft, x, y) + Count3(root->pright, x, y);
}
return d;
}
//===================================
//===================================
//In Noi Dung Cua Cay Thoa DK a, b, c, d, e
//In Noi Dung Cac Nut La
void In(TREE root) {
if (root) //if (root != NULL)
{
if ((root->pleft == NULL) && (root->pright == NULL)) {
In(root->pleft);
//Xu Ly Nut Goc (IN)
printf("%7d", root->key);
In(root->pright);
}
}
}
//===================================
//In Noi Dung Cac Nut Trong Cay Co Toi Thieu 1 Nhanh Con (Bac >= 1 : DK B)
void In1(TREE root) {
if (root) //if (root != NULL)
{
if (((root->pleft != NULL) && (root->pright == NULL)) || ((root->pleft == NULL) && (root->pright != NULL))) {
In1(root->pleft);
//Xu Ly Nut Goc (IN)
printf("%7d", root->key);
In1(root->pright);
}
}
}
//===================================
//In Noi Dung Cac Nut Trong Cay Chia Het Cho X (Dieu Kien F)
void In2(TREE root, int x) {
if (root) //if (root != NULL)
{
if (root->key % x == 0) {
In2(root->pleft, x);
//Xu Ly Nut Goc (IN)
printf("%7d", root->key);
In2(root->pright, x);
}
}
}
//===================================
//Dem So Nut Trong Cay >= X, <= Y (Dieu Kien F)
void In3(TREE root, int x, int y) {
int d = 0;
if (root) //if (root != NULL)
{
int d = 0;
if ((root->key >= x) && (root->key <= y)) {
In3(root->pleft, x, y);
//Xu Ly Nut Goc (IN)
printf("%7d", root->key);
In3(root->pright, x, y);
}
}
}
//////////////////////////////////////
int Dem_Nut_La_Chia_Het_Cho_x(TREE root, int x) {
if (root == NULL) {
return 0; // Cay rong
}
if (root->pleft == NULL && root->pright == NULL) {
// Nut la
if (root->key % x == 0) {
return 1; // Nut la co noi dung chia het cho x
}
}
// De quy den nhanh con trai va phai
return Dem_Nut_La_Chia_Het_Cho_x(root->pleft, x) + Dem_Nut_La_Chia_Het_Cho_x(root->pright, x);
}
void In_Nut_Bac_Lon_Hon_1_Doan_XY_NLR(TREE root, int x, int y) {
if (root != NULL) {
// Kiem tra nut hien tai co bac >= 1 va gia tri trong doan [x, y] hay khong
if ((root->pleft != NULL || root->pright != NULL) && (root->key >= x && root->key <= y)) {
printf("%d ", root->key); // In gia tri nut
}
// Duyet tiep nhanh con trai
In_Nut_Bac_Lon_Hon_1_Doan_XY_NLR(root->pleft, x, y);
// Duyet tiep nhanh con phai
In_Nut_Bac_Lon_Hon_1_Doan_XY_NLR(root->pright, x, y);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment