高中信息技术-竞赛班数据结构专项培训教程-07树教案(共19页).doc

精选优质文档-倾情为你奉上7 树7.1 树的概念【定义】 树（Tree）是n（n0）个结点的有限集合T，它满足如下两个条件：(1) 有且仅有一个特定的称为根（Root）的结点；(2) 其余的结点可分为m（m0）个互不相交的有限集合，其中每一个集合又都是一颗树，并称为根的子树（Sub Tree）。 图7.1.1【基本术语】k1. 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度（degree）。如图7.1，A的度为3，C的度为1，F的度为0。2. 度为0的结点称为叶子（leaf）或终端结点。例如K、L、F、G、M、I、J。度不为0的结点称为分支结点或非终端结点。除根结点外，分支结点也称为内部结点。3. 树的度是树内各结点的度的最大值，如图7.1中树的度为3。4. 结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲（parent）。如图7.1.1，B为A的子树的根，则B是A的孩子，