|
其实如果说到森林，那就没有必要再扯到二叉上去了，但是二叉树由于其规整性，还是被我们充分的利用着。 对于普通的树结构，我们想要表达他们直接的成员关系是有很多种方法的。 从社会学角度上将我们有几种方法： 1）双亲法，对于每个元素我们保存它的父节点引用就可以保存整个树的结构。 可以很容易的得到节点的父节点，但是需要有一个保存所有节点的方法（例如数组，或者是链表），也就是说，这种方法，实际上是利用线性存储方式存储所有的节点，然后给每个节点一个父节点索引属性。这种方法，很难找到一个节点的子节点（理论上，通过遍历所有节点，找出以某个节点为父节点的节点，就是子节点），同时兄弟节点也可以这么找。 2）孩子双亲法，这种方法在每个节点具有双亲属性的前提下，再维护一条保存子节点的链表，这样就寻找子节点就很容易了。 3）孩子兄弟法，这种方法是参考二叉树结构的方法，其实社会学中，孩子兄弟可以得到很好的解释。一个家族中，父亲可以这样管理，首先对于子辈的，它子需要知道第一个子节点（我们称为长子）；对于兄弟，它子需要知道比他小一号的兄弟就可以了。这样的话，每个节点只需要维护两个引用（与二叉树一样，只是语义不同）。节点如果希望得到所有子节点，只需要访问第一个子节点，然后通过该节点，访问兄弟节点，然后一直访问下去。如果要得到所有兄弟节点，只需要直接访问兄弟节点，并且一直往下访问。 不管是访问子节点还是访问兄弟节点，都是比较容易的，并且每个节点的结构都比较规范（这是它最大的优点） 所以就上面三种而言，其实而有千秋，但是被我们充分利用的是孩子兄弟法，这种方法，与二叉树的结构是吻合的，并且这种方法，天生就可以用于保存森林。 其实，我们还可以自行设计出一个结构： 孩子法，每个节点维护一个指向所有节点的链表。但这个非常的不公整，所以不被待见。 孩子兄弟法，看起来变扭，但却十分有用。前面所说，孩子节点的语法结构和二叉树一样，这样我们可以将一个普通的树使用二叉树结构来保存，这就是树和二叉树之间的转换（其实说转换是不合适的，应该说是用二叉树结构来保存树。除了树这个概念我们有时候还要讨论森林，森林在社会学中，表达是一种无明显父节点的若干组织之间的组合。这个东西用孩子兄弟方法保存最好不过。因为，理论上讲，孩子兄弟节点表示的树，根节点上是没有右子树的（没有兄弟节点）。而如果把各个树看作是兄弟的话，恰好弥补了这个问题，并且，同时也保留了它们之间只是平等树，而不是同一个节点的多个子树（他们是森林的若干树）。 所以孩子兄弟法，是非常重要的一种树结构。 |
|
|
