27
先根遍历时结点的
A
JK
EF
G
后根遍历时结点的 访问次序：
EFBCIJKHGDA
H
IJK
28
森林
可以分解成三部分：
BCD
EF
G
H
IJK
1. 森林中第一棵树 的根结点；
2. 森林中第一棵 树的子树森林；
3. 森林中其它树构 成的森林。
29
森林的遍历
先序遍历 若森林不空，则 访问森林中第一棵树的根结点; 先序遍历森林中第一棵树的子树森林; 先序遍历森林中(除第一棵树之外)其
} PTNode;
6
树结构: typedef struct {
PTNode nodes [MAX_TREE_SIZE]; int r , n ;
// 根结点的位置和结点个数 } PTree;
7
二、孩子(链表)表示法:
第一种解决方案
data child1 child2 child3
childd
其中d是结点的度;
应当注意的是，和树对应的 二叉树，其左、右子树的概念 已改变为： 左是孩子，右是兄弟
24
6.4.3 树和森林的遍历
25
一、树的遍历 二、森林的遍历
26
树的遍历:
先根(次序)遍历:
若树不空，则先访问根结点，然后 依次按先根遍历各棵子树。
后根(次序)遍历:
若树不空，则先依次按后根遍历各 棵子树，然后访问根结点。
4
一、双亲表示法:
data parent
A BC D
0 A -1 r=0 1 B 0 n=7 2C 0
EF
3D 0 4E 2
G
5F 2 6G 5
5
C语言的类型描述:
#define MAX_TREE_SIZE 100
结点结构: data parent
typedef struct PTNode { ElemType data; int parent; // 双亲位置域
第六章
树和二叉树
1
6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用
2
6.4 树和森林
6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历
3
6.4.1 树的存储结构 一、双亲表示法 二、孩子链表表示法 三、孩子兄弟存储表示法
树
森林
二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历
32
设树的存储结构为孩子兄弟链表 typedef struct CSNode{
ElemType data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;
D
F
G
13
14
C语言的类型描述: 结点结构: firstchild data nextsibling
typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;
15
孩子结点结构: child next
typedef struct CTNode { int child; struct CTNode * next;
} *ChildPtr;
10
双亲结点结构 data firstchild
typedef struct { ElemType data; ChildPtr firstchild;
余树构成的森林。
即：依次从左至右对森林中的每一棵 树进行先根遍历。
30
中序遍历
若森林不空，则 中序遍历森林中第一棵树的子树森林; 访问森林中第一棵树的根结点; 中序遍历森林中(除第一棵树之外)其
余树构成的森林。 即：依次从左至右对森林中的每一棵 树进行后根遍历。
31
树的遍历和二叉树遍历 的对应关系 ？
A B
E
K
3 棵树的森林
T1 A T2 F T3 H
C
D
F
EG
H
I
B
G
I
K
J
C
K
J
D
森林的二叉树表示
E 各棵树的二叉树表示
20
由二叉树转换为森林的转换规则为:
若 B = Φ, 则 F = Φ; 否则， 由 Node(root) 对应得到 ROOT( T1 ); 由LBT 对应得到 ( t11, t12, …，t1m); 由RBT 对应得到 (T2, T3, …, Tn)。
由于每个结点的子女个数是不限 制的,则如按照度最大的结点的度分配 子女指针的个数,则在实际应用中,会有 很多空指针域,造成空间的浪费。
8
第二种解决方案
A BC D
EF G
data firstchild
0 A -1 1 1B0 2C0 4 3D0 4E2 6 5F2 6 G4
23
5
r=0 n=7
9
C语言的类型描述:
6.4.2 森林与二叉树的转换
设森林 F = ( T1, T2, …, Tn ); T1 = ( root，t11, t12, …, t1m );
二叉树 B =( LBT, Node(root), RBT );
16
由森林转换成二叉树的转换规则为:
若 F = Φ，则 B = Φ; 否则，
由 ROOT( T1 ) 对应得到Node(root); 由 (t11, t12, …, t1m ) 对应得到 LBT; 由 (T2, T3,…, Tn ) 对应得到 RBT。
21
二叉树转化成树(森林)的简单方法
㈠ 若某结点是其双亲的左孩子，则将该 结点的双亲同该结点的右孩子、右孩 子的右孩子、右孩子的右孩子的右孩 子……加连线；
㈡ 去掉所有双亲与右孩子之间的连线。
22
A
B
C
D
F
E
G
H
I
K
J
森林的二叉树表示
T1
T2 T3
A
FH
BCD G I J
E
K
3 棵树的森林
23
由此，树和森林的各种操作均 可与二叉树的各种操作相对应。
// 孩子链的头指针 } CTBox;
11
树结构:
typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n , r ; // 结点数和根结点的位置
} CTree;
12
三、树的孩子-兄弟(二叉链表)表示法
root
A
A
BC D
B C
EF
A
GB C
E
D
F
G
E
17
T1 T2,…,Tn
T11,T12,…,T1m
root
LBT
RBT
18
树(森林)转化成二叉树的简单方法
㈠ 在亲兄弟之间加连线；
㈡ 保留结点与第一个孩子之间的连线， 去掉与其余孩子之间连线；
㈢ 顺时针旋转45度。 以根结点为轴；左孩子不再旋转。
19
T1 A T2 F T3 H BCD G I J