树形结构是一类重要的非线性数據结构.其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组織机构都可用树来形象表示.下面总结一下对于树的一些基本概念的描述.

下面列出树结构中的一些基本术语.

1. 树的 结点 包含一个数据元素及若幹指向其子树的分支.

分支结点也称为内部结点. 树的度 是树内各结点的度的最大值. 上图(b)的树的度为 3 .

而A则是D的双亲 , 同一个双亲的孩子之间互称兄弟(Sibling). 例如, H , I  和 J 互为兄弟. 将这些关系进一步推广, 可认为D是M的祖父. 结点的祖先(Ancestor)是从根到该结点所经分支上的所有结点. 例如,

4. 结点的 层次(Level) 从根开始定義起, 根为第一层, 根的孩子为第二层. 若某结点在第L层, 则其子树的根就在第L+1层. 其双亲在同一层的结点互为 堂兄弟 . 例如, 结点G与 E , F , H , I , J 互为堂兄弟.

5. 如果将樹中结点的各子树看成从左至右是有次序的(即不能互换), 则称该数为 有序树 ,否则称为 无序树 . 在有序树中最左边的子树的根称为第一个孩子, 最祐边的称为最右一个孩子.

6. 森林(Forest) 是m(m>=0)棵互不相交的树的集合. 对树中每个结点而言, 其子树的集合即为森林. 由此 , 也可以森林和树相互递归的定义来描述树.

!= 0 时, 在树根和其子树森林之间存在下列关系 :

这个定义将有助于得到森林和树与二叉树之间转换的递归定义.

数据结构和算法——二叉树: