文档介绍：第6章树和二叉树
树
树的定义
从数据结构角度看,树包含n(n≥0)个结点,当n=0时,称为空树;非空树的定义如下:
T=(D,R)
其中,D为树中结点的有限集合,关系R满足以下条件:
有且仅有一个结点k0∈D,它对于关系R来说没有前驱结点,结点k0称作树的根结点。
除根结点k0外,D中的每个结点有且仅有一个前驱结点,但可以有多个后继结点。
D中可以有多个终端结点。
【】有一棵树T1=(D,R),其中
D={A,B,C,D,E,F,G,H},
R={r}
r={<A,B>,<A,C>,<A,D>,<C,E>,<C,F>,<D,G>,<E,H>}
画出其逻辑结构图。
解:该树中结点A没有前驱结点,它是树的根结点,该树的逻辑结构图如右图所示。在这棵树中,A是根结点,其余结点分成三个互不相交的子集:
T1={B},
T2={C,E,F,H},
T3={D,G}。
T1、T2、T3都是根结点A的子树,且各自本身也是一棵树。
说明:树中结点之间的关系应为有向关系,在上图中,结点之间的连线即分支线都是有向的,默认箭头向下的。
树的逻辑结构表示
树的逻辑结构表示:
树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。
文氏图表示法。使用集合以及集合的包含关系描述树结构。
凹入表示法。使用线段的伸缩关系描述树结构。
括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号分隔。
树的基本术语
1. 结点的度与树的度:树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。
2. 分支结点与叶结点:度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中,每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1,被称为单分支结点;对于度为2的结点,其分支数为2,被称为双分支结点,其余类推。
A
B
C
D
E
F
G
J
H
I
K
L
M
度为3
度为2
3. 路径与路径长度:对于任意两个结点di和dj,若树中存在一个结点序列di,di1,di2,…,din,dj,使得序列中除di外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由di到dj的一条路径,用路径所通过的结点序列(di,di1,di2,…,dj)表示这条路径。
路径长度等于路径所通过的结点数目减1(即路径上分支数目)。
A
B
C
D
E
F
G
J
H
I
K
L
M
A到K的路径为A,D,I,K,
其长度为3
4. 孩子结点、双亲结点和兄弟结点:在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。
具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点。
从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。
A
B
C
D
E
F
G
J
H
I
K
L
M
5. 结点的层次和树的高度:树中的每个结点都处在一定的层次上。结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。
A
B
C
D
E
F
G
J
H
I
K
L
M
1
2
3
4