树的递归定义 若T1,T2,…,T是子树(T1可以不 是其他树的子树),它们的根分 别是a1a2A,T的子树是T2T2① 的子树是T3,…,Tk的子树是Tk,(⑦ 则称a1到a有路径(通路),记为: g a12a2…,ak 图-一棵树
11 树的递归定义 a b c d e f g 图 - 一棵树 •若T1 , T2 , …, Tk是子树（T1可以不 是其他树的子树），它们的根分 别是a1 ,a2 ,…,ak，T1的子树是T2 , T2 的子树是T3， …, Tk-1的子树是Tk， 则称a1到ak有路径（通路），记为： <a1 ,a2 ,…,ak>
§5.1.2基本术语 树枝(分枝):结点之间的二元关系(序偶) 度:结点拥有的子树(后继)的个数称为该结点的度, 这实质上是出度。 叶子:无后继(子树)的结点称为叶子 °分枝结点:有后继的结点称为分枝结点。 °儿子:结点x的子树的根称为x的儿子。 °双亲(父亲):结点x的前趋结点称为x的双亲。 祖先:结点x的父亲称为该结点的祖先;结点x的父亲的 祖先也称x的祖先。 12
12 •树枝（分枝）：结点之间的二元关系（序偶）。 •度：结点拥有的子树（后继）的个数称为该结点的度， 这实质上是出度。 •叶子：无后继（子树）的结点称为叶子。 •分枝结点：有后继的结点称为分枝结点。 •儿子：结点x的子树的根称为x的儿子。 •双亲（父亲）：结点x的前趋结点称为x的双亲。 •祖先：结点x的父亲称为该结点的祖先；结点x的父亲的 祖先也称x的祖先
§5.1.2基本术语 后代:结点x的儿子称x的后代,结点x的儿子的后代也称 x的后代。 兄弟:同父亲的结点称为兄弟结点 堂兄弟:父亲是兄弟关系的结点称为堂兄弟结点。 层次(层号):根为第1层,对任何其它结点,若它父亲 为第k层结点,则它为第(k+1)层结点(层号为k+1) 深度:树中的具有最大层号的结点的层号,称为树的深 度 13
13 •后代：结点x的儿子称x的后代，结点x的儿子的后代也称 x的后代。 •兄弟：同父亲的结点称为兄弟结点。 •堂兄弟：父亲是兄弟关系的结点称为堂兄弟结点。 •层次（层号）：根为第1层，对任何其它结点，若它父亲 为第k层结点，则它为第(k+1)层结点(层号为k+1)。 •深度：树中的具有最大层号的结点的层号，称为树的深 度
§5.1.2基本术语 °结点按层编号(层序编号):将树中结点按从上(层) 到下(层)、同层从左到右的次序排成一个线性序列,依 次给它们编以连续的自然数。 祖辈(上层):层号比结点x小的结点,称为x的祖辈 (上层) 后辈(下层):层号比结点x大的结点,称为x的后辈 (下层) 森林:相互不相交的树的集合称为森林。 同构:若对两棵树,通过适当地重命名其中一棵中的结 点,就可以使两棵树完全相等(结点对应相等,对应结点 的相关关系也对应相等),则称这两棵树同构
14 •结点按层编号（层序编号）：将树中结点按从上（层） 到下（层）、同层从左到右的次序排成一个线性序列，依 次给它们编以连续的自然数。 •祖辈（上层）：层号比结点x小的结点，称为x的祖辈 （上层） •后辈（下层）：层号比结点x大的结点，称为x的后辈 （下层） •森林：相互不相交的树的集合称为森林。 •同构：若对两棵树，通过适当地重命名其中一棵中的结 点，就可以使两棵树完全相等（结点对应相等，对应结点 的相关关系也对应相等），则称这两棵树同构
§5.1.2基本术语 【例53】具有3个结点的不同构的有序树有下 列几种: 图-结点总数为3的不同构的有序树 15
15 • 【例5.3】具有3个结点的不同构的有序树有下 列几种： 图 - 结点总数为3的不同构的有序树