Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Cây tổng quát - Tìm tổ tiên chung gần nhất của 2 nút

Share

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Cây tổng quát - Tìm tổ tiên chung gần nhất của 2 nút

Bài gửi  admin on Tue Apr 06, 2010 2:15 pm

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....


Được sửa bởi Admin ngày Fri Feb 25, 2011 2:34 pm; sửa lần 9.

weniken
Nhập môn
Nhập môn

Tổng số bài gửi : 4
Points : 15
Join date : 26/02/2010
Age : 26
Đến từ : Bến Tre city

HEHEHE

Bài gửi  weniken on Tue Apr 06, 2010 6:40 pm

THANK
WENI


Được sửa bởi weniken ngày Tue Apr 06, 2010 6:41 pm; sửa lần 1.

ghhg
Nhập môn
Nhập môn

Tổng số bài gửi : 5
Points : 10
Join date : 29/07/2010

Tìm tổ tiên của một nút

Bài gửi  ghhg on Thu Jul 29, 2010 4:28 pm

Xin hãy chỉ giúp hướng giải quyết của bài này, có biểu diễn cây như sau:
Code:

Type
   Node = ^Cell;
   Cell = record;
      Parent: Node ;   /*trỏ vào nút cha của nút*/
      Leftmost_Child : Node /*trỏ vào nút con cực trái của nút*/
      Right_Sibling : Node; /*trỏ vào anh em kề phải của nút */
   End;
   Tree=Node; /*một cây được xac định bởi nút gốc*/
Câu hỏi: cho 2 nút a và d, xét xem nút a có là tổ tiên của nút d không?

kieudiem
Nhập môn
Nhập môn

Tổng số bài gửi : 17
Points : 48
Join date : 14/11/2009

cho 2 nút a và d, xét xem nút a có là tổ tiên của nút d không?

Bài gửi  kieudiem on Thu Jul 29, 2010 5:18 pm

Ý tuởng:
Cho nút d về nút gốc, nếu a nằm trên đường dẫn này thì a là tổ tiên của d và nguợclai.
Mình viết code bằng C, bạn tham khảo nhé!

Code:

int Ancestor(Node a,Node d,Tree T)
{
    Node i=d;
    while (i!=NULL)
    {
        if(i==a)
              return 1;
        else
              i=i->Parent;
    }
    return 0;
}
Vui lên cho đời bớt khổ...

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Re: Cây tổng quát - Tìm tổ tiên chung gần nhất của 2 nút

Bài gửi  admin on Fri Feb 25, 2011 2:37 pm

Code:
int Ancestor(Node a,Node d,Tree T)
{
    Node i=d;
    while (i!=NIL)
    {
        if(i==a)
              return 1;
        else
              i=T.Parent[i];
    }
    return NIL;
}

Sponsored content

Re: Cây tổng quát - Tìm tổ tiên chung gần nhất của 2 nút

Bài gửi  Sponsored content Today at 7:44 pm


    Hôm nay: Sat Dec 10, 2016 7:44 pm