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