数据结构的C++实现之树的定义和基本概念

数据结构的C++实现之树的定义和基本概念2013-08-14 csdn Simba888888一、树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点。

（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree），如图1所示：

图1

树的定义之中还用到了树的概念，即递归定义。如图2中的子树T1和T2就是根结点A的子树。当然D,G,H,I 组成的的树又是B结点的子树，E,J 组成的树是C结点的子树。

图2

对于树的定义还需要注意两点：

1.n>0时根结点是唯一的，不可能存在多个根结点。

2.m>0时，子树的个数没有限制，但它们一定是互不相交的。如图3中的两个结构就不符合树的定义，因为它们都有相交的子树。

图3

二.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点，除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图4，因为这棵树结点的度的最大值是结点D的度3，所以树的度也为3。

图4