【数据结构】4——树和森林

数据结构——4树和森林

笔记

树的存储结构

双亲表示法

每个节点只存储其父节点的引用或索引

通常使用数组来存储树中所有节点的信息，数组的每个元素对应一个节点，数组的索引通常从0或1开始。对于数组中的任意元素（即某个节点），其值表示该节点的双亲节点在数组中的位置（索引）。如果某个节点是根节点，则其双亲位置通常用-1或null表示，以表示它没有双亲节点。

节点结构：每个节点通常包含数据部分和指向其父节点的引用或索引。节点的数据部分可以是任何类型的信息，而父节点的引用可以是节点在数组中的索引，也可以是指向父节点的指针。
存储方式：整个树结构存储在一个数组（或类似的数据结构）中。根节点通常在数组的第一个位置（或者索引为0的位置），其父节点的引用为空或为一个特定的标识（如-1），表示它没有父节点。
遍历能力：通过双亲表示法可以方便地找到任意节点的父节点，但要找到某个节点的所有子节点则需要遍历整个数组，效率较低。
空间利用：这种表示法不需要额外的空间来存储子节点的信息，因此在空间利用上相对高效。

       A
     / | \
    B  C  D
   / \
  E   F
  
从索引 1 开始
索引:      1  2  3  4  5  6
节点:      A  B  C  D  E  F
双亲索引: -1  1  1  1  2  2

节点 A 的双亲索引是 -1，表示它是根节点。
节点 B、C、D 的双亲索引都是 1，表示它们的双亲是节点 A。
节点 E 的双亲索引是 2，表示它的双亲是节点 B，以此类推。


//查找节点 E 的双亲节点：
从数组中找到索引为 5 的元素，其值为 2，表示节点 E 的双亲节点是索引为 2 的节点，即节点 C。

孩子链表

每个节点除了存储其数据之外，还包含一个指向其所有子节点的链表。

节点结构：每个节点包含数据部分和指向其第一个子节点的指针。如果节点没有子节点，则该指针为空。
子节点链表：每个节点可能有一个链表，链表的每个节点代表其一个子节点。链表的每个节点通常包含指向子节点的指针和指向下一个子节点链表节点的指针。
遍历能力：孩子链表结构便于遍历树的子节点，可以方便地访问任何节点的所有直接子节点。
空间利用：孩子链表结构需要额外的空间来存储子节点链表的指针，因此相对于双亲表示法，它可能占用更多的空间。
灵活性：这种表示法可以很容易地表示动态变化的树结构，如二叉查找树的插入和删除操作。

        A
       / \
      B   C
     / \
    D   E

伪代码
节点A:
    value = "A"
    first_child = 节点B
    next_sibling = None

节点B:
    value = "B"
    first_child = 节点D
    next_sibling = 节点C

节点C:
    value = "C"
    first_child = None
    next_sibling = None

节点D:
    value = "D"
    first_child = None
    next_sibling = 节点E

节点E:
    value = "E"
    first_child = None
    next_sibling = None

孩子兄弟表示法（二叉树表示法、二叉链表表示法）

基本原理：
在孩子兄弟表示法中，每个节点包含三个部分：

数据域：存储该节点的数据信息。
第一个孩子指针：指向该节点的第一个孩子节点。
下一个兄弟指针：指向该节点的下一个兄弟节点。

通过这种方式，树中的每个节点可以通过其孩子指针找到它的所有孩子节点，通过兄弟指针找到它的所有兄弟节点。这样就可以方便地遍历整棵树。

找双亲比较难

假设有一棵树如下：
     O
   / |  \
  P  Q   R
 / \ /
