❤️

ARCHAI

Undergraduate / Rookie

Back

普通树

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

孩子兄弟表示法(链式结构)

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

//孩子兄弟即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(也可以对各个树后根遍历得到)

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

总结

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

森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历
Archai
Built with Hugo
Theme Stack designed by Jimmy