树、森林与二叉树转换

树的存储方式

双亲表示法

用数组保存结点，每个结点额外保存双亲下标。

1
2
3
4
typedef struct {
    ElemType data;
    int parent;
} PTNode;

根结点的 parent = -1。双亲表示法找双亲方便，找孩子需要扫描数组。

适用场景：经常需要找双亲、较少需要找孩子的结构，例如并查集。

存储森林时，可以让每棵树的根结点 parent = -1；需要额外知道哪些结点是根，或扫描所有 parent = -1 的位置得到森林的根集合。

孩子表示法

每个结点保存一个孩子链表，链表中记录所有孩子的位置。找孩子方便，找双亲不方便。

1
2
3
4
5
6
7
8
9
typedef struct ChildNode {
    int childIndex;
    struct ChildNode *next;
} ChildNode;

typedef struct {
    ElemType data;
    ChildNode *firstChild;
} ChildBox;

孩子表示法是“顺序存储结点 + 链式存储孩子关系”的结合。存储森林时同样要记录多个根的位置。

适用场景：经常需要找孩子、较少需要找双亲的结构，例如服务流程树。

孩子兄弟表示法

每个结点保存第一个孩子和右兄弟：

1
2
3
4
5
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild;
    struct CSNode *nextSibling;
} CSNode, *CSTree;

孩子兄弟表示法可以把普通树转换成二叉树结构：左指针指向第一个孩子，右指针指向下一个兄弟。

树转换为二叉树

规则：

  1. 每个结点的第一个孩子作为它的左孩子。
  2. 每个结点的右兄弟作为它的右孩子。
  3. 原树中兄弟之间的横向关系变为二叉树中的右链。

口诀：左孩子，右兄弟。

森林转换为二叉树

森林中每棵树先转换为二叉树，然后把各棵树的根看作兄弟，用右指针连接。

结果：

  • 第一棵树的根是整棵二叉树的根。
  • 第一棵树根的右孩子是第二棵树的根。
  • 第二棵树根的右孩子是第三棵树的根，以此类推。

二叉树还原为树或森林

还原规则与转换规则相反：

  • 左孩子链还原为“第一个孩子”。
  • 右孩子链还原为“兄弟”。
  • 根结点的右链若存在，说明还原结果是森林；根结点没有右兄弟时，还原结果是一棵树。

树、森林与二叉树遍历对应关系

原结构 遍历 对应的左子右兄二叉树遍历
树 先根遍历 先序遍历
树 后根遍历 中序遍历
森林 先序遍历 先序遍历
森林 中序遍历 中序遍历

一般的树没有“中序遍历”。

树的层次遍历仍然用队列实现：先访问根，再从左到右依次访问每一层的结点。

森林的先序遍历先访问第一棵树的根，再先序遍历第一棵树根的子树森林，最后先序遍历剩余森林。

森林的中序遍历先中序遍历第一棵树根的子树森林，再访问第一棵树的根，最后中序遍历剩余森林。