Cấu trúc dữ liệu: Cây tổng quát với kiểu dữ liệu dạng chuỗi ký tự

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
#define MaxLength 10
#define NIL -1

typedef string 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++){
        cout<<"Node "<<i<<": ";
        cout<<"P("<<i<<",T) = "<<Parent(i,T)<<" - ";
        cout<<"L("<<i<<",T) = "<<LabelNode(i,T)<<endl;


    }
}
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)
        cout<<"Node "<<i<<" khong co con!!";
    else
    {
        cout<<"Danh sach con cua nut "<<i<<endl;
        cout<<lmc<<"  ";
        Node rs = RightSibling(lmc,T);
        while(rs!=NIL){
            cout<<rs<<"  ";
            rs = RightSibling(rs,T);
        }
    }
}
void PreOrder(Node n,Tree T){
    cout<<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);
    cout<<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);
    }
    cout<<LabelNode(n,T)<<"  ";

}

bool IsPath(Node A, Node B, Tree T){
    Node pB = Parent(B,T);
    if (pB == A || A == B)
        return true;
    else if (pB == NIL)
        return false;
    else
        return 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);
}
bool IsLeaf(Node n, Tree T){
    return LeftMostChild(n,T)==NIL;
}
bool IsAncestor(Node A, Node B, Tree T){
   return IsPath(A,B,T);
}
bool 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)
        return CommonAncestor(Parent(A,T),B,T);
    else if (da<db)
        return  CommonAncestor(A,Parent(B,T),T);
    else
        return  CommonAncestor(Parent(A,T),Parent(B,T),T);
}
int main(){
    Tree T;
    MakeNullTree(T);
    string data[10]={"can tho","ninh kieu","ca mau","lam dong","kien giang","hau giang","an giang","soc trang","bac lieu","tra vinh"};
    for(int i=0;i<10;i++)
        T.Data[i]=data[i];
    T.Parent={-1,0,0,1,1,4,4,4,2,2};
    T.MaxNode=10;
    PrintTree(T);
    if (EmptyTree(T))
        cout<<"Cay rong!";
    cout<<"LeftMostChild(8,T) = "<<LeftMostChild(8,T)<<endl;
    cout<<"RightSibling(5,T) = "<<RightSibling(5,T)<<endl;
    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);
    cout<<"\nisPath(2,5,T) = "<<IsPath(2,5,T);
    cout<<"\nisPath(1,1,T) = "<<IsPath(1,1,T);
    cout<<"\nisAncestor(1,7,T) = "<<IsAncestor(1,7,T);
    cout<<"\nisAncestor(2,4,T) = "<<IsAncestor(2,4,T);
    cout<<"\nisAncestor(4,2,T) = "<<IsAncestor(4,2,T);
    cout<<"\nisAncestor(0,0,T) = "<<IsAncestor(0,0,T);
    cout<<"\nisDescendant(7,1,T) = "<<IsDescendant(7,1,T);
    cout<<"\nisDescendant(4,2,T) = "<<IsDescendant(4,2,T);
    cout<<"\nisDescendant(5,5,T) = "<<IsDescendant(5,5,T);
    cout<<"\nPath(1,7,T) = "<<Path(1,7,T);
    cout<<"\nHeight(0,T) = "<<Height(0,T);
    cout<<"\nDepth(0,T) = "<<Depth(0,T);
    cout<<"\nDepth(4,T) = "<<Depth(4,T);

    cout<<"\nCommonAncestor(2,8,T) = "<<CommonAncestor(2,8,T);
    cout<<"\nCommonAncestor(8,2,T) = "<<CommonAncestor(8,2,T);
    cout<<"\nCommonAncestor(9,2,T) = "<<CommonAncestor(9,2,T);
    cout<<"\nCommonAncestor(5,8,T) = "<<CommonAncestor(5,8,T);
    cout<<"\nCommonAncestor(8,5,T) = "<<CommonAncestor(8,5,T);
    cout<<"\nCommonAncestor(3,7,T) = "<<CommonAncestor(3,7,T);

    return 0;
}