ARCHAI

普通树

对于一棵普通类型的树形结构，可将其转化为二叉树之后再参考二叉树的方法进行相关操作。

孩子兄弟表示法（链式结构）

通过此方法可将普通树转化为二叉树

//孩子兄弟即Child, Sibling
typedef struct CSNode{
    Elemtype data;
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针,等价于*lchild,*rchild
}CSNode,*CSTree

图示如下

树的遍历

1.深度优先遍历（先根遍历&后根遍历）

• 先根遍历

若树非空，先访问根结点，再依次对每棵子树进行先根遍历(递归)。

对如上图所示的树进行先根遍历：

A B C D

A (BE ) (CF) (DG)

A (BEH) (CF) (DG)

即先根遍历序列为A B E H C F D G

发现与通过“孩子兄弟法”将树转为二叉树后的先序遍历序列相同

• 后根遍历

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

对如上图所示的树进行后根遍历：

B C D A

(E B) (F C) (G D) A

(H E B) (F C) (GD) A

即后根遍历序列为H E B F C G D A

发现与通过“孩子兄弟法”将树转为二叉树后的中序遍历序列相同

2.广度优先遍历（层序遍历）

利用队列实现（参考二叉树层序遍历）

对于上图所示的树进行层序遍历：

A B C D E F G H

😯不难看出深度优先和广度优先分别表示遍历时的路径走向。前者是先往深处走，故为深度优先遍历；后者是先往宽了走，即为广度优先遍历。

森林

对于森林，也可以将其转化为二叉树之后进行操作

同样的，我们采用孩子兄弟法将树转化为二叉树，具体操作为将森林中各个树的根节点视为兄弟关系。如下图所示：

###　1.先序遍历

若森林为非空，则按如下规则进行遍历：

访问森林中第一棵树的根结点。

先序遍历第一棵树中根结点的子树森林。

先序遍历除去第一棵树之后剩余的树构成的森林。

B

(B E)

(B E K L)

(B E K L F)

(B E K L F) C

(B E K L F) (C G)

(B E K L F) (C G) D

(B E K L F) (C G) (D H)

(B E K L F) (C G) (D H M)

(B E K L F) (C G) (D H M I J)

最终，对森林的先序遍历序列为 B E K L F C G D H M I J(也可以对各个树先根遍历得到)

发现与通过“孩子兄弟法”将树转为二叉树后的先序遍历序列相同

2.中序遍历

若森林为非空，则按如下规则进行遍历：

中序遍历森林中第一棵树的根结点的子树森林。

访问第一棵树的根结点。

中序遍历除去第一棵树之后剩余的树构成的森林。

K L

K L E

K L E F

(K L E F B)

(K L E F B) (G C)

(K L E F B) (G C) (M)

(K L E F B) (G C) (M H I J)

(K L E F B) (G C) (M H I J D)

最终，对森林的先序遍历序列为 K L E F B G C M H I J D(也可以对各个树后根遍历得到)

发现与通过“孩子兄弟法”将树转为二叉树后的中序遍历序列相同

总结

对于树或者森林进行遍历操作，与转化为二叉树之后的操作对应关系如下：