一、树的存储结构

普通树中的一个结点可以有任意多个孩子，因此不能像二叉树那样只设置“左指针”和“右指针”。常见存储方式有三种。

1. 双亲表示法

每个结点记录两部分：

  • 结点的数据
  • 该结点双亲在数组中的下标

例如：

        A
      / | \
     B  C  D
       / \
      E   F

可以存成：

下标 数据 双亲下标
0 A -1
1 B 0
2 C 0
3 D 0
4 E 2
5 F 2

根结点没有双亲，所以通常记为 -1。

优点： 查找某个结点的双亲非常方便。

缺点： 查找一个结点的所有孩子不方便，需要遍历整个数组。

2. 孩子表示法

每个结点维护一个链表，链表中记录它所有孩子的位置。

例如结点 A 的孩子链表为：

A → B → C → D

结点 C 的孩子链表为：

C → E → F

整体结构类似：

A : B → C → D
B : 空
C : E → F
D : 空
E : 空
F : 空

优点： 查找某个结点的所有孩子非常方便。

缺点： 查找双亲不方便。

3. 孩子兄弟表示法

        A
      / | \
     B  C  D
       / \
      E   F
  • 左孩子右兄弟

这种结构非常重要，因为它可以把任意一棵普通树转化为二叉树。

二、树转换为二叉树

普通树转换成二叉树时，使用的核心规则是：

左指针指向第一个孩子，右指针指向下一个兄弟。

也称为“左孩子右兄弟”。

原树：

        A
      / | \
     B  C  D
       / \
      E   F

转换后如下。

        A
       /
      B
       \
        C
       / \
      E   D
       \
        F

注意：转换后的二叉树中，某个结点的“右孩子”不一定是原树中的孩子，它可能是原树中的兄弟。

还原也需要掌握，不过都差不多，我就不写了

三、森林转换为二叉树

森林是由多棵互不相交的树组成的。

例如：

树1：        A          树2：       G
           / \                    / \
          B   C                  H   I

转换步骤：

  1. 分别把每棵树转换为二叉树。
  2. 将第二棵树的根作为第一棵树根的右孩子。
  3. 将第三棵树的根作为第二棵树根的右孩子。
  4. 依次连接。

结果类似：

        A
       /  \
      B    G
       \   /
        C  H
            \
             I

核心规则仍然是：

左孩子右兄弟

麻辣火锅+牛奶果然是一种错误，搞得我一天都在拉肚子…… 下次再也不敢这么吃了🤡

花海咲季