大话数据结构007 树

树

树是典型的的一对多的关系

有且仅有一个称为根节点的元素，如图中的A，子树数量不做限制，但是不存在交叉。

以下不是树：

节点拥有的子树的个数称为度，度为0的节点称为叶子结点或者终端节点，度不为0的节点称为非叶子节点或者分支节点。

树的度就是全部子树的度的最大值。

 

父级节点称为双亲，子节点称为孩子。同一个双亲的子节点之间互为兄弟。

树的深度是树的最高层级。

树中的各个节点之间存在次序，称为有序树，否则称为无序树。

森林是多个互不相交的树的集合。

 

树的模型

 

 

树的存储结构1 ：双亲表示法

 

data存储本节点的数据，parent存的是指针，存储双亲节点的位置

我们以一个树为例：

根节点的双亲默认为-1

这样，我们可以根据双亲节点的指针迅速的找到双亲节点的位置。

但是，这样的存储结构还是有问题，怎么找到子节点呢？

我们增设长子指针。

 

树的存储结构2 ：孩子表示法

 

对于每个节点，我们使用多重链表存储孩子域。

方法一：使用树的度来分配指针个数。（一个指针对应着一个子树的根节点）

 

 

 方法二：每个节点的指针的个数就是本节点的度。

 

data存储数据，degree存储的是本节点的度，后面是本节点的指针域。

 

我们结合上述两种方法，来看孩子表示法：

将每个节点的孩子排列起来，以单链表作为存储结构，n个节点就会有n个链表，n个头指针组成一个线性表，存放到一维数组中。

左侧的数组存储的是各个节点的链表的位置（长子的存储位置）。

同一行属于同一个双亲的兄弟节点。

这样查找孩子是方便的，但是找双亲是很难的，需要遍历。

我们稍作改进，添加双亲指针即可：

 

树的存储结构3：孩子兄弟表示法

 

为长子添加右兄弟指针域：