[quote]Dưới đây là các bài tập về cây nhị phân cho các bác nhà ta đây
Viết hàm xuất các giá trị trong cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
// Viết hàm xuất các giá trị trong cây
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("Xuat cay LNR (Tang dan): ");
Xuat(c);
}
Viết hàm xuất các giá trị chẵn trong cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//871 Viết hàm xuất các giá trị chẵn trong cây
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
if (c->iX % 2 == 0)
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("Xuat gia tri chan theo LNR (Tang dan): ");
Xuat(c);
}
viết xuất địa chỉ các nút trên cây có giá trị (khoá) lớn hơn x và nhỏ hơn y
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//872 Viết hàm xuất địa chỉ các nút trên cây có giá trị (Khóa) lớn hơn X và nhỏ hơn Y
void Xuat(Tree c, int x, int y)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft,x,y);
if (xiX && c->iX
printf("\n%4d", &c);
if (c->pRight != NULL)
Xuat(c->pRight,x,y);
}
}
void NhapXY(int &x, int &y)
{
printf("Nhap x: ");
scanf_s("%d",&x);
printf("Nhap y: ");
scanf_s("%d",&y);
}
void main()
{
Tree c = NULL;
Nhap(c);
int x,y;
NhapXY(x,y);
printf("\nXuat dia chi < x va > y: ");
Xuat(c,x,y);
}
Viết hàm xuất các số hoàn thiện trong cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//873 Viết hàm xuất các số hoàn thiện trong cây
bool SoHoanThien(int x)
{
int s=0;
for (int i=1; i
if (x%i==0)
s+=i;
if (s==x)
return true;
return false;
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
if (SoHoanThien(c->iX))
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("Xuat cac so hoan thien theo LNR: ");
Xuat(c);
}
Viết hàm xuất tất cả các nút trên tầng thứ k của cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//874* Viết hàm xuất các nút trên tầng thứ k của cây
void Xuat(Tree c, int k)
{
if (c!=NULL)
{
k--;
if (c->pLeft != NULL)
Xuat(c->pLeft,k);
if (k==0)
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight,k);
}
}
void NhapK(int &k)
{
printf("\nNhap tang thu k: ");
scanf_s("%d",&k);
}
void main()
{
Tree c = NULL;
Nhap(c);
int k;
NhapK(k);
printf("\nXuat cac gia tri tang thu k cua cay theo LNR: ");
Xuat(c,k+1);
}
Viết hàm xuất tất cả các nút trên cây theo thứ tự từ tầng 0 đến tầng h-1 củacây (với h là chiều cao của cây)
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//875* Viết hàm xuất các nút trên cây theo thứ tự tầng 0 đến tầng h-1 của cây (với h là chiều cao của cây)
int ChieuCaoCay(Tree c)
{
if (c == NULL)
return 0;
int a = ChieuCaoCay(c->pLeft);
int b = ChieuCaoCay(c->pRight);
int max = (a>b)?a:b;
return 1 + max;
}
void XuatTheoTangK(Tree c, int k)
{
if (c!=NULL)
{
k--;
if (c->pLeft != NULL)
XuatTheoTangK(c->pLeft,k);
if (k==0)
printf("%4d", c->iX);
if (c->pRight != NULL)
XuatTheoTangK(c->pRight,k);
}
}
void Xuat(Tree c)
{
int h = ChieuCaoCay(c);
printf ("\nChieu cao cay: %d",h);
for (int i=0; i<=h-1; i++)
{
printf("\n tang %d :", i);
XuatTheoTangK(c,i+1);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cac gia tri theo thu tu tang 0 -> h-1: ");
Xuat(c);
}
Đếm số lượng nút có đúng 1 con
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//876 Đếm số lượng nút có đúng 1 con
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if ((c->pLeft != NULL && c->pRight == NULL) || (c->pLeft == NULL && c->pRight != NULL))
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 1 con: %d", Dem(c));
}
Đếm số lượng nút có đúng 2 con
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//877 Đếm số lượng nút có đúng 2 con
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (c->pLeft != NULL && c->pRight != NULL)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 2 con: %d", Dem(c));
}
Đếm số lượng nút chẵn
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//878 Đếm số lượng nút chẵn
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (c->iX%2==0)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut chan: %d", Dem(c));
}
Đếm số lượng nút lá mà thông tin tại nút đó là giá trị chẵn
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//879 Đếm số lượng nút lá mà thông tin tại nút đó là giá trị chẵn
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (c->iX%2==0 && c->pLeft == NULL && c->pRight == NULL)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut la ma gia tri chan: %d", Dem(c));
}
Đếm số lượng nút có đúng 1 con mà thông tin tại nút đó là số nguyên tố
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//880 Đếm số lượng nút có đúng 1 con mà thông tin tại đó là số nguyên tố
bool SoNguyenTo(int n)
{
if (n<=1)
return 0;
for (int i=2; i
if (n%i == 0)
return 0;
return 1;
}
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (SoNguyenTo(c->iX))
if ((c->pLeft!=NULL && c->pRight==NULL) || (c->pLeft==NULL && c->pRight!=NULL))
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 1 con va gia tri la so nguyen to: %d", Dem(c));
}
Đếm số lượng nút có đúng 2 con mà thông tin tại nút đó là số chính phương
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//881 Đếm số lượng nút có đúng 2 con mà thông tin tại đó là số chính phương
bool SoChinhPhuong(int n)
{
if (n<=0)
return 0;
int s = sqrt((double)n);
if (s*s == n)
return 1;
return 0;
}
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (SoChinhPhuong(c->iX))
if (c->pLeft!=NULL && c->pRight!=NULL)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 2 con va gia tri la so chinh phuong: %d", Dem(c));
}
Đếm số lượng nút trên tầng thứ k của cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//882 Đếm số lượng nút trên tầng thứ k
int Dem(Tree c, int k)
{
if (c!=NULL)
{
k--;
int a = Dem(c->pLeft,k);
int b = Dem(c->pRight,k);
if (k==0)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut tren tang thu k: %d", Dem(c,2));
}
Đếm số lượng nút nằm ở tầng thấp hơn tầng thứ k của cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//883 Đếm số lượng nút nằm ở tầng thấp hơn tầng thứ k trên cây
int DemTangThuk(Tree c, int k)
{
if (c!=NULL)
{
k--;
int a = DemTangThuk(c->pLeft,k);
int b = DemTangThuk(c->pRight,k);
if (k==0)
return 1 + a + b;
return a + b;
}
return 0;
}
int Dem(Tree c, int k)
{
if (c!=NULL)
{
int DemSoLuong = 0;
for (int i=1;i
{
DemSoLuong += DemTangThuk(c,i);
}
return DemSoLuong;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut nam o tang thap hon tang thu k: %d", Dem(c,2));
}
Đếm số lượng nút nằm ở tầng cao hơn tầng thứ k của cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//884 Đếm số lượng nút nằm ở tầng cao hơn tầng thứ k trên cây
int ChieuCaoCay(Tree c)
{
if (c!=NULL)
{
int a = ChieuCaoCay(c->pLeft);
int b = ChieuCaoCay(c->pRight);
int max = (a>b)?a:b;
return 1 + max;
}
return 0;
}
int DemTangThuk(Tree c, int k)
{
if (c!=NULL)
{
k--;
int a = DemTangThuk(c->pLeft,k);
int b = DemTangThuk(c->pRight,k);
if (k==0)
return 1 + a + b;
return a + b;
}
return 0;
}
int Dem(Tree c, int k)
{
if (c!=NULL)
{
int DemSoLuong = 0;
for (int i=k;i
{
DemSoLuong += DemTangThuk(c,i);
}
return DemSoLuong;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut nam o tang cao hon tang thu k: %d", Dem(c,2));
}
Tính tổng các nút trong cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//885 Tính tổng các nút trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
return c->iX + a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut trong cay: %d", Tinh(c));
}
Tính tổng các nút lá trong cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//886 Tính tổng các nút lá trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->pLeft == NULL && c->pRight == NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut lá trong cay: %d", Tinh(c));
}
Tính tổng các nút có đúng một con
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//887 Tính tổng các nút có đúng 1 con trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if ((c->pLeft != NULL && c->pRight == NULL) || (c->pLeft == NULL && c->pRight != NULL))
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut co dung 1 con trong cay: %d", Tinh(c));
}
Tính tổng các nút có đúng hai con
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//888 Tính tổng các nút có đúng 2 con trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->pLeft != NULL && c->pRight != NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut co dung 2 con trong cay: %d", Tinh(c));
}
Tính tổng các nút lẻ
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//889 Tính tổng các nút lẻ
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->iX % 2 != 0)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut le: %d", Tinh(c));
}
tính tổng các nút lá mà thông tin tại nút đó là giá trị chẵn
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//890 Tính tổng các nút lá mà thông tin tại nút đó là giá trị chẵn
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->iX % 2 == 0)
if (c->pLeft == NULL && c->pRight == NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut la co gia tri chan: %d", Tinh(c));
}
Tính tổng các nút có đúng 1 con mà thông tin tại nút đó là số nguyên tố
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//891 Tính tổng các nút có đúng một con mà thông tin nút đó là số nguyên tố
bool SoNguyenTo(int n)
{
if (n<=1)
return false;
for (int i=2; i
if(n%i==0)
return false;
return true;
}
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (SoNguyenTo(c->iX))
if ((c->pLeft != NULL && c->pRight == NULL) && (c->pLeft == NULL && c->pRight != NULL))
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut dung 1 con co gia tri so nguyen to: %d", Tinh(c));
}
Tính tổng các nút có đúng 2 con mà thông tin tại nút đó là số chính phương
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//892 Tính tổng các nút có đúng hai con mà thông tin nút đó là số chính phương
bool SoChinhPhuong(int n)
{
int a = sqrt((double)n);
if (a*a != n)
return false;
return true;
}
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (SoChinhPhuong(c->iX))
if (c->pLeft != NULL && c->pRight != NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut dung 2 con co gia tri so chinh phuong: %d", Tinh(c));
}
Tính chiều cao cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//893 Tính chiều cao cây
int ChieuCao(Tree c)
{
if (c!=NULL)
{
int a = ChieuCao(c->pLeft);
int b = ChieuCao(c->pRight);
int max = (a>b)?a:b;
return 1 + max;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh chieu cao cay: %d", Tinh(c));
}
Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" haykhông?
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//894 Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không?
//0 là cây nhị phân
//1 ko phải là cây nhị phân
void TimMax(Tree c, int &Max)
{
if (c==NULL)
return ;
if (c->pLeft != NULL)
Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
if (c->pRight != NULL)
Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
Max = (Max > c->iX) ? Max : c->iX;
TimMax(c->pLeft,Max);
TimMax(c->pRight,Max);
}
int KiemTra(Tree c)
{
if (c==NULL)
return 0;
int Left = KiemTra(c->pLeft);
int MaxL, MaxR;
if (c->pLeft != NULL && c->pRight != NULL)
{
TimMax(c->pLeft, MaxL);
TimMax(c->pRight, MaxR);
if (!(MaxL < c->iX && c->iX < MaxR))
return 1;
}
else if (c->pLeft == NULL && c->pRight != NULL)
{
TimMax(c->pRight, MaxR);
if (!(c->iX < MaxR))
return 1;
}
else if (c->pLeft != NULL && c->pRight == NULL)
{
TimMax(c->pLeft, MaxL);
if (!(MaxL < c->iX))
return 1;
}
int Right = KiemTra(c->pRight);
return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
int Kt = KiemTra(c);
if (Kt == 0)
printf("\nla cay nhi phan tim kiem");
else
printf("\nko phai cay nhi phan tim kiem");
}
void main()
{
//Dùng để nhập cây nhị phân tìm kiếm
/*Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);*/
//Mẫu tree 1 để test: mẫu này ko phải là cây nhị phân tìm kiếm
//Tree c = NULL;
//c = TaoNode(4);
//Node* a = TaoNode(3);
//c->pLeft = a;
//Node* a1 = TaoNode(2);
//a->pLeft = a1;
//Node* a2 = TaoNode(6);
//a->pRight = a2;
//Node* b1 = TaoNode(5);
//c->pRight = b1;
//Node* b2 = TaoNode(1);
//b1->pLeft = b2;
//Node* b3 = TaoNode(7);
//b1->pRight = b3;
//Node* b4 = TaoNode(0);
//b2->pLeft = b4;
//Node* b5 = TaoNode(;
//b2->pRight = b5;
//Mẫu tree 2 để test: mẫu này ko phải là cây nhị phân tìm kiếm
/*Tree c = TaoNode(10);
Node* a1 = TaoNode(;
Node* a2 = TaoNode(2);
Node* a3 = TaoNode(11);
c->pLeft = a1;
a1->pLeft = a2;
a1->pRight = a3;*/
//Mẫu tree 3 để test: mẫu này là cây nhị phân tìm kiếm
Tree c = TaoNode(10);
Node* a1 = TaoNode(;
Node* a2 = TaoNode(2);
Node* a3 = TaoNode(9);
Node* b1 = TaoNode(12);
c->pLeft = a1;
c->pRight = b1;
a1->pLeft = a2;
a1->pRight = a3;
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
XuatKqKiemTra(c);
}
Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng" haykhông?
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//895 Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng" hay không?
//Cây nhị phân cân bằng là cây nhị phân tìm kiếm mà tại mỗi nút của nó
//độ cao của cây con trái và cây con phải chêch lệch ko quá 1
//0 là cây nhị phân tìm kiếm
//1 ko phải là cây nhị phân tìm kiếm
void TimMax(Tree c, int &Max)
{
if (c==NULL)
return ;
if (c->pLeft != NULL)
Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
if (c->pRight != NULL)
Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
Max = (Max > c->iX) ? Max : c->iX;
TimMax(c->pLeft,Max);
TimMax(c->pRight,Max);
}
int DoCao(Tree c)
{
if (c==NULL)
return 0;
int DoCaoR = DoCao(c->pRight);
int DoCaoL = DoCao(c->pLeft);
int max = (DoCaoR > DoCaoL) ? DoCaoR : DoCaoL;
return max + 1;
}
int KiemTra(Tree c)
{
if (c==NULL)
return 0;
int Left = KiemTra(c->pLeft);
//kiểm tra điều kiện của cây nhị phân tìm kiếm
int MaxL, MaxR;
if (c->pLeft != NULL && c->pRight != NULL)
{
TimMax(c->pLeft, MaxL);
TimMax(c->pRight, MaxR);
if (!(MaxL < c->iX && c->iX < MaxR))
return 1;
}
else if (c->pLeft == NULL && c->pRight != NULL)
{
TimMax(c->pRight, MaxR);
if (!(c->iX < MaxR))
return 1;
}
else if (c->pLeft != NULL && c->pRight == NULL)
{
TimMax(c->pLeft, MaxL);
if (!(MaxL < c->iX))
return 1;
}
//kiểm tra điều kiện của cây nhị phân tìm kiếm cân bằng
int DoCaoR = DoCao(c->pRight);
int DoCaoL = DoCao(c->pLeft);
printf ("\n\tnode: %d lech Right: %d, Left: %d", c->iX,DoCaoR, DoCaoL);
if (abs(DoCaoR - DoCaoL) > 1) //chêch lệch lớn hơn 1
return 1;
int Right = KiemTra(c->pRight);
return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
int Kt = KiemTra(c);
if (Kt == 0)
printf("\nla cay nhi phan tim kiem can bang");
else
printf("\nko phai cay nhi phan tim kiem can bang");
}
void main()
{
//Dùng để nhập cây nhị phân tìm kiếm
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
XuatKqKiemTra(c);
}
Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng hoàntoàn" hay không?
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL[quote]
Viết hàm xuất các giá trị trong cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
// Viết hàm xuất các giá trị trong cây
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("Xuat cay LNR (Tang dan): ");
Xuat(c);
}
Viết hàm xuất các giá trị chẵn trong cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//871 Viết hàm xuất các giá trị chẵn trong cây
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
if (c->iX % 2 == 0)
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("Xuat gia tri chan theo LNR (Tang dan): ");
Xuat(c);
}
viết xuất địa chỉ các nút trên cây có giá trị (khoá) lớn hơn x và nhỏ hơn y
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//872 Viết hàm xuất địa chỉ các nút trên cây có giá trị (Khóa) lớn hơn X và nhỏ hơn Y
void Xuat(Tree c, int x, int y)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft,x,y);
if (x
printf("\n%4d", &c);
if (c->pRight != NULL)
Xuat(c->pRight,x,y);
}
}
void NhapXY(int &x, int &y)
{
printf("Nhap x: ");
scanf_s("%d",&x);
printf("Nhap y: ");
scanf_s("%d",&y);
}
void main()
{
Tree c = NULL;
Nhap(c);
int x,y;
NhapXY(x,y);
printf("\nXuat dia chi < x va > y: ");
Xuat(c,x,y);
}
Viết hàm xuất các số hoàn thiện trong cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//873 Viết hàm xuất các số hoàn thiện trong cây
bool SoHoanThien(int x)
{
int s=0;
for (int i=1; i
if (x%i==0)
s+=i;
if (s==x)
return true;
return false;
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
if (SoHoanThien(c->iX))
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("Xuat cac so hoan thien theo LNR: ");
Xuat(c);
}
Viết hàm xuất tất cả các nút trên tầng thứ k của cây
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//874* Viết hàm xuất các nút trên tầng thứ k của cây
void Xuat(Tree c, int k)
{
if (c!=NULL)
{
k--;
if (c->pLeft != NULL)
Xuat(c->pLeft,k);
if (k==0)
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight,k);
}
}
void NhapK(int &k)
{
printf("\nNhap tang thu k: ");
scanf_s("%d",&k);
}
void main()
{
Tree c = NULL;
Nhap(c);
int k;
NhapK(k);
printf("\nXuat cac gia tri tang thu k cua cay theo LNR: ");
Xuat(c,k+1);
}
Viết hàm xuất tất cả các nút trên cây theo thứ tự từ tầng 0 đến tầng h-1 củacây (với h là chiều cao của cây)
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
//875* Viết hàm xuất các nút trên cây theo thứ tự tầng 0 đến tầng h-1 của cây (với h là chiều cao của cây)
int ChieuCaoCay(Tree c)
{
if (c == NULL)
return 0;
int a = ChieuCaoCay(c->pLeft);
int b = ChieuCaoCay(c->pRight);
int max = (a>b)?a:b;
return 1 + max;
}
void XuatTheoTangK(Tree c, int k)
{
if (c!=NULL)
{
k--;
if (c->pLeft != NULL)
XuatTheoTangK(c->pLeft,k);
if (k==0)
printf("%4d", c->iX);
if (c->pRight != NULL)
XuatTheoTangK(c->pRight,k);
}
}
void Xuat(Tree c)
{
int h = ChieuCaoCay(c);
printf ("\nChieu cao cay: %d",h);
for (int i=0; i<=h-1; i++)
{
printf("\n tang %d :", i);
XuatTheoTangK(c,i+1);
}
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cac gia tri theo thu tu tang 0 -> h-1: ");
Xuat(c);
}
Đếm số lượng nút có đúng 1 con
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//876 Đếm số lượng nút có đúng 1 con
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if ((c->pLeft != NULL && c->pRight == NULL) || (c->pLeft == NULL && c->pRight != NULL))
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 1 con: %d", Dem(c));
}
Đếm số lượng nút có đúng 2 con
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//877 Đếm số lượng nút có đúng 2 con
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (c->pLeft != NULL && c->pRight != NULL)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 2 con: %d", Dem(c));
}
Đếm số lượng nút chẵn
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//878 Đếm số lượng nút chẵn
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (c->iX%2==0)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut chan: %d", Dem(c));
}
Đếm số lượng nút lá mà thông tin tại nút đó là giá trị chẵn
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//879 Đếm số lượng nút lá mà thông tin tại nút đó là giá trị chẵn
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (c->iX%2==0 && c->pLeft == NULL && c->pRight == NULL)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut la ma gia tri chan: %d", Dem(c));
}
Đếm số lượng nút có đúng 1 con mà thông tin tại nút đó là số nguyên tố
PHP Code:
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//880 Đếm số lượng nút có đúng 1 con mà thông tin tại đó là số nguyên tố
bool SoNguyenTo(int n)
{
if (n<=1)
return 0;
for (int i=2; i
if (n%i == 0)
return 0;
return 1;
}
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (SoNguyenTo(c->iX))
if ((c->pLeft!=NULL && c->pRight==NULL) || (c->pLeft==NULL && c->pRight!=NULL))
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 1 con va gia tri la so nguyen to: %d", Dem(c));
}
Đếm số lượng nút có đúng 2 con mà thông tin tại nút đó là số chính phương
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//881 Đếm số lượng nút có đúng 2 con mà thông tin tại đó là số chính phương
bool SoChinhPhuong(int n)
{
if (n<=0)
return 0;
int s = sqrt((double)n);
if (s*s == n)
return 1;
return 0;
}
int Dem(Tree c)
{
if (c!=NULL)
{
int a = Dem(c->pLeft);
int b = Dem(c->pRight);
if (SoChinhPhuong(c->iX))
if (c->pLeft!=NULL && c->pRight!=NULL)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut co dung 2 con va gia tri la so chinh phuong: %d", Dem(c));
}
Đếm số lượng nút trên tầng thứ k của cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//882 Đếm số lượng nút trên tầng thứ k
int Dem(Tree c, int k)
{
if (c!=NULL)
{
k--;
int a = Dem(c->pLeft,k);
int b = Dem(c->pRight,k);
if (k==0)
return 1 + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut tren tang thu k: %d", Dem(c,2));
}
Đếm số lượng nút nằm ở tầng thấp hơn tầng thứ k của cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//883 Đếm số lượng nút nằm ở tầng thấp hơn tầng thứ k trên cây
int DemTangThuk(Tree c, int k)
{
if (c!=NULL)
{
k--;
int a = DemTangThuk(c->pLeft,k);
int b = DemTangThuk(c->pRight,k);
if (k==0)
return 1 + a + b;
return a + b;
}
return 0;
}
int Dem(Tree c, int k)
{
if (c!=NULL)
{
int DemSoLuong = 0;
for (int i=1;i
{
DemSoLuong += DemTangThuk(c,i);
}
return DemSoLuong;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut nam o tang thap hon tang thu k: %d", Dem(c,2));
}
Đếm số lượng nút nằm ở tầng cao hơn tầng thứ k của cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//884 Đếm số lượng nút nằm ở tầng cao hơn tầng thứ k trên cây
int ChieuCaoCay(Tree c)
{
if (c!=NULL)
{
int a = ChieuCaoCay(c->pLeft);
int b = ChieuCaoCay(c->pRight);
int max = (a>b)?a:b;
return 1 + max;
}
return 0;
}
int DemTangThuk(Tree c, int k)
{
if (c!=NULL)
{
k--;
int a = DemTangThuk(c->pLeft,k);
int b = DemTangThuk(c->pRight,k);
if (k==0)
return 1 + a + b;
return a + b;
}
return 0;
}
int Dem(Tree c, int k)
{
if (c!=NULL)
{
int DemSoLuong = 0;
for (int i=k;i
{
DemSoLuong += DemTangThuk(c,i);
}
return DemSoLuong;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nDem so luong nut nam o tang cao hon tang thu k: %d", Dem(c,2));
}
Tính tổng các nút trong cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//885 Tính tổng các nút trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
return c->iX + a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut trong cay: %d", Tinh(c));
}
Tính tổng các nút lá trong cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//886 Tính tổng các nút lá trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->pLeft == NULL && c->pRight == NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut lá trong cay: %d", Tinh(c));
}
Tính tổng các nút có đúng một con
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//887 Tính tổng các nút có đúng 1 con trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if ((c->pLeft != NULL && c->pRight == NULL) || (c->pLeft == NULL && c->pRight != NULL))
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut co dung 1 con trong cay: %d", Tinh(c));
}
Tính tổng các nút có đúng hai con
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//888 Tính tổng các nút có đúng 2 con trong cây
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->pLeft != NULL && c->pRight != NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut co dung 2 con trong cay: %d", Tinh(c));
}
Tính tổng các nút lẻ
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//889 Tính tổng các nút lẻ
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->iX % 2 != 0)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut le: %d", Tinh(c));
}
tính tổng các nút lá mà thông tin tại nút đó là giá trị chẵn
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//890 Tính tổng các nút lá mà thông tin tại nút đó là giá trị chẵn
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (c->iX % 2 == 0)
if (c->pLeft == NULL && c->pRight == NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut la co gia tri chan: %d", Tinh(c));
}
Tính tổng các nút có đúng 1 con mà thông tin tại nút đó là số nguyên tố
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//891 Tính tổng các nút có đúng một con mà thông tin nút đó là số nguyên tố
bool SoNguyenTo(int n)
{
if (n<=1)
return false;
for (int i=2; i
if(n%i==0)
return false;
return true;
}
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (SoNguyenTo(c->iX))
if ((c->pLeft != NULL && c->pRight == NULL) && (c->pLeft == NULL && c->pRight != NULL))
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut dung 1 con co gia tri so nguyen to: %d", Tinh(c));
}
Tính tổng các nút có đúng 2 con mà thông tin tại nút đó là số chính phương
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//892 Tính tổng các nút có đúng hai con mà thông tin nút đó là số chính phương
bool SoChinhPhuong(int n)
{
int a = sqrt((double)n);
if (a*a != n)
return false;
return true;
}
int Tinh(Tree c)
{
if (c!=NULL)
{
int a = Tinh(c->pLeft);
int b = Tinh(c->pRight);
if (SoChinhPhuong(c->iX))
if (c->pLeft != NULL && c->pRight != NULL)
return c->iX + a + b;
return a + b;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh tong cac nut dung 2 con co gia tri so chinh phuong: %d", Tinh(c));
}
Tính chiều cao cây
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//893 Tính chiều cao cây
int ChieuCao(Tree c)
{
if (c!=NULL)
{
int a = ChieuCao(c->pLeft);
int b = ChieuCao(c->pRight);
int max = (a>b)?a:b;
return 1 + max;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
printf("\nTinh chieu cao cay: %d", Tinh(c));
}
Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" haykhông?
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//894 Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không?
//0 là cây nhị phân
//1 ko phải là cây nhị phân
void TimMax(Tree c, int &Max)
{
if (c==NULL)
return ;
if (c->pLeft != NULL)
Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
if (c->pRight != NULL)
Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
Max = (Max > c->iX) ? Max : c->iX;
TimMax(c->pLeft,Max);
TimMax(c->pRight,Max);
}
int KiemTra(Tree c)
{
if (c==NULL)
return 0;
int Left = KiemTra(c->pLeft);
int MaxL, MaxR;
if (c->pLeft != NULL && c->pRight != NULL)
{
TimMax(c->pLeft, MaxL);
TimMax(c->pRight, MaxR);
if (!(MaxL < c->iX && c->iX < MaxR))
return 1;
}
else if (c->pLeft == NULL && c->pRight != NULL)
{
TimMax(c->pRight, MaxR);
if (!(c->iX < MaxR))
return 1;
}
else if (c->pLeft != NULL && c->pRight == NULL)
{
TimMax(c->pLeft, MaxL);
if (!(MaxL < c->iX))
return 1;
}
int Right = KiemTra(c->pRight);
return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
int Kt = KiemTra(c);
if (Kt == 0)
printf("\nla cay nhi phan tim kiem");
else
printf("\nko phai cay nhi phan tim kiem");
}
void main()
{
//Dùng để nhập cây nhị phân tìm kiếm
/*Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);*/
//Mẫu tree 1 để test: mẫu này ko phải là cây nhị phân tìm kiếm
//Tree c = NULL;
//c = TaoNode(4);
//Node* a = TaoNode(3);
//c->pLeft = a;
//Node* a1 = TaoNode(2);
//a->pLeft = a1;
//Node* a2 = TaoNode(6);
//a->pRight = a2;
//Node* b1 = TaoNode(5);
//c->pRight = b1;
//Node* b2 = TaoNode(1);
//b1->pLeft = b2;
//Node* b3 = TaoNode(7);
//b1->pRight = b3;
//Node* b4 = TaoNode(0);
//b2->pLeft = b4;
//Node* b5 = TaoNode(;
//b2->pRight = b5;
//Mẫu tree 2 để test: mẫu này ko phải là cây nhị phân tìm kiếm
/*Tree c = TaoNode(10);
Node* a1 = TaoNode(;
Node* a2 = TaoNode(2);
Node* a3 = TaoNode(11);
c->pLeft = a1;
a1->pLeft = a2;
a1->pRight = a3;*/
//Mẫu tree 3 để test: mẫu này là cây nhị phân tìm kiếm
Tree c = TaoNode(10);
Node* a1 = TaoNode(;
Node* a2 = TaoNode(2);
Node* a3 = TaoNode(9);
Node* b1 = TaoNode(12);
c->pLeft = a1;
c->pRight = b1;
a1->pLeft = a2;
a1->pRight = a3;
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
XuatKqKiemTra(c);
}
Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng" haykhông?
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL;
p->iX=X;
return p;
}
void ThemNodeVaoCay(Node* p, Tree &c)
{
if (c == NULL)//nếu cây rỗng
c = p;
else //cây khác rỗng
{
if (p->iX < c->iX)
ThemNodeVaoCay(p,c->pLeft);
else if (p->iX > c->iX)
ThemNodeVaoCay(p,c->pRight);
else
return;
}
}
void Nhap(Tree &c)
{
int chon = 0;
do
{
int x;
printf("\nNhap x: ");
scanf_s("%d",&x);
Node* p = TaoNode(x);
ThemNodeVaoCay(p,c);
printf("Muon nhap thong tin tiep ko? 1: co, 0: ko ~~>");
scanf_s("%d",&chon);
}while(chon);
}
void Xuat(Tree c)
{
if (c!=NULL)
{
if (c->pLeft != NULL)
Xuat(c->pLeft);
printf("%4d", c->iX);
if (c->pRight != NULL)
Xuat(c->pRight);
}
}
//895 Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng" hay không?
//Cây nhị phân cân bằng là cây nhị phân tìm kiếm mà tại mỗi nút của nó
//độ cao của cây con trái và cây con phải chêch lệch ko quá 1
//0 là cây nhị phân tìm kiếm
//1 ko phải là cây nhị phân tìm kiếm
void TimMax(Tree c, int &Max)
{
if (c==NULL)
return ;
if (c->pLeft != NULL)
Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
if (c->pRight != NULL)
Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
Max = (Max > c->iX) ? Max : c->iX;
TimMax(c->pLeft,Max);
TimMax(c->pRight,Max);
}
int DoCao(Tree c)
{
if (c==NULL)
return 0;
int DoCaoR = DoCao(c->pRight);
int DoCaoL = DoCao(c->pLeft);
int max = (DoCaoR > DoCaoL) ? DoCaoR : DoCaoL;
return max + 1;
}
int KiemTra(Tree c)
{
if (c==NULL)
return 0;
int Left = KiemTra(c->pLeft);
//kiểm tra điều kiện của cây nhị phân tìm kiếm
int MaxL, MaxR;
if (c->pLeft != NULL && c->pRight != NULL)
{
TimMax(c->pLeft, MaxL);
TimMax(c->pRight, MaxR);
if (!(MaxL < c->iX && c->iX < MaxR))
return 1;
}
else if (c->pLeft == NULL && c->pRight != NULL)
{
TimMax(c->pRight, MaxR);
if (!(c->iX < MaxR))
return 1;
}
else if (c->pLeft != NULL && c->pRight == NULL)
{
TimMax(c->pLeft, MaxL);
if (!(MaxL < c->iX))
return 1;
}
//kiểm tra điều kiện của cây nhị phân tìm kiếm cân bằng
int DoCaoR = DoCao(c->pRight);
int DoCaoL = DoCao(c->pLeft);
printf ("\n\tnode: %d lech Right: %d, Left: %d", c->iX,DoCaoR, DoCaoL);
if (abs(DoCaoR - DoCaoL) > 1) //chêch lệch lớn hơn 1
return 1;
int Right = KiemTra(c->pRight);
return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
int Kt = KiemTra(c);
if (Kt == 0)
printf("\nla cay nhi phan tim kiem can bang");
else
printf("\nko phai cay nhi phan tim kiem can bang");
}
void main()
{
//Dùng để nhập cây nhị phân tìm kiếm
Tree c = NULL;
Nhap(c);
printf("\nXuat cay nhi phan LNR: ");
Xuat(c);
XuatKqKiemTra(c);
}
Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng hoàntoàn" hay không?
PHP Code:
#include
#include
struct Node
{
Node* pLeft;
Node* pRight;
int iX;
};
typedef Node* Tree;
Node* TaoNode(int X)
{
Node* p = new Node;
if (p == NULL)
return NULL;
p->pLeft = NULL;
p->pRight = NULL[quote]