第六章：树结构

概念

1. 节点的子树根称为该节点的孩子，某节点的孩子就是该节点往下直接跟该节点相连的节点。
2. 子树：每个节点+该节点往下所有元素→就是→该节点双亲节点的子树。

树的存储结构

回顾一下结构体与数组：
以整型数组为例，数组作为整体就是一个顺序结构，数组的每个节点就是一个int，由于int仅仅是一个数，不能存储多种信息，因此构造一个结构体节点，替代数组的int，这样每个节点就可以存储多种信息，而数组仍然作为一个数据框架，盛放每个结构体节点。
进一步，我们希望存储一些关于这个数组本身的整体信息，比如数组的长度、末尾元素的位置等等，当然我们可以在函数中定义一些变量来描述，但是这样就与数组本身分散开了，为了整洁起见，可以把数组及数组本身相关的信息封装在一个结构体中，这样在定义这样的一个结构体的同时就相当于同时定义了一个数组，以及与该数组相关的一些变量。

1. 双亲表示法

为每个节点定义结构体变量，每个节点存储①该节点数据②该节点的双亲的位置（下标）；再用一个结构体封装一个树结构，包括一个数组，用于存储上面定义的节点，另外包含树的节点数、根的位置等信息。

// 树的存储结构 双亲表示法
#define MAXSIZE 128

typedef struct PTNode
{
    int data;  // 节点数据
    int parent;  // 双亲位置
}PTNode;

typedef struct  // 树结构
{
    PTNode nodes[MAXSIZE];  // 节点数组
    int r, n;  // 根的位置和节点数
}PTree;

2. 孩子表示法

修改双亲表示法的节点的结构，data不变还是用来存储每个元素的数据，将指示双亲位置的整型变量替换为指向孩子节点结构体的指针。
孩子节点结构体：因为每个节点有个数不等的孩子节点，利用链表存储这些孩子节点的位置。因此构造孩子节点结构体，数据项是该孩子节点的在主数组中的位置（下标），指针项指向下一个孩子节点。

// 孩子表示法
#define MAXSIZE 128

typedef struct CTNode
{
    int child;
    struct CTNode *next;
}*ChildPtr;

typedef struct
{
    int data;
    ChildPtr firstchild;
}Node;

typedef struct 
{
    CTNode nodes[MAXSIZE];
    int r, n;
}CTree;

双亲表示法和孩子表示法对比

这种结构对于我们要查找某个节点的某个孩子，或者某个节点的兄弟，只需要查找这个结点的单链表即可。
遍历整棵树（比如打印所有元素的数值）也是很方便的，对头结点的数组循环即可。

但是，这也存在问题，如何直接知道某个节点的双亲，此时需要遍历整个数组（整个树）。
改进：修改节点结构体，加入一个成员parent，用于标识双亲节点的位置（下标）

typedef struct
{
    int data;
    int parent;
    ChildPtr firstchild;
}Node;