树形结构是一种非线性结构。
树形结构是结点之间有分支,并具有层次关系的结构。它非常类似于自然界中的树。
树结构在客观世界中是大量存在的,例如家谱、行政组织机构都可用树形象地表示。
树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。
树的实例——家族树
在现实生活中,有入如下血统关系的家族可用树形图表示:
- 张源有三个孩子张明、张丽和张亮;
- 张明有两个孩子张林和张维;
- 张亮有三个孩子张平、张华和张群;
- 张平有两个孩子张晶和张磊。
attachment:tree.jpg
树的定义:
树是由n (n≥0)个结点构成的有限集合;n=0的树称为空树;当n≠0时,树中的结点应该满足以下两个条件:
- 有且仅有一个特定的结点称之为根,它没有前驱结点;
其余结点分成m(m≥0)个互不相交的有限集合latex($$T_1, T_2,\cdots,T_m$$),其中每一个集合又都是一棵树,称latex($$T_1, T_2,\cdots,T_m$$)为根结点的子树。