£ 6.1 树
£ 6.1.1 树的定义
( 1 )定义
树( Tree ):是 n ( n≥0 )个结点的有限集。
定义一:(递归定义):
① 在任意一棵非空树中,有且仅有一个特定的称为根( root )
的结点;
② 当 n>1 时,其余结点可分为 m ( m>0 )个互不相交的有限集
T
1
, T
2
, … , T
m
,其中每一个集合本身又是一棵树。并且
T
1
, T
2
, … , T
m
,称为根的子树( SubTree )。
定义二:(形式定义)
任何一棵树是一个二元组 Tree = (root, F) 。
其中: root 是数据元素,称做树的根结点; F 是 m ( m≥0 )棵树的森林,
F =( T
1
, T
2
, … , T
m
),其中 T
i
= (r
i
, F
i
) 称做根 root 的第 i 棵子树;当 m≠0
时,在树根和其子树森林之间存在下列关系:
RF = {<root, r
i
> | i = 1, 2, … ,m; m > 0}
第 1 页 / 共 63 页