树的存储结构 #

1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法

双亲表示法 #

• 因为树结构除了根节点外，均有唯一的父(双亲)节点，因此可用一个顺序表(数组、列表)来存储每个节点对应父节点信息。根节点没有双亲，所以其在数组中存储的值为-1。其余的节点，只需要存储其父节点对应的数组下标即可
• 优缺点:很容易找到某个节点的双亲节点，但是寻找某个节点的孩子节点的时候需要遍历整个数组

孩子表示法 #

• 孩子表示法存储普通树采用的是 “顺序表+链表” 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点。需要注意，与双亲表示法不同的是，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置
• 优缺点:比较容易遍历双亲节点的子节点，但是只能从根(父)节点遍历到子节点，不能从某个子节点返回到它的父节点

孩子兄弟表示法 #

• 孩子兄弟表示法,指的是将整棵树用二叉链表存储起来,具体实现方案是: 从树的根节点开始,依次存储各个结点的孩子结点和兄弟结点

小结 #

• 理解树的存储结构的含义
• 掌握树的双亲表示法以及孩子兄弟表示法

习题 #

1. 使用列表实现树存储的双亲表示法
2. 谈一谈树存储的孩子兄弟表示法的优缺点，观察经过孩子兄弟表示法之后的树有什么特点？