C语言数据结构系列之树的概念结构和常见表示方法

树是一种非线性数据结构，它由若干个节点构成，节点之间通过边来连接，具有层次关系。

树的基本概念和术语

• 节点：树中的元素，它可以包含一个数据元素或多个数据元素，一个节点也可以称为一个分支节点。
• 根节点：树的最上层节点，它没有父节点。
• 叶子节点：没有子节点的节点称为叶子节点。
• 父节点和子节点：父节点是某个节点的上一级节点，子节点是某个节点的下一级节点。
• 兄弟节点：具有同一父节点的节点称为兄弟节点。
• 子树：一个节点和它的子节点构成的树称为子树。

树的表示方法

双亲表示法

双亲表示法是通过每个节点存储它的父节点来表示树的关系。

#define MAX_TREE_SIZE 100
typedef struct{
    ElemType data; // 数据元素
    int parent; // 父节点位置
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE]; // 双亲节点数组
    int r; // 树根位置
    int n; // 节点数目
}PTree;

使用双亲表示法时，需要遍历一次树找到每个节点的父节点并记录，这个过程会导致时间开销较大。

孩子表示法

孩子表示法是通过每个节点存储它的一个子节点指针，来表示树的关系。

#define MAX_TREE_SIZE 100
typedef struct CTNode{
    int child; // 子节点在数组中的位置
    struct CTNode *next; // 指向下一个子节点的指针
} *ChildPtr;

typedef struct{
    ElemType data; // 数据元素
    ChildPtr firstchild; // 子节点指针
}CTBox;

typedef struct{
    CTBox nodes[MAX_TREE_SIZE]; // 子节点数组
    int r; // 树根的位置
    int n; // 节点个数
}CTree;

使用孩子表示法时，需要为每个节点创造一个子节点指针，这可能会引起大量的空间浪费。另外，孩子表示法也需要对树进行遍历来找到每个节点的子节点。

孩子兄弟表示法

孩子兄弟表示法是通过每个节点存储它的第一个子节点和下一个兄弟节点，来表示树的关系。

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild; // 指向第一个子节点的指针
    struct CSNode *nextsibling; // 指向下一个兄弟节点的指针
}CSNode, *CSTree;

使用孩子兄弟表示法时，一个节点可以快速地访问其第一个子节点和下一个兄弟节点，但也需要遍历树以找到某个节点的后代或兄弟节点。

树的遍历

树的遍历就是按照某种规则依次访问树中所有节点的过程。

先序遍历

先序遍历就是先访问根节点，再按照先序遍历的方式遍历左子树和右子树。在先序遍历中，根节点总是在第一个被访问。

void PreOrderTraverse(CSTree T){
    if(T){ // 树不为空
        visit(T); // 访问根节点
        PreOrderTraverse(T -> firstchild); // 对左子树进行遍历
        PreOrderTraverse(T -> nextsibling); // 对右子树进行遍历
    }
}

中序遍历

中序遍历就是先按中序遍历的方式遍历左子树，然后访问根节点，最后按照中序遍历的方式遍历右子树。在中序遍历中，根节点总是在左右子树之间被访问。

void InOrderTraverse(CSTree T){
    if(T){ // 树不为空
        InOrderTraverse(T -> firstchild); // 对左子树进行遍历
        visit(T); // 访问根节点
        InOrderTraverse(T -> nextsibling); // 对右子树进行遍历
    }
}

后序遍历

后序遍历就是先按照后序遍历的方式遍历左子树和右子树，然后访问根节点。在后序遍历中，根节点总是在左右子树被访问之后才被访问。

void PostOrderTraverse(CSTree T){
    if(T){ // 树不为空
        PostOrderTraverse(T -> firstchild); // 对左子树进行遍历
        PostOrderTraverse(T -> nextsibling); // 对右子树进行遍历
        visit(T); // 访问根节点
    }
}

示例一

以下是使用孩子表示法创建一棵具有5个节点的树，并通过先序遍历、中序遍历和后序遍历遍历树的过程：

CTree create_tree(){
    CTree T;
    T.n = 5;
    T.r = 0;
    T.nodes[0].data = 1;
    T.nodes[1].data = 2;
    T.nodes[2].data = 3;
    T.nodes[3].data = 4;
    T.nodes[4].data = 5;
    T.nodes[0].firstchild = &T.nodes[1]; // 节点1的第一个子节点是节点2
    T.nodes[1].firstchild = &T.nodes[2]; // 节点2的第一个子节点是节点3
    T.nodes[2].firstchild = NULL; // 节点3没有子节点
    T.nodes[3].firstchild = &T.nodes[4]; // 节点4的第一个子节点是节点5
    T.nodes[4].firstchild = NULL; // 节点5没有子节点
    return T;
}

void visit(CTree T){
    printf("%d ", T.data);
}

void traverse(){
    CTree T = create_tree();
    printf("先序遍历：");
    PreOrderTraverse(T.nodes[0].firstchild);
    printf("\n中序遍历：");
    InOrderTraverse(T.nodes[0].firstchild);
    printf("\n后序遍历：");
    PostOrderTraverse(T.nodes[0].firstchild);
}

这个示例创建了一棵具有5个节点的树，并分别使用先序遍历、中序遍历和后序遍历遍历树中的所有节点。

示例二

以下是使用孩子兄弟表示法创建一棵具有6个节点的二叉树，并通过先序遍历、中序遍历和后序遍历遍历二叉树的过程：

CSTree create_binary_tree(){
    CSTree T;
    T = (CSTree)malloc(sizeof(CSNode));
    T -> data = 1;
    T -> firstchild = (CSTree)malloc(sizeof(CSNode));
    T -> firstchild -> data = 2;
    T -> firstchild -> firstchild = (CSTree)malloc(sizeof(CSNode));
    T -> firstchild -> firstchild -> data = 4;
    T -> firstchild -> firstchild -> firstchild = NULL;
    T -> firstchild -> firstchild -> nextsibling = (CSTree)malloc(sizeof(CSNode));
    T -> firstchild -> firstchild -> nextsibling -> data = 5;
    T -> firstchild -> firstchild -> nextsibling -> firstchild = NULL;
    T -> firstchild -> firstchild -> nextsibling -> nextsibling = NULL;
    T -> firstchild -> nextsibling = (CSTree)malloc(sizeof(CSNode));
    T -> firstchild -> nextsibling -> data = 3;
    T -> firstchild -> nextsibling -> firstchild = NULL;
    T -> firstchild -> nextsibling -> nextsibling = NULL;
    return T;
}

void visit(CSTree T){
    printf("%d ", T -> data);
}

void traverse(){
    CSTree T = create_binary_tree();
    printf("先序遍历：");
    PreOrderTraverse(T);
    printf("\n中序遍历：");
    InOrderTraverse(T);
    printf("\n后序遍历：");
    PostOrderTraverse(T);
}

这个示例创建了一棵具有6个节点的二叉树，并分别使用先序遍历、中序遍历和后序遍历遍历树中的所有节点。