CÀI ĐẶT CÂY TỔNG QUÁT BẰNG MẢNG
Cho cây T có n nút, ta có thể gán tên cho các nút lần lượt là 0,1, 2, .., n-1. Sau đó ta dùng một mảng một chiều A để lưu trữ cây bằng cách cho A[i] = j với j là nút cha của nút i. Nếu i là nút gốc ta cho a[i] = -1 vì nút gốc không có cha.
Nếu cây T là cây có nhãn ta có thể dùng thêm một mảng một chiều thứ hai L chứa các nhãn của cây bằng cách cho L[i] = x với x là nhãn của nút i, hoặc khai báo mảng a là mảng của các struct có hai trường: trường Parent giữ chỉ số nút cha; trường Data giữ nhãn của nút và một trường MaxNode giữ số nút hiện tại đang có trên cây.
Với cách lưu trữ như thế, hàm PARENT(n,T) tốn chỉ một hằng thời gian trong khi các hàm đòi hỏi thông tin về các con không làm việc tốt vì phai tốn vòng lặp để dò tìm. Chẳng hạn cho một nút i tìm nút con trái nhất của nút i là không thể xác định được. Để cải thiện tình trạng này ta qui ước việc đặt tên cho các nút (đánh số thứ tự) như sau:
- Đánh số theo thứ tự tăng dần bắt đầu tại nút gốc.
- Nút cha được đánh số trước các nút con.
- Các nút con cùng một nút cha được đánh số lần lượt từ trái sang phải.
Chương trình minh họa cài đặt cây tổng quát bằng mảng.
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;
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];
}
//Xac dinh nut goc trong cay
Node Root(Tree T)
{
if (!EmptyTree(T))
return 0;
else
return NIL;
}
//Ham xac dinh con trai nhat cua mot nut
Node LeftMostChild(Node n,Tree T)
{
Node i;
int found;
if (n<0)
return NIL;
i=n+1;
found=0;
while ((i<=T.MaxNode-1) && !found)
if (T.Parent[i]==n)
found=1;
else i=i+1;
if (found)
return i;
else
return NIL;
}
//Ham xac dinh anh em ruot phai cua mot nut
Node RightSibling(Node n,Tree T)
{
Node i,parent;
int found;
if (n<0)
return NIL;
parent=T.Parent[n];
i=n+1;
found=0;
while ((i<=T.MaxNode-1) && !found)
if (T.Parent[i]==parent)
found=1;
else i=i+1;
if (found)
return i;
else
return NIL;
}
//Duyet tien tu
void PreOrder(Node n,Tree T)
{
Node i;
printf("%c ",Label_Node(n,T));
i=LeftMostChild(n,T);
while (i!=NIL) {
PreOrder(i,T);
i=RightSibling(i,T);
}
}
//Duyet trung tu
void InOrder(Node n,Tree T)
{
Node i;
i=LeftMostChild(n,T);
if (i!=NIL)
InOrder(i,T);
printf("%c ",Label_Node(n,T));
i=RightSibling(i,T);
while (i!=NIL){
InOrder(i,T);
i=RightSibling(i,T);
}
}
//Duyet hau tu
void PostOrder(Node n,Tree T)
{
Node i;
i=LeftMostChild(n,T);
while (i!=NIL){
PostOrder(i,T);
i=RightSibling(i,T);
}
printf("%c ",Label_Node(n,T));
}
//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);
printf("\nDanh sach duyet tien tu cua cay vua nhap la\n");
PreOrder(Root(T),T);
printf("\nDanh sach duyet trung tu cua cay vua nhap la\n");
InOrder(Root(T),T);
printf("\nDanh sach duyet hau tu cua cay vua nhap la\n");
PostOrder(Root(T),T);
getch();
}
