树的基本概念
定义：树是n个结点的有限集。n=0时称为空树，n>=1时为非空树。
在任意一颗非空树中：
- 有且仅有一个特定的称为根的结点。
- 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2……Tm。
其中每一个集合本身又是一棵树，并且称为根的子树。 - 用到了递归的概念。也即树中还有树的概念。
树图.png
对于树的定义还要强调两点：
- n>0时根结点是唯一的，不可能存在多个根结点。
- m>0时子树的个数没有限制，但他们一定互不相交。
结点分类：
结点包含：1）一个数据元素 2）若干指向其子树的分支
结点的度：结点拥有的子树数。度为0的结点称为叶结点或终端结点（即树的最下方），度不为0的称为分支结点或内部结点。
树的度：树内各结点度的最大值。
结点间关系：
孩子（child）：结点的子树的根（也即下方第一个）称为该结点的孩子。
双亲（parent）:上面的那个结点称为孩子的双亲。
兄弟（Sibling）：同一个双亲的孩子，如上图D和E。
堂兄弟：双亲在同一层的结点。
树的其他相关概念：
结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。上图所示树图就有三层。
树的深度或高度：树种结点的最大层次。
有序树无序树：树中结点的各子树从左至右，如若有次序不能互换，则称为有序树，否则称为无序树。
森林：是m颗（m>0）互不相交的树的集合。对树中每个结点而言，其子树的集合就是森林。（不包括根，因为算上根就只有一棵树了。）
网友评论