DUYỆT THEO MỨC TRÊN CÂY TỔNG QUÁT CÀI ĐẶT BẰNG MẢNG


Thuật toán:

Code:

//Do sau cua nut p
int DepthNode(Node p, Tree T) {
   if((p>=0|| p<T.MaxNode) && !EmptyTree(T)) {
      unsigned 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, temp;
   for(unsigned int i=0; i < T.MaxNode; i++)
   {
      temp = DepthNode(i,T);
      if(Max < temp)
         Max = temp;
   }
   return Max;
}
//Duyet cac nut theo muc cua nut tang dan
void LevelOrder(Tree T) {
   for(int i = 0; i<=HeightTree(T); i++)
      for(unsigned int j = 0; j<T.MaxNode; j++)
         if(DepthNode(j,T)==i)
            printf("%c\t",T.Data[j]);
}


CHƯƠNG TRÌNH MẪU

Code:

/* Chuong trinh cai dat cay tong quat bang mang*/
#include "conio.h"
#include "stdio.h"
#define MAXLENGTH 100   //chi so toi da cua mang
#define NIL -1
typedef char DataType;         //Kieu du lieu cho nhan
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
   unsigned int MaxNode;      //Luu so nut tren cay
}Tree;
//Khoi tao cay rong
void MakeNull_Tree (Tree *T) {
   (*T).MaxNode=0;
}
//Kiem tra cay rong
unsigned char 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))
      return T.Data[n];
   else
      return NIL;
}
//Xac dinh nut goc trong cay
Node Root(Tree T)
{
   if (!EmptyTree(T))
      return 0;
   else
      return NIL;
}
//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]);
   }
}
//Do sau cua nut p
int DepthNode(Node p, Tree T) {
   if((p>=0|| p<T.MaxNode) && !EmptyTree(T)) {
      unsigned 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, temp;
   for(unsigned int i=0; i < T.MaxNode; i++)
   {
      temp = DepthNode(i,T);
      if(Max < temp)
         Max = temp;
   }
   return Max;
}
//Duyet cac nut theo muc cua nut tang dan
void LevelOrder(Tree T) {
   for(int i = 0; i<=HeightTree(T); i++)
      for(unsigned int j = 0; j<T.MaxNode; j++)
         if(DepthNode(j,T)==i)
            printf("%c\t",T.Data[j]);
}
//Chuong trinh chinh
void main(){
   clrscr();
   Tree T;   
   printf("Nhap du lieu cho cay tong quat\n");
   ReadTree(&T);
   printf("\nBieu thuc duyet theo muc la:\n");
   LevelOrder(T);
   getch();
}