TỔ TIÊN CHUNG GẦN NHẤT CỦA 2 NÚT TRÊN CÂY
Thuật toán:Tìm tổ tiên chung gần nhất của 2 nút p và q trong cây ta thực hiện các bước sao đây:
Bước 1: Nếu p = 0 hoặc q = 0 thì thuật toán kết thúc tổ tiên chung gần nhất là nurt 0. Thuật toán kết thúc.
Bước 2: Nếu T.Parent[p]!=NIL thì gán p = T.Parent[p] và chuyển sang bước 3. Ngược lại chuyển sang bước 4.
Bước 3: So sánh p với tất cả các tổ tiên của q. Nếu p = q thì tổ tiên chung là q hoặc q và thuật toán kết thúc. Ngược lại chuyển về bước 2.
Bước 4: Trả về giá trị NIL cho hàm tìm kiếm và thuật toán kết thúc.
Xét cấu trúc dữ liệu của cây tổng quát cài đặt bằng mảng.
Code:
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;Thuật toán tìm tổ tiên chung gần nhất của hai nút p và q.
Code:
//Tim to tien chung gan nhat
Node NearRoot(Node p, Node q, Tree T) {
if(p>=0 && p<T.MaxNode && q>=0 && q<T.MaxNode && !EmptyTree(T))
{
if( p==Root(T)||q==Root(T))
return 0;
else
{
while(p!=NIL)
{
Node k = q;
while(k!=NIL)
{
if( p == k)
return k;
k = T.Parent[k];
}
p = T.Parent[p];
}
}
}
else
return NIL;
}Chương trình minh họa.
Code:
/* Chuong trinh cai dat cay tong quat bang mang - To tien chung cua hai nut p va q*/
#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 NearRoot(Node p, Node q, Tree T) {
if(p>=0 && p<T.MaxNode && q>=0 && q<T.MaxNode && !EmptyTree(T))
{
if( p==Root(T)||q==Root(T))
return 0;
else
{
while(p!=NIL)
{
Node k = q;
while(k!=NIL)
{
if( p == k)
return k;
k = T.Parent[k];
}
p = T.Parent[p];
}
}
}
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]);
}
}
//Chuong trinh chinh
void main(){
clrscr();
Tree T;
Node p,q;
char ch;
printf("Nhap du lieu cho cay tong quat\n");
ReadTree(&T);
do{
printf("\nNhap vao 2 nut can tim to tien chung gan nhat: ");
scanf("%d%d",&p,&q);
Node temp = NearRoot(p,q,T);
if(temp==NIL)
printf("Khong co to tien chung");
else
{
printf("\nTo tien chung gan nhat la nut %d co nhan %c.",temp,T.Data[temp]);
}
printf("\nNhan ESC thoat khoi chuong trinh");
ch = getch();
clrscr();
}while(ch!=27);
}
-------------------
Cuộc sống luôn phức tạp. Đời người có nhiều thử thách....
Cuộc sống luôn phức tạp. Đời người có nhiều thử thách....
Được sửa bởi Admin ngày Fri Feb 25, 2011 2:34 pm; sửa lần 9.