MENU

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

April 2, 2019 • 数据结构与算法

一般树的表示

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

用链表实现

  • 如果用链表来实现的话,每个节点就是一个结构体,如下图:
  • 在这颗树中,节点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度,如下图
  • 这个时候我们可以看到另一颗树,我们遗忘掉儿子-兄弟表示法中各个节点的关系,那么就可以发现,这棵树中每个节点只有两个指针域,一个左边一个右边,每个节点最多只有两个子节点,具有这样特征的树,我们叫做二叉树 点题!!
二叉树节点结构示意图
  • 二叉树是我们主要研究的树形数据结构。

问题

  • 树的集合称为森林。是否也可以使用“儿子-兄弟”表示法存储森林?如何实现?
Archives QR Code
QR Code for this page
Tipping QR Code