Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn Phí
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn PhíĐăng Nhập

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


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

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

descriptionCây tìm kiếm nhị phân - Chiều cao của cây EmptyCách 2: xác định chiều cao của cây

more_horiz
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();
}
privacy_tip Permissions in this forum:
Bạn không có quyền trả lời bài viết
power_settings_newLogin to reply