S  T U
|
V
用孩子兄弟表示法表示为：
节点 O：数据为 O，第一个孩子为节点 P，下一个兄弟为 null。
节点 P：数据为 P，第一个孩子为节点 S，下一个兄弟为节点 Q。
节点 Q：数据为 Q，第一个孩子为 null，下一个兄弟为节点 R。
节点 R：数据为 R，第一个孩子为节点 U，下一个兄弟为 null。
节点 S：数据为 S，第一个孩子为 null，下一个兄弟为节点 T。
节点 T：数据为 T，第一个孩子为 null，下一个兄弟为 null。
节点 U：数据为 U，第一个孩子为节点 V，下一个兄弟为 null。
节点 V：数据为 V，第一个孩子为 null，下一个兄弟为 null。

树与二叉树转换

树转换为二叉树的方法：
加线：在兄弟之间加一条连线。
抹线：对每个节点，除了其左孩子外，去除其与其余孩子之间的连线。
旋转：以树的根结点为轴心，将整棵树顺时针旋转45度。
左（第一个）孩子右兄弟

       A
     / | \
    B  C  D
   / \     \
  E   F     G

根节点 A 的第一个子节点 B 作为它的左孩子。
B 的第一个子节点 E 作为它的左孩子，C 是 B 的兄弟，因此在二叉树中作为 B 的右孩子。
E 的兄弟 F 作为它的右孩子。
C 没有子节点，但它有兄弟 D，所以 D 作为 C 的右孩子。
D 的第一个子节点 G 作为它的左孩子。
       A
      /
     B
    / \
   E   C
    \   \
     F   D
         /
        G

二叉树转换为树的方法为：
加线：若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点……都与该结点用线连接起来。
抹线：抹掉原二叉树中所有结点与其右孩子结点的连线。
调整：使各结点按层次排列，形成树结构。

原先在二叉树中的左孩子表示多叉树中的第一个子节点，而右兄弟则表示多叉树中的后续子节点。

    A
   /
  B
 / \
E   C
 \   \
  F   D
和上面相反，右孩子是兄弟
    A
   /|\
  B C D
 / \
E   F

森林和二叉树转化

森林转二叉树

选择一棵根树：从森林中选择一棵树作为新二叉树的根。这棵树将成为二叉树的根节点。
连接其他树：将森林中的其他树依次连接到选定的根树的右侧。为了做到这一点，可以将每棵树的根节点作为上一棵树的根节点的右子节点。
调整结构：如果需要，调整树的结构以确保它符合二叉树的定义。这可能包括重新排列节点以保持正确的顺序或平衡。

二叉树转森林

去右孩线，二叉树转树

树和森林的遍历

树

先根

    A
   / \
  B   C
 / \   \
D   E   F

访问根节点 A。
遍历左子树：
访问左子树的根节点 B。
遍历 B 的左子树：
访问 D。
遍历 B 的右子树：
访问 E。
遍历右子树：
访问右子树的根节点 C。
遍历 C 的左子树（为空，跳过）。
遍历 C 的右子树：
访问 F

A -> B -> D -> E -> C -> F

后根

      A
     / \
    B   C
   / \
  D   E
  
递归遍历左子树 B
递归遍历左子树 D，访问 D
递归遍历右子树 E，访问 E
回到 B，访问 B
递归遍历右子树 C，访问 C
回到根节点 A，访问 A

D E B C A

层次

    A
   / \
  B   C
 / \   \
D   E   F

A B C D E F 

森林

Tree 1:      Tree 2:       Tree 3:
    A           F             K
   / \         / \           / \
  B   C       G   H         L   M
     /             \
    D               I

前序遍历结果：
Tree 1: A B C D
Tree 2: F G H I
Tree 3: K L M
森林的前序遍历整体结果：A B C D F G H I K L M

中序遍历结果：
Tree 1: B A D C
Tree 2: G F H I
Tree 3: L K M
森林的中序遍历整体结果：B A D C G F H I L K M

后序遍历结果：
Tree 1: B D C A
Tree 2: G I H F
Tree 3: L M K
森林的后序遍历整体结果：B D C A G I H F L M K