树

sibling 兄弟

根节点：
度：结点拥有的子树数（叶结点、分支结点），树的度是各个结点度的最大值。
层次：
森林：m(m>0)棵互不相交的树

1.树的储存结构

1)双亲表示法

• 在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
• 根节点的位置域约定为 -1
• 想知道结点的孩子，需遍历整个结构。

树结构
双亲表示法

2)孩子表示法

• 多重链表表示法：每个结点有多个指针域，其中每个指针指向一棵子树的根结点。
• 方案一浪费空间，各结点·度相差小，空间就能充分利用；
• 方案二空间利用率提高，但造成运算时间损耗增加。

方案一
方案二

• ☆ 孩子表示法：把每个结点的孩子结点排列起来，以单链表作为储存结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序储存结构，存放进一个一维数组中。

image.png

https://blog.csdn.net/qq_30611601/article/details/80652731

3)