当前位置:C++技术网 > 资讯 > 数据结构笔记分享:2 树的基本术语介绍

数据结构笔记分享:2 树的基本术语介绍

更新时间:2015-11-05 23:43:24浏览次数:1+次


结点(node):树中的元素。

根结点和它的子树根(如果存在)之间形成一条边。

E、A、F、B、G、C、D、L、J、M、N均为结点。

路径(path):从某个结点沿树中的边可到达另一个结点,则称这两个结点之间存在一条路径。

E和N之间存在一条路径

双亲(parent):若一个结点有子树,那么该结点称为子树根的双亲。
A、F、B的双亲是E。C、D的双亲是F。
孩子(child):某结点子树的根是该结点的孩子。
E有三个孩子:A、F、B。D有一个孩子:J。
兄弟(sibling):有相同双亲的结点互为兄弟。
A、F、B互为兄弟,C和D互为兄弟。

后裔(decendent):一个结点的所有子树上的任何结点都是该结点的后裔。
结点C的后裔为:L、M、N。
祖先(ancestor):从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点L的祖先为:E、F、C。
结点的度(degree):结点拥有的子树数。
结点E的度为3,结点F的度为2,
结点A的度为1,结点G的度为0。
叶子(leaf):度为零的结点。
B、G、J、M、N均为叶子结点。
分支结点(branch):度不为零的结点。
E、A、F、C等为分支结点。
树的度:树中结点的最大的度。
该树的度为3。

结点的层次:根结点的层次为1,其余结点的层次等于其双亲结点的层次加1。
结点E的层次为1。
结点M的层次为5。
树的高度:树中结点的最大层次。
∵树中结点的最大
层次为5。
∴树的高度为5。