Giải thuật và lập trình - C: Solution CÀI ĐẶT CÂY (TREE) bằng mảng


Đăng ký nhận thông báo về những video mới nhất

Link bài học:

https://v1study.com/giai-thuat-va-lap-trinh-c-iii-cai-dat-cay.html

Solution tham khảo:

#include<stdio.h>
#include<stdlib.h>

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

///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];

}

///Hàm xác định nút gốc trong cây
Node Root(Tree T){

    if (!EmptyTree(T))

        return 0;

     else

        return NIL;

}

///Hàm 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;

}

///Hàm 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("%d ",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("%d ",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("%d ",Label_Node(n,T));

}

///Nhập liệu cho cây
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 main() thực thi chương trình
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;

}

Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Copied !!!