cay nhi phan tim kiem 2
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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Dem 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
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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<k; i++)
{
DemSoLuong += DemTangThuk(c,i);
}
return DemSoLuong;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Dem 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
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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<ChieuCaoCay(c); i++)
{
DemSoLuong += DemTangThuk(c,i);
}
return DemSoLuong;
}
return 0;
}
void main()
{
Tree c = NULL;
Nhap(c);
printf("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Dem 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
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh tong cac nut trong cay: %d", Tinh(c));
}
Tính tổng các nút lá trong cây
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh tong cac nut lá trong cay: %d", Tinh(c));
}
Tính tổng các nút có đúng một con
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh tong cac nut co dung 1 con trong cay: %d", Tinh(c));
}
Tính tổng các nút có đúng hai con
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh tong cac nut co dung 2 con trong cay: %d", Tinh(c));
}
Tính tổng các nút lẻ
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh 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
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh 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ố
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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<n; 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh 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
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh tong cac nut dung 2 con co gia tri so chinh phuong: %d", Tinh(c));
}
Tính chiều cao cây
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
Xuat cay nhi phan LNR: ");
Xuat(c);
printf("
Tinh 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?
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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("
la cay nhi phan tim kiem");
else
printf("
ko 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("
Xuat 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(8);
//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(8);
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(8);
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("
Xuat 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?
Code:
#include <stdio.h>
#include <math.h>
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("
Nhap 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 ("
\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("
la cay nhi phan tim kiem can bang");
else
printf("
ko 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("
Xuat 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?
Code:
#include <stdio.h>
#include <math.h>
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;
Bạn đang đọc truyện trên: Truyen247.Pro