[回忆梳理] 1.树的存储结构

对数据结构中树这一部分进行总结提炼，一些基础概念暂时略过，或者完成此篇文章后另加一个附录，在附录中进行标记

1.双亲表示法

1.1基本用法

• 定义一个结点，结点分为两部分，一部分是自身的数据域，另外一部分标识双亲位置的位置域
• 以一组连续的空间来存储这样的树的结点
• 根节点的位置域为-1
• 通过结点寻找双钱的时间复杂度为常数阶O(1)

• 缺点：寻找孩子结点需要遍历整个树

  
  结点图

双亲表示法伪代码 双亲表示法举例

1.2 双亲表示法改进1
由于寻找孩子结点的时候需要遍历，为了改进此问题，我们将原有结点中增加一部分，指示其最左边的孩子，称为长子域，这样对于只有1个或者0个孩子的就可以很好表示了，2个孩子的时候可以通过长子去推断次子，再多及不满足要求了

增加长子域节点图

1.3 双亲表示法改进2
如果我们关注兄弟之间的关系，可以在原有的基本用法上增加右兄弟结点，用以表示兄弟之间的关系，如果没有右兄弟则标为-1

1.4 小结
双亲表达法以双亲的位置为主要元素，其他部分可以根据具体的场景去灵活添加适应更好的需求

2. 孩子表示法

• 把每个结点的孩子结点以单链表的方式存储
• n个结点就有n个孩子链表，n个头指针
• 叶子结点的则对应空表
• n个头指针组成一个线性表，用顺序存储，存到一维数组
• 用两种即结点结构分别存储孩子链表的孩子结点和表头数组的表头结点
  • 孩子结点的next指示该结点对应的根节点的另外的孩子结点的指针
  • 表头结点的firstchild指示其孩子结点的头指针

孩子结点
表头结点

孩子表示法伪代码2

• 孩子和双亲表达法的简单改进结合

  
  

3. 孩子兄弟表示法

对于一棵树它的做第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，由此设计出一种结点，有两个指针，分别指向第一个孩子和它的右结点

• 伪代码如下

• 结构图

  
  
  

• 缺点：
  对于查找双亲比较麻烦，可以改进结点的结构，增加双亲的指针，不赘述

• 下一篇 [回忆梳理] 二叉树的性质