数据结构——树的存储结构

双亲表示法

采用一组连续的存储空间来存储每个结点，同时在每个结点中增设一个伪指针，指示双亲结点在数组中的位置，根结点的下表为$0$，其伪指针域为$-1$。

​

#define MAX_TREE_SIZE 100 typedef struct{ // 每个结点 ElemType data; // 结点数据 int parent; // 结点双亲 }PTNode; typedef struct{ // 树 PNOde nodes[MAX_TREE_SIZE]; // 结点结构体数组 int n; // 结点数量 }PTree;

孩子表示法

将每个结点的孩子结点都用单链表连接起来形成一个线性结构，$n$个结点具有$n$个孩子链表。

#define MAX_TREE_SIZE 100 typedef struct{ // 孩子结点结构体 int child; // 孩子结点下标 struct CNode *next; // 下一个孩子结点的指针 }CNode; typedef struct{ // 每一个结点存放的数据元素 ElemType data; // 结点数据 struct CNode *child;// 对应的第一个孩子结点的指针——单链表头指针 }PNode; typedef struct{ // 树结构 PNode nodes[MAX_TREE_SIZE]; // 结点数量 int n; // 结点数组 }CTree;

孩子兄弟表示法

以二叉链表作为树的存储结构，又称二叉树表示法（左孩子右兄弟）。

typedef struct CsNode{ ElemType data; struct CSNode *friendchild, *nextsibling; }CSNode,CSTree;

根结点右指针为空——没有兄弟结点

区别与联系

方法优点缺点双亲表示法寻找结点双亲结点效率高寻找结点的孩子结点效率低孩子表示法寻找结点的孩子结点效率高寻找结点的双亲结点效率低孩子兄弟表示法寻找结点的孩子结点效率高方便实现树转换为二叉树寻找结点的双亲结点效率低