来自计算思维百科
跳转至: 导航搜索

树是一类重要的非线性数据结构,可以对有层次的数据进行组织。

基本概念

树是n(n≥0 )个结点的有限集T,在一棵非空树中:

①有且仅有一个特定的称为根的结点。

②当n≥1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树,如图1(a)即为以A为根节点的树,该树由分别以B、C、D为根节点的三棵子树组成。这是一种递归形式的定义,因为在树的定义中又用到树的概念。 

3.2.15.png3.2.16.png

                       图1 树

树的节点包含一个数据元素及若干指向其他子树的分支。节点拥有的子树数称为节点的度。度为0的节点称为叶节点或终端节点,度不为0的节点称为非终端节点或分支节点。除根节点之外,分支节点也称为内部节点。树的度是树内各节点的度的最大值。如图1(a)中,这棵树节点的度的最大值是节点D和G的3,所以树的度为3。度为2的树称为二叉树,如图1(b)所示。二叉树是使用最多的一种树结构。

树中节点的层次从根节点开始定义起,根为第一层,根的孩子为第二层。若某节点在第l层,则其子树的根就在第l+1层。其双亲在同一层的节点互为堂兄弟。显然,图2中,D、E、F是堂兄弟,而G、H、I、J也是。树中节点的最大层次称为树的深度或高度,图2中树的深度为4。

3.2.17.png

图2 树的层次与深度示意图

应用范围

树形数据结构可以用到很多具有层次结构的问题中,如公司员工的管理关系等。

使用方法及步骤

1、确定根节点;

2、有根节点按照父子关系创建子节点;

3、对每个子节点重复步骤2;直至所有节点都构建好。

应用案例

遗传系谱图

遗传系谱图中圆圈代表女性,正方形代表男性。在数据结构里面,我们可以用树的知识来简化这种模型,不再区分性别,只分成孩子和双亲。