Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Cây tìm kiếm nhị phân - Chiều cao của cây

Share

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Cây tìm kiếm nhị phân - Chiều cao của cây

Bài gửi  admin on Thu Apr 29, 2010 8:57 am

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();
}

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Cách 2: xác định chiều cao của cây

Bài gửi  admin on Sat Mar 05, 2011 6:03 pm

Thuật toán:
Code:
//chieu cao cay
int HeightTree(Tree T) {
   if( T == NULL)
      return -1;
   else
   if(T->Left == NULL && T->Right == NULL)
      return 0;
   else
   if(T->Left != NULL && T->Right != NULL)
      return Max(HeightTree(T->Left),HeightTree(T->Right)) + 1;
   else
   if(T->Left == NULL)
      return 1 + HeightTree(T->Right);
   else
      return 1 + HeightTree(T->Left);
}

CHƯƠNG TRÌNH MẪU
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 -1;
   else
   if(T->Left == NULL && T->Right == NULL)
      return 0;
   else
   if(T->Left != NULL && T->Right != NULL)
      return Max(HeightTree(T->Left),HeightTree(T->Right)) + 1;
   else
   if(T->Left == NULL)
      return 1 + HeightTree(T->Right);
   else
      return 1 + HeightTree(T->Left);
}
//chuong trinh chinh
void main() {
   Tree T = NULL;   //Khoi tao cay ban dau
   int n;
   clrscr();
   InputTree(&T);
   printf("Chieu cao =  %d",HeightTree(T));
   getch();
}

    Hôm nay: Fri Dec 09, 2016 7:03 am