Giải thuật và lập trình - C: III. Cài đặt cây

Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực

1. Cài đặt cây 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 hạn đánh số như cây trong hình III.8.

Ví dụ:

Cây tổng quát

Hình III.8 Hình ảnh một cây tổng quát

Cây trong hình III.8 được biểu diễn trong mảng như sau:

mảng

Khai báo cấu trúc dữ liệu

#define MAXLENGTH 100 /* Chỉ số tối đa của mảng */

#define NIL -1

typedef int DataType;

typedef int Node;

typedef struct{

    /* Lưu trữ nhãn (dữ liệu) của nút trong cây */

    DataType Data[MAXLENGTH];

    /* Lưu trữ cha của các nút trong cây theo nguyên tắc: Cha của nút i sẽ lưu ở vị trí i trong mảng */

    Node Parent[MAXLENGTH];

    /* Số nút thực sự trong cây */

    int MaxNode;

} Tree;

Tree T;

Sự lưu trữ như vậy còn gọi là sự lưu trữ kế tiếp và cách lưu trữ cây như trên, ta có thể viết được các phép toán cơ bản trên cây như sau:

Khởi tạo cây rỗng:

void MakeNull_Tree (Tree *T){

    (*T).MaxNode=0;

}

Kiểm tra cây rỗng

int EmptyTree(Tree T){

    return T.MaxNode == 0;

}

Xác định nút cha của nút trên cây

Node Parent(Node n,Tree T){

    if (EmptyTree(T) || (n>T.MaxNode-1))

        return NIL;

    else return T.Parent[n];

}

Xác định nhãn của nút trên cây

DataType Label_Node(Node n,Tree T){

    if (!EmptyTree(T) && (n<=T.MaxNode-1))

        return T.Data[n];

}

Xác định nút gốc trong cây

Node Root(Tree T){

    if (!EmptyTree(T))

        return 0;

     else

        return NIL;

}

Xác định con trái nhất của một nút

Node LeftMostChild(Node n,Tree T){

    Node i;

    int found;

    if (n<0) return NIL;

    i=n+1;/* Vị trí nút đầu tiên hy vọng là con của nút n */

    found=0;

    while ((i<=T.MaxNode-1) && !found)

        if (T.Parent[i]==n) found=1; /* Đã tìm thấy con trái nhất của nút n */

        else i=i+1;

    if (found) return i;

    else return NIL;

}

Xác định anh em ruột phải của một nút:

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;

}

Thủ tục duyệt tiền tự

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

    }

}

Thủ tục duyệt trung tự

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

    }

}

Thủ tục duyệt hậu tự

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

}

Ví dụ: Viết chương trình nhập dữ liệu vào cho cây từ bàn phím như tổng số nút trên cây; ứng với từng nút thì phải nhập nhãn của nút, cha của một nút. Hiển thị danh sách duyệt cây theo các phương pháp duyệt tiền tự, trung tự, hậu tự của cây vừa nhập.

Hướng giải quyết: Với những yêu cầu đặt ra như trên, chúng ta cần phải thiết kế một số chương trình con sau:

  • Tạo cây rỗng MAKENULL(T)
  • Nhập dữ liệu cho cây từ bàn phím INPUTTREE(T). Trong đó có nhiều cách nhập dữ liệu vào cho một cây nhưng ở đây ta có thể thiết kế thủ tục này đơn giản như sau:

