一般的树与二叉树的关系 | 树

一般树的表示

• 在进行树的表示的时候，我们通常用链表而不是数组表示，因为如果用数组来表示树的话，只能表示出节点的顺序，而很难表示节点间的关系。

用链表实现

• 如果用链表来实现的话，每个节点就是一个结构体，如下图：

• 在这颗树中，节点A有三个子结点，所以结构体A中会存在三个指针，节点B有两个子结点，所以结构体B中会存在两个指针，节点C有一个子结点，所以结构体C中会存在一个指针，这样看似用链表顺利地表示了树，但是这样的树的结构中，每个节点的子结点的数量不同，导致每个节点的结构都不同，给之后的程序实现带来一定的困难。
• 那么如果将所有节点都定义成一样的结构 （例如所有的节点都和A的结构一样） 呢？
  这个样子的话，虽然每个节点的结构统一了，但其实这样同样还存在一些问题：如果一个树有N个节点，那么这个树就总共有3N个指针域，但是我们的边只有N-1条。因此将会有将近1/3的指针域为空，这样会导致内存空间的大量浪费。
• 那么有没有一种更好的方法吗？下面就来介绍另一个生成树的方法：儿子——兄弟表示法。

儿子——兄弟表示法

• 在这个方法中，树上的每一个节点的结构是统一的，拥有两个指针域，一个指向自己的第一个子结点(First chiled)，另一个指向自己的 兄弟节点(Next Sibling) ，用儿子——兄弟表示法表示上面的树可以表示成下图的树：

• 儿子——兄弟表示法有以下几点优点：

  1. 每个节点的结构都是统一的，避免了内存空间的浪费。
  2. 一共有2N个指针域，有N-1个指针域是非空的，N+1个指针域是空的，减少了为空指针的数量。
• 这时如果我们将儿子-兄弟表示法生成的树顺时针旋转45度，如下图

• 这个时候我们可以看到另一颗树，我们遗忘掉儿子-兄弟表示法中各个节点的关系，那么就可以发现，这棵树中每个节点只有两个指针域，一个左边一个右边，每个节点最多只有两个子节点，具有这样特征的树，我们叫做二叉树 点题！！。

二叉树节点结构示意图

• 二叉树是我们主要研究的树形数据结构。

问题

• 树的集合称为森林。是否也可以使用“儿子-兄弟”表示法存储森林？如何实现？