O树的基本术语 第六章树和三叉树 叶结点( leaf node)或称终端结点, A 系指树中度为0(或没有后件)的结点。 如K,L,G,M,|,J都是叶结点。 ⑥G⑤ 分支结点( branch node)亦称非终端 结点,系指度不为0的结点,包括根结点。 双亲( parent)树中各结点的直接前趋称为该结点的双亲。如 结点A是结点D的双亲,结点H是结点M的双亲等等。 孩子( children)一个树结点的直接后继均是该树结点的孩子 。如结点B,C,D均是结点A的孩子 见弟( Sibling)同一个双亲的孩子之间互称兄弟。如结点E, 互为兄弟,H,,J互为兄弟,等等 祖先( ancestor)从根结点到该结点所经分支上的所有结点。 如结点K的祖先分别为A,B,E。 第11页
第六章 树和二叉树 第11页 叶结点（leaf node）或称终端结点， 系指树中度为0（或没有后件）的结点。 如K，L，G，M，I，J都是叶结点。 双亲（parent）树中各结点的直接前趋称为该结点的双亲。如 结点A是结点D的双亲，结点H是结点M的双亲等等。 祖先（ancestor）从根结点到该结点所经分支上的所有结点。 如结点K的祖先分别为A，B，E。 分支结点（branch node）亦称非终端 结点，系指度不为0的结点，包括根结点。 孩子（children）一个树结点的直接后继均是该树结点的孩子 。如结点B，C，D均是结点A的孩子。 兄弟（Sibling）同一个双亲的孩子之间互称兄弟。如结点E，F 互为兄弟，H，I，J互为兄弟，等等。 ⚫ 树 的 基 本 术 语 A B C D E F H J K L G I M
树的基本术语 第六章树和三叉树 子孙( descendant)以某结点为根的子树中 的任一结点都称为该结点的子孙。比如,除根 结点A之外的所有结点都是A的子孙 (B 堂兄弟( brother -in-aw)其双亲在同一层o更①① 的结点。如结点E,G和H均为堂兄弟 (M 树枝( branch)亦称为树边,系指连接两个结点的有向线段。 一般是由父结点指向子结点。为了画图方便,一般将箭头方向省略 结点的层次( evel of node)结点所位于的层数(以根结点为 第一层)。如结点B的层次为2。树中任一结点的层次等于它的双亲 结点的层次加1。 结点的枝长( length of branch)亦称该结点的路径长度,系指 由根结点至该结点所经过的树枝数,它应等于该结点的层次数减1 。如结点B的枝长为1 树的深度( depth of tree)亦称树的高度,系指树中各结点层 次的最大值。如树A的深度为4 第12页
第六章 树和二叉树 第12页 子孙（descendant）以某结点为根的子树中 的任一结点都称为该结点的子孙。比如，除根 结点A之外的所有结点都是A的子孙 树枝（branch）亦称为树边，系指连接两个结点的有向线段。 一般是由父结点指向子结点。为了画图方便，一般将箭头方向省略 树的深度（depth of tree）亦称树的高度，系指树中各结点层 次的最大值。如树A的深度为4。 堂兄弟（brother-in-law）其双亲在同一层 的结点。如结点E，G和H均为堂兄弟。 结点的层次（level of node）结点所位于的层数（以根结点为 第一层）。如结点B的层次为2。树中任一结点的层次等于它的双亲 结点的层次加1。 结点的枝长（length of branch）亦称该结点的路径长度，系指 由根结点至该结点所经过的树枝数，它应等于该结点的层次数减1 。如结点B的枝长为1。 ⚫ 树 的 基 本 术 语 A B C D E F H J K L G I M
树的葚本术语 第六章树和三叉树 有序树( ordered tree)规定了树中所有结点的每一棵子树或 后件的次序(从左至右,且不能互换)的树。比如,以下两棵树是 互不相同的有序树。 C CB 无序树( unorded tree)凡不是有序树的树 完全树( Complete tree)亦称正则树,系指在n阶树中,它的 每一个结点,要末有n个后件,要末一个后件也没有。比如,下列 三棵树 (a) (b) 中,(a)、(b)均为完全树,而(c)则不是完全树。 第13页
第六章 树和二叉树 第13页 有序树（ordered tree）规定了树中所有结点的每一棵子树或 后件的次序（从左至右，且不能互换）的树。比如，以下两棵树是 互不相同的有序树。 完全树（Complete tree）亦称正则树，系指在n阶树中，它的 每一个结点，要末有n个后件，要末一个后件也没有。比如，下列 三棵树 无序树（unorded tree）凡不是有序树的树。 A B C A C B 中，(a),(b)均为完全树，而(c)则不是完全树。 (a) (b) (c) ⚫ 树 的 基 本 术 语
树的基本术语 第六章树和三叉树 一定义3mm≥0)棵互不相交树的集合称 为森林。森林与树的概念非常相近,比如⑥@⊙ 将范例树中的根结点A删去,该树就分自0的① 解成由原树的三棵子树B,C,D组成 的森林。反之,可以用一个新的树根 结点将若干棵互不相交的树(即森林)组合成一棵新树。 一定义4任何一棵树是一个二元组Tree=(root,F),其中 root是数据元素,称做树的根结点;F是m(m≥0)棵树的森 林,F=(T1,T2,…,Tm),其中T=(,F称做树根root的第i 棵子树;当m时,在树根和其子树森林之间存在下列关 系 RT=<<root, ri>1sism, m>Of 此定义有助于得到森林和树与二叉树之间转换的递归 定义。 第14页
第六章 树和二叉树 第14页 定义3 m(m ≥0)棵互不相交树的集合称 为森林。森林与树的概念非常相近，比如 将范例树中的根结点A删去，该树就分 解成由原树的三棵子树B，C，D组成 的森林。反之，可以用一个新的树根 结点将若干棵互不相交的树(即森林)组合成一棵新树。 定义4 任何一棵树是一个二元组Tree=(root,F)，其中 root是数据元素，称做树的根结点；F是m(m≥0)棵树的森 林，F=(T1 ,T2 ,…，Tm)，其中Ti=(ri,Fi)称做树根root的第i 棵子树；当m≠0时，在树根和其子树森林之间存在下列关 系 RT={<root,ri>|1≤i≤m,m>0} 此定义有助于得到森林和树与二叉树之间转换的递归 定义。 ⚫ 树 的 基 本 术 语 A B C D E F H J K L G I M
0树的基本操作 第六章树和三叉树 (1)初始化操作 Initiate(① 置T为空树。 ②)要求根结点函数Roo(T或Ro(x 返回树T的根结点或结点x所在的树的根结点。若T是空树或x 不在任何一棵树上,则返回空函数值NULL (3)求双亲结点函数 Parente(Tx) 返回树T中的根结点或结点x不在树T中,则返回空函数值 NULL (4求孩子结点函数 Child(①x 返回树T结点x的第个孩子结点。若结点x是树T中的叶结点 或无第i个孩子结点,或者结点ⅹ不在树T中,则返回空函数值NULL (5)求右兄弟结点函数 Right Sibling(T,x) 返回树T中结点x右边的兄弟结点。若结点x是其双亲的最右边 的孩子结点或结点x不在树T中,则返回空函数值NULL。 第15页
第六章 树和二叉树 第15页 (1) 初始化操作Initiate(T) 置T为空树。 (2)要求根结点函数Root(T)或Root(x) 返回树T的根结点或结点x所在的树的根结点。若T是空树或x 不在任何一棵树上，则返回空函数值NULL。 (3)求双亲结点函数Parent(T,x) 返回树T中的根结点或结点x不在树T中，则返回空函数值 NULL。 (4)求孩子结点函数Child(T,x,i) 返回树T中结点x的第i个孩子结点。若结点x是树T中的叶结点 或无第i个孩子结点，或者结点x不在树T中，则返回空函数值NULL。 (5)求右兄弟结点函数 Right_Sibling (T,x) 返回树T中结点x右边的兄弟结点。若结点x是其双亲的最右边 的孩子结点或结点x不在树T中，则返回空函数值NULL。 ⚫ 树 的 基 本 操 作