CHIỀU CAO CỦA CÂY NHỊ PHÂN
Để xác định chiều cao cây ta xác định như sau:
Code:
int HeightTree(Tree T) {
if( T == NULL)
return 0;
else
return Max(HeightTree(T->Left),HeightTree(T->Right)) + 1;
}
Sau khi xác định xong chiều cao của cây sẽ là Max(HeightTree(T)-1, 0) vì cây rỗng và cây chỉ có nút gốc thì nó có độ cao là 0. HeightTree(T)-1 vì chiều cao của cây được tính bắt đầu từ 0.
Chương trình minh họa:
Code:
/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"
//Cau truc cua Node
typedef struct Node{
int info;
Node*Left;
Node*Right;
}Node;
//Dinh nghia cay nhi phan
typedef Node * Tree;
//Khoi tao Node
Node* MakeNode(int x) {
Node *p = new Node();
p ->info = x;
p ->Left = NULL;
p ->Right = NULL;
return p;
}
//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Tree *T, Node *p) {
if (p->info < (*T)->info ) {
if((*T)->Left)
InsertNode(&(*T)->Left,p);
else
(*T)->Left = p;
}
else
if (p->info > (*T)->info){
if((*T)->Right)
InsertNode(&(*T)->Right,p);
else
(*T)->Right = p;
}
}
//Thu tuc them node cho cay ban dau
void PushNode(Tree *T,int x) {
Tree p = MakeNode(x);
if (*T == NULL)
*T = p;
else
InsertNode(&*T,p);
}
//Nhap cac Node vao cay
void InputTree(Tree *T) {
int x;
printf("Nhap vao cac phan tu trong cay nhi phan tim kiem.\n");
printf("Nhap so 0 thi ket thuc:");
do {
scanf("%d",&x);
if (x != 0)
PushNode(&*T,x);
} while(x != 0);
}
//tra ve gia tri lon nhat trong hai so a va b
int Max(int a, int b) {
if(a>b)
return a;
else
return b;
}
//chieu cao cay
int HeightTree(Tree T) {
if( T == NULL)
return 0;
else
return Max(HeightTree(T->Left),HeightTree(T->Right)) + 1;
}
//chuong trinh chinh
void main() {
Tree T = NULL; //Khoi tao cay ban dau
int n;
clrscr();
InputTree(&T);
printf("Chieu cao = %d",Max(HeightTree(T)-1,0));
getch();
}