普通树
对于一棵普通类型的树形结构,可将其转化为二叉树之后再参考二叉树的方法进行相关操作。
孩子兄弟表示法(链式结构)
通过此方法可将普通树转化为二叉树
//孩子兄弟即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(也可以对各个树后根遍历得到)
发现与通过“孩子兄弟法”将树转为二叉树后的中序遍历序列相同
总结
对于树或者森林进行遍历操作,与转化为二叉树之后的操作对应关系如下:
树 | 森林 | 二叉树 |
---|---|---|
先根遍历 | 先序遍历 | 先序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |