data structure

1. 树的存储结构

树的存储方式有很多,即可采用顺序存储结构又可采取链式存储结构,只要能唯一反映树中各结点之间的逻辑关系即可,这里介绍三种。

1.1 双亲表示法

这种存储方式采用一组连续空间来存储每个结点,同时在每个结点中增设一个伪指针,指示其双亲结点在数组中的位置。根结点下标为 0,其伪指针域为 -1。

该存储结构利用了每个结点(根结点除外)只有唯一双亲的性质,可以很快得到每个结点的双亲结点,但求结点的孩子时需要遍历整个结构。

1.2 孩子表示法

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构,此时 n 个结点就有 n 个孩子链表(叶子结点的孩子链表为空表)

这种存储方式寻找子女的操作非常直接,而寻找双亲的操作需要遍历 n 个结点中孩子链表指针所指向的 n 个孩子链表。

实际存储中,tree[n] 表示所有的结点,结点包括数据域,孩子链表的头指针,孩子链表存储孩子索引即可 。

1.3 孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法,即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针,及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)

这种存储表示法比较灵活,其最大的优点是可以方便地实现树转换为二叉树的操作,易于查找结点的孩子等,但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个 parent 域指向其父结点,则查找结点的父结点也很方便

2. 树、森林与二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构,因此以二叉链表作为媒介可以导出树与二叉树的一个对应关系,即给定一棵树,可以找到唯一的一棵二叉树与之对应。从物理结构上,树的孩子兄弟表示法与二叉树的二叉链表表示法相同,即每个结点共有两个指针,分别指向结点第一个孩子和结点的下一个兄弟结点,而二叉链表中使用双指针。因此,可以用同一存储结构的不同解释将一棵树转换为二叉树。

树转换为二叉树的规则 :每个结点左指针指向它的第一个孩子结点,右指针指向它在树中的相邻兄弟结点,可表示为 “左孩子右兄弟” 。由于根结点没有兄弟,所以由树转换而得到的二叉树没有右子树。

将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树,再将第一棵树的根作为转换后的二叉树的根,将第一棵树的左子树作为转换后二叉树根的左子树,将第二棵树作为转换后二叉树的右子树,将第三棵树作为转换后二叉树根的右子树的右子树,以此类推,就可以将森林转换为二叉树 。

二叉树转换为森林的规则 :若二叉树非空,则二叉树的根及其左子树为第一棵树的二叉树形式,二叉树的根的右子树又棵视为一个由除第一棵树外的森林转换后的二叉树,应用同样的方法,知道最后一棵没有右子树的二叉树为止,这样就得到了原森林。二叉树转换为树的规则与此类似,二叉树转换为树或森林是唯一的。

树转换成二叉树的画法

  1. 在兄弟结点之间加一连线
  2. 对每个接待你,只保留它与第一个子结点的连线,与其他字节带你的连线全部抹掉
  3. 以树根为轴心,顺时针旋转 45 度

森林转换为二叉树的画法

  1. 将每棵树的根相连
  2. 将森林中的每棵树转换成相应的二叉树
  3. 以第一棵树的根为轴心顺时针旋转 45 度

3. 树和森林的遍历

树的遍历操作是某种方式访问树中的每个结点,且只访问一次。树的遍历操作主要有先根遍历和后根遍历。

  1. 先根遍历。若树非空,则先访问根结点,再按从左到右的顺序遍历根结点的每棵子树。其访问顺序与这棵树对应二叉树的先序遍历顺序相同。
  2. 后根遍历。若树非空,则按从左到右的顺序遍历根结点的每棵子树,之后再访问根结点。其访问顺序与这棵树相应二叉树的中序遍历顺序相同。

另外,树也有层次遍历,与二叉树的层次遍历思想基本相同,即按层序依次访问各结点。

按照森林和树相互递归的定义,棵得到森林的两种遍历方法。

  1. 先序遍历森林。若森林为非空,则按如下规则进行遍历
    1. 访问森林中第一棵树的根结点
    2. 先序遍历第一棵树根结点的子树森林
    3. 先序遍历除去第一棵树之后剩余的树构成的森林
  2. 中序遍历森林。若森林为非空,则按如下规则进行遍历
    1. 中序遍历森林中第一棵树的根结点的子树森林。
    2. 访问第一棵树的根结点
    3. 中序遍历除去第一棵树之后剩余的树构成的森林

树和森林的遍历:可采用对应二叉树的遍历算法来实现

森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

4. 树的应用 - 并查集

并查集是一种简单的集合表示,它支持以下 3 种操作

  1. Union(S, Root1, Root2) :吧集合 S 中的子集合 Root2 并入子集合 Root1 。要求 Root1 和 Root2 互不相交,否则不执行合并。
  2. Find(S, x) :查找集合 S 中单元素 x 所在的子集合,并返回该子集合的名字。
  3. Initial(S) :将集合 S 中的每个元素都初始化为只有一个单元素的子集合。

通常用树(森林)的双亲表示作为并查集的存储结构。每个子集合以一棵树表示。所有表示子集合的树,构成表示全集合的森林,存放再双亲表示数组内。通常用数组元素的下标代表元素名,用根结点的下标代表子集合名,根结点的双亲结点为负数 。