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

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;

}