树和二叉树：树的概念

树的概念

树的定义

树形式化定义： T={D,R} D是包含n个节点的有限集合(n>=0)。当n=0时，该树为空树，否则关系R满足以下条件：

• 有且仅有一个节点d属于D，它对于关系R来说没有前趋节点，节点d称作树的根节点
• 除根节点外，每个节点有且仅有一个前趋节点
• D中每个节点可以有零个或多个后继节点

树的递归定义： 树是由（n>=0）个节点组成的有限集合（记为T）。其中：

• 其中n=0，它是一棵空树，这时树的特例；
• 如果n>0,其中存在一个唯一节点作为树的根节点（root），其余节点可分为m（m>=0）个互不相交的有限子集T1,T2,…,Tm,而每个子集本身又是一颗树，称为称为根节点root的子树。
  

树的（逻辑）表示

（1）树形表示法。 使用一颗倒置的树表示树结构，非常直观和形象。

（2）文氏图表示法。 使用集合以及集合包含关系描述树结构。

（3）凹入表示法。 使用线段的伸缩关系表示树结构。

（4）括号表示法。 用一个字符串表示树。
基本形式：根（子树1，子树2，…，子树m）

树的基本术语

1.节点的度与树的度： 树中一个节点的子树的个数称为该节点的度。树中各节点的度的最大值称为树的度，通常将度为m的树称为m次树或者m叉树。

2.分支节点与叶节点： 度不为零的节点称为非终端节点，又叫分支节点。度为零的节点称为终端节点或叶节点（或叶子节点）

度为1的节点称为单分支节点；度为2的节点称为双分支节点，以此类推。

3.路径与路径长度： 两个节点di和dj的节点序列（di，d1，d2，…，dj）称为路径。其中<dx,dy>是分支。

路径长度等于路径所通过的节点数目减1（即路径上分支数目）。

4.孩子节点，双亲节点和兄弟节点： 在一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节点）。相应地，该节点被称作孩子节点的双亲节点（父母节点）

具有同一双亲的孩子节点互为兄弟节点

5.子孙节点和祖先节点： 在一颗树中，一个节点的所有子树中的节点称为该节点的子孙节点

从根节点到达一个节点的路径经过的所有节点被称为该节点的祖先节点

6.节点层次和树的高度： 树中的每个节点都处在一个层次上。节点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层，以此类推，一个节点所在的层次为其双亲节点所在的层次加1

树中节点的最大层次称为树的高度（或树的深度）

7.有序树和无序树： 若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树

8.森林： n（n>0）个互不相交的树的集合称为森林
只要把树的根节点删去就成了森林

反之，只要给n棵独立的树加上一个节点，并把这n棵树作为该节点的子树，则森林就变成了一颗树

树的性质

性质1 - 树中的节点树等于所有节点的度数加1

（1）树中每个分支计为一个节点的度—所有节点的度之和=分支树

（2）根节点加上一个分支，这样分支数与节点数相同—实际分支数=n-1(n=度之和+1)

性质2 - 度为m的树中第i层至多有m^i-1个节点（i>=1）

性质3 - 高度为h的m次数至多有 m^h-1/m-1 个节点