Cấu trúc dữ liệu: Cây tổng quát bằng mảng

#include <stdio.h>
#define MaxLength 10
#define NIL -1
typedef char DataType;
typedef int Node;
typedef struct Tree{
    DataType Data[MaxLength];
    Node Parent[MaxLength];
    int MaxNode;
};

void MakeNullTree(Tree &T){
    T.MaxNode = 0;
}
int EmptyTree(Tree T){
    return T.MaxNode == 0;
}

DataType LabelNode(Node i,Tree T){
    return T.Data[i];
}

Node Parent(Node i,Tree T){
    return T.Parent[i];
}
void PrintTree(Tree T){
    for(int i=0;i<T.MaxNode;i++){
        printf("Node %d: ",i);
        printf("P(%d,T) = %d - ",i,Parent(i,T));
        printf("L(%d,T) = %c \n",i,LabelNode(i,T));
    }
}
Node LeftMostChild(Node i, Tree T){
    for(Node j=i+1;j<T.MaxNode;j++){
        if (Parent(j,T)==i)
            return j;
    }
    return NIL;
}

Node RightSibling(Node i, Tree T){
    Node p = Parent(i,T);
    for (Node j=i+1;j<T.MaxNode;j++){
        if (p==Parent(j,T))
            return j;
    }
    return NIL;
}
void PrintChilds(Node i, Tree T){
    Node lmc = LeftMostChild(i,T);
    if (lmc == NIL)
        printf("Node %d khong co con!!",i);
    else
    {
        printf("Danh sach con cua nut %d: \n",i);
        printf("%d\t",lmc);
        Node rs = RightSibling(lmc,T);
        while(rs!=NIL){
            printf("%d\t",rs);
            rs = RightSibling(rs,T);
        }
    }
}
void PreOrder(Node n,Tree T){
    printf("%c ",LabelNode(n,T));
    Node i = LeftMostChild(n,T);
    while(i!=NIL){
        PreOrder(i,T);
        i=RightSibling(i,T);
    }

}
void InOrder(Node n,Tree T){
    Node i = LeftMostChild(n,T);
    if (i!=NIL)
        InOrder(i,T);
    printf("%c ",LabelNode(n,T));
    i = RightSibling(i,T);
    while(i!=NIL){
        InOrder(i,T);
        i = RightSibling(i,T);
    }
}

void PostOrder(Node n,Tree T){
    Node i = LeftMostChild(n,T);
    while(i!=NIL){
        PostOrder(i,T);
        i = RightSibling(i,T);
    }
    printf("%c ",LabelNode(n,T));

}

int IsPath(Node A, Node B, Tree T){
    Node pB = Parent(B,T);
    if (pB == A || A == B)
        return 1;
    else if (pB == NIL)
        return 0;
    else
        IsPath(A,pB,T);
}
int Path(Node A, Node B, Tree T){
    if (!IsPath(A,B,T) || A == B)
        return 0;
    else
        return 1 + Path(A,Parent(B,T),T);
}
int IsLeaf(Node n, Tree T){
    return LeftMostChild(n,T)==NIL;
}
int IsAncestor(Node A, Node B, Tree T){
   return IsPath(A,B,T);
}
int IsDescendant(Node A,Node B, Tree T){
    return IsAncestor(B,A,T);
}
int Height(Node n, Tree T){
    int max = 0;
    for(Node i=n+1;i<T.MaxNode;i++){
        if (IsLeaf(i,T) && IsDescendant(i,n,T))
        {
            int p = Path(n,i,T);
            if (p>max)
                max = p;
        }
    }
    return max;
}
int Depth(Node n, Tree T){
    return Path(0,n,T);
}
Node CommonAncestor(Node A, Node B, Tree T){
    if (A == Parent(B,T))
        return A;
    else if (B == Parent(A,T))
        return B;
    else if (Parent(A,T)==Parent(B,T))
        return Parent(A,T);
    int da = Depth(A,T);
    int db = Depth(B,T);
    if (da>db)
        CommonAncestor(Parent(A,T),B,T);
    else if (da<db)
        CommonAncestor(A,Parent(B,T),T);
    else
        CommonAncestor(Parent(A,T),Parent(B,T),T);
}
int main(){
    Tree T;
    MakeNullTree(T);
    T.Data={'A','B','C','D','E','F','G','H','I','J'};
    T.Parent={-1,0,0,1,1,4,4,4,2,2};
    T.MaxNode=10;
    if (EmptyTree(T))
        printf("Cay rong!!!");
    printf("LeftMostChild(8,T)=%d\n",LeftMostChild(8,T));
    printf("RightSibling(5,T)=%d\n",RightSibling(5,T));
    PrintChilds(3,T);
    printf("\nDuyet tien tu:\n");
    PreOrder(0,T);
    printf("\nDuyet trung tu:\n");
    InOrder(0,T);
    printf("\nDuyet hau tu:\n");
    PostOrder(0,T);
    printf("\nisPath(2,5,T) = %d",IsPath(2,5,T));
    printf("\nisPath(1,1,T) = %d",IsPath(1,1,T));
    printf("\nisAncestor(1,7,T) = %d",IsAncestor(1,7,T));
    printf("\nisAncestor(2,4,T) = %d",IsAncestor(2,4,T));
    printf("\nisAncestor(4,2,T) = %d",IsAncestor(4,2,T));
    printf("\nisAncestor(0,0,T) = %d",IsAncestor(0,0,T));
    printf("\nisDescendant(7,1,T) = %d",IsDescendant(7,1,T));
    printf("\nisDescendant(4,2,T) = %d",IsDescendant(4,2,T));
    printf("\nisDescendant(5,5,T) = %d",IsDescendant(5,5,T));
    printf("\nPath(1,7,T) = %d",Path(1,7,T));
    printf("\nHeight(0,T) = %d",Height(0,T));
    printf("\nDepth(0,T) = %d",Depth(0,T));
    printf("\nDepth(4,T) = %d",Depth(4,T));
    printf("\nCommonAncestor(2,8,T) = %d",CommonAncestor(2,8,T));
    printf("\nCommonAncestor(8,2,T) = %d",CommonAncestor(8,2,T));
    printf("\nCommonAncestor(9,2,T) = %d",CommonAncestor(9,2,T));
    printf("\nCommonAncestor(5,8,T) = %d",CommonAncestor(5,8,T));
    printf("\nCommonAncestor(8,5,T) = %d",CommonAncestor(8,5,T));
    printf("\nCommonAncestor(3,7,T) = %d",CommonAncestor(3,7,T));
    return 0;
}