void InputTree(Tree *T){

    int i;

    MakeNull_Tree(&*T);

    //Nhập số nút của cây cho đến khi số nút nhập vào là hợp lệ

    do {

        printf("Moi nhap so luong nut cua cay: ");

        scanf("%d",&(*T).MaxNode);

    } while (((*T).MaxNode<1) || ((*T).MaxNode>MAXLENGTH));

    printf("Nhap nhan cua nut goc: ");

    fflush(stdin);

    scanf("%d",&(*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("%d",&(*T).Data[i]);

    }

}

  • Hàm xác định con trái nhất của một nút LEFTMOST_CHILD(n,T). Hàm này được dựng trong phép duyệt cây.
  • Hàm xác đinh anh em ruột phải của một nút RIGHT_SIBLING (n,T). Hàm này được dựng trong phép duyệt cây.
  • Các chương trình con hiển thị danh sách duyệt cây theo các phép duyệt.

Với những chương trình con được thiết kế như trên, ta có thể tạo một chương trình chính để thực hiện theo yêu cầu đề bài như sau:

main(){

    printf("Nhap du lieu cho cay tong quat\n");

    InputTree(&T);

    printf("Danh 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);

    return 0;

}

2. Biểu diễn cây bằng danh sách các con

Một cách biểu diễn khác cũng thường được dùng là biểu diễn cây dưới dạng mỗi nút có một danh sách các nút con. Danh sách có thể cài đặt bằng bất kỳ cách nào chúng ta đã biết, tuy nhiên vì số nút con của một nút là không biết trước nên dùng danh sách liên kết sẽ thích hợp hơn.

Ví dụ: Cây ở hình III.8 có thể lưu trữ dưới dạng như trong hình III.9

Lưu trữ cây bằng danh sách các con

Hình III.9 Lưu trữ cây bằng danh sách các con

Có thể nhận xét rằng các hàm đòi hỏi thông tin về các con làm việc rất thuận lợi, nhưng hàm PARENT lại không làm việc tốt. Chẳng hạn tìm nút cha của nút 8 đòi hỏi ta phải duyệt tất cả các danh sách chứa các nút con.

(Có thể tham khảo cách cài đặt chi tiết trong giáo trình "Thực tập Cấu trúc dữ liệu")

3. Biểu diễn theo con trái nhất và anh em ruột phải:

Các cấu trúc đã dùng để mô tả cây ở trên có một số nhược điểm, nó không trợ giúp phép tạo một cây lớn từ các cây nhỏ hơn, nghĩa là ta khó có thể cài đặt phép toán CREATEi bởi vì mỗi cây con đều có một mảng chứa các header riêng. Chẳng hạn CREATE2(v,T1,T2) chúng ta phải chép hai cây T1, T2 vào mảng thứ ba rồi thêm một nút n có nhãn v và hai nút con là gốc của T1 và T2. Vì vậy nếu chúng ta muốn thiết lập một cấu trúc dữ liệu trợ giúp tốt cho phép toán này thì tất cả các nút của các cây con phải ở trong cùng một vùng (một mảng). Ta thay thế mảng các header bằng mảng CELLSPACE chứa các struct có ba trường LABELS, LEFTMOST_CHILD, RIGHT_SIBLING. Trong đó LABELS giữ nhãn của nút, LEFTMOST_CHILD là một con nháy chỉ đến con trái nhất của nút, còn RIGHT_SIBLING là con nháy chỉ đến nút anh ruột phải. Hơn nữa mảng này giữ tất cả các nút của tất cả các cây.

Với cấu trúc này các phép toán đều thực hiện dễ dàng trừ PARENT, PARENT đòi hỏi phải duyệt toàn bộ mảng. Nếu chúng ta muốn cải tiến cấu trúc để trợ giúp phép toán này ta có thể thêm trường thứ 4 PARENT là một con nháy chỉ tới nút cha (xem hình III.11).

Để cài đặt cây theo cách này chúng ta cũng cần quản lí các ô trống theo cách tương tự như cài đặt danh sách bằng con nháy, tức là liên kết các ô trống vào một danh sách có chỉ điểm đầu là Availlable. Ở đây mỗi ô chứa 3 con nháy nên ta chỉ cần chọn 1 để trỏ đến ô kế tiếp trong danh sách, chẳng hạn ta chọn con nháy Right_sibling. Ví dụ cây trong hình III.10 có thể được cài đặt như trong hình III.11. Các ô được tô đậm là các ô trống, tức là các ô nằm trong danh sách Available.

Hình ảnh cây tổng quát

Hình III.10 Hình ảnh cây tổng quát

Hình 11

Hình III.11

 

(có thể tham khảo cách cài đặt chi tiết trong giáo trình "Thực tập Cấu trúc dữ liệu")

4. Cài đặt cây bằng con trỏ

Hoàn toàn tương tự như cài đặt ở trên nhưng các con nháy Leftmost_child, Right_sibling và Parent được thay bằng các con trỏ.

Hãy so sách các ưu khuyết điểm của các cách cài đặt cây?

» Tiếp: IV. Cây nhị phân (BINARY TREES)
« Trước: II. Kiểu dữ liệu trừu tượng cây
Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực
Copied !!!