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 - Cài đặt bằng mảng

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 - Cài đặt bằng mảng

Bài gửi  admin on Tue Apr 06, 2010 12:52 am

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

cauquan1001
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 25/11/2010

Re: Cây tổng quát - Cài đặt bằng mảng

Bài gửi  cauquan1001 on Thu Nov 25, 2010 11:50 pm

anh ơi anh có thể chuyển bài trên sang ngôn ngữ Pascal đc ko ạ ? Smile

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 - Cài đặt bằng mảng

Bài gửi  admin on Fri Nov 26, 2010 2:05 pm

cauquan1001 đã viết:anh ơi anh có thể chuyển bài trên sang ngôn ngữ Pascal đc ko ạ ? Smile

Chào em,

Việc cài đặt theo một ngôn ngữ nào đó chỉ là minh họa trên ngôn ngữ lập trình thôi.

Nếu ta nắm vững thuật toán thì việc chọn ngôn ngữ không còn quan trọng nữa.

Em thử tìm hiểu và chuyển đổi ngôn ngữ thử xem, nếu trong quá trình chuyển đổi còn gặp phải lỗi trong Pascal hay ý tưởng thuật toán mình sẽ hướng dẫn bạn làm cho tốt hơn.

along115
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 11/04/2012

Re: Cây tổng quát - Cài đặt bằng mảng

Bài gửi  along115 on Wed Apr 11, 2012 9:30 pm

thầy ơi! ngày mai (thứ 5) em phải báo cáo về cây sử dụng mảng rồi! thầy cho 6 câu:
1/nhập cây
2/in cây
3/ đếm số nút lá
4/tính bậc cây
5/tính độ sâu của 1 nút
6/tính chiều cao của 1 nút
câu 1 và 2 thì cũng tạm ổn rồi nhưng các câu còn lại thầy có thể giúp dùm em được không?

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 - Cài đặt bằng mảng

Bài gửi  admin on Thu Apr 12, 2012 8:28 am

along115 đã viết:thầy ơi! ngày mai (thứ 5) em phải báo cáo về cây sử dụng mảng rồi! thầy cho 6 câu:
1/nhập cây
2/in cây
3/ đếm số nút lá
4/tính bậc cây
5/tính độ sâu của 1 nút
6/tính chiều cao của 1 nút
câu 1 và 2 thì cũng tạm ổn rồi nhưng các câu còn lại thầy có thể giúp dùm em được không?

Các bài toán trên đều có code mẫu. Em đọc trên diễn đàn nhé!


Gia sư Alpha
------------------------------------------------------------------------------------
Điện thoai: 07106 255 599 - 0932 836 026 - 0987 700 288
Website: http://giasualpha.com
Email: giasualpha@gmail.com
------------------------------------------------------------------------------------

Sponsored content

Re: Cây tổng quát - Cài đặt bằng mảng

Bài gửi  Sponsored content Today at 11:36 pm


    Hôm nay: Mon Dec 05, 2016 11:36 pm