XÁC ĐỊNH CHIỀU CAO CỦA CÂY TỔNG QUÁT


Chiều cao của cây là chiều cao của nút gốc tới nút lá với chiều cao là cao nhất.
Ý tưởng:
    - Xác định độ sâu của 1 nút bất kỳ.
    - Tính độ sâu của tất cả các nút trên cây, tìm ra độ sâu lớn nhất đó chính là chiều cao của cây.


Xét cấu trúc dữ liệu của cây tổng quát.

Code:

#define MAXLENGTH 100   //chi so toi da cua mang
#define NIL -1
typedef char DataType;
typedef int Node;
typedef struct {
   DataType Data[MAXLENGTH];   //Luu gia tri cua nut
   Node Parent[MAXLENGTH];      //Cha cua nut i se luu o vi tri i trong mang
   int MaxNode;
}Tree;


Hàm tính độ sâu của một nút.

Code:

//Do sau cua node p
int DepthNode(Node p, Tree T) {
   if(p>=0|| p<T.MaxNode) {
      int temp = 0;
      while(p!=Root(T)) {
         p = T.Parent[p];
         temp++;
      }
      return temp;
   }
   else
      return NIL;
}


Hàm tính chiều cao của cây.

Code:

int HeightTree(Tree T) {
   int Max = NIL;
   for(int i = T.MaxNode-1; i>=0; i--)
      if(Max < DepthNode(i,T))
         Max = DepthNode(i,T);
   return Max;
}


Chương trình minh họa.

Code:

/* Chuong trinh cai dat cay tong quat bang mang - tinh chieu cao cua cay*/
#include "conio.h"
#include "stdio.h"

#define MAXLENGTH 100   //chi so toi da cua mang
#define NIL -1
typedef char DataType;
typedef int Node;
typedef struct {
   DataType Data[MAXLENGTH];   //Luu gia tri cua nut
   Node Parent[MAXLENGTH];      //Cha cua nut i se luu o vi tri i trong mang
   int MaxNode;
}Tree;

//Khoi tao cay rong
void MakeNull_Tree (Tree *T)
{
   (*T).MaxNode=0;
}
//Kiem tra cay rong
int EmptyTree(Tree T)
{
   return T.MaxNode == 0;
}
//Xac dinh nut cha cua nut tren cay
Node Parent(Node n,Tree T)
{
   if (EmptyTree(T) || (n>T.MaxNode-1))
      return NIL;
   else
      return T.Parent[n];
}
//Xac dinh gia tri cua nut tren cay
DataType Label_Node(Node n,Tree T)
{
   if (!EmptyTree(T) && (n<=T.MaxNode-1))
      return T.Data[n];
   else
      return 13;  //ky ty Enter
}
//Xac dinh nut goc trong cay
Node Root(Tree T)
{
   if (!EmptyTree(T))
      return 0;
   else
      return NIL;
}
//Do sau cu nut p
int DepthNode(Node p, Tree T) {
   if(p>=0|| p<T.MaxNode) {
      int temp = 0;
      while(p!=Root(T)) {
         p = T.Parent[p];
         temp++;
      }
      return temp;
   }
   else
      return NIL;
}
//Chieu cao cua cay
int HeightTree(Tree T) {
   int Max = NIL;
   for(int i = T.MaxNode-1; i>=0; i--)
      if(Max < DepthNode(i,T))
         Max = DepthNode(i,T);
   return Max;
}
//Doc cay
void ReadTree(Tree *T){
   int i;
   MakeNull_Tree(&*T);
   do {
      printf("Cay co bao nhieu nut? ");
      scanf("%d",&(*T).MaxNode);
   } while (((*T).MaxNode<1) || ((*T).MaxNode>MAXLENGTH));
   printf("Nhap nhan cua nut goc: ");
   fflush(stdin);
   scanf("%c",&(*T).Data[0]);
   (*T).Parent[0]=NIL; /* nut goc khong co cha */
   for (i=1;i<=(*T).MaxNode-1;i++){
      printf("Nhap cha cua nut %d: ",i);
      scanf("%d",&(*T).Parent[i]);
      printf("Nhap nhan cua nut %d: ",i);
      fflush(stdin);
      scanf("%c",&(*T).Data[i]);
   }
}
//Chuong trinh chinh
void main(){
   clrscr();
   Tree T;   
   printf("Nhap du lieu cho cay tong quat\n");
   ReadTree(&T);
   if(HeightTree(T)!=NIL)
      printf("Chieu cao cua cay la: %d", HeightTree(T));
   else
      printf("Cay rong!!!");
   getch();
}