第6章树型结构 >树的基本概念 >树类的定义 >树的存储结构 >树的遍历 >树的线性表示
第6章 树型结构 ➢树的基本概念 ➢树的遍历 ➢树的线性表示 ➢树类的定义 ➢树的存储结构
61树的基本概念 树是由n(n≥0)个结点构成的有限集合,n=0的 树称为空树;当n≠0时,树中的结点应该满足以下 两个条件 (1)有且仅有一个特定的结点称之为根; (2)其余结点分成m(m≥0)个互不相交的有限集合 T2…mn,其中每一个集合又都是一棵树,称 TT2…Tm为根结点的子树。 B C D) E G 图61 J K
6.1 树的基本概念 树是由n (n≥0)个结点构成的有限集合，n=0的 树称为空树；当n≠0时，树中的结点应该满足以下 两个条件： (1) 有且仅有一个特定的结点称之为根； (2) 其余结点分成m(m≥0)个互不相交的有限集合 T1 , T2 ,……Tm，其中每一个集合又都是一棵树，称 T1 , T2 ,……Tm为根结点的子树。 B D E F G A H I J K C 图6.1
在树中采用线段连接两个相关联的结点,如A和B D和H等。其中A和D是上端结点,B和H是下端结点。 称A、D分别是B、H的双亲(或父母或前件),B和H 分别为A和D的子女(或孩子或后件)。显然,双亲和 子女的关系是相对而言的。图61中,B是A的子女 但又是E和F的双亲。由于E和F的双亲为同一结点,称E 和F互为兄弟。在任何一棵树中,除根结点外,其它任 何一个结点有且仅有一个双亲,有0个或多个子女,且 它的子女恰巧为其子树的根结点。我们将一结点拥有 的子女数称为该结点的度,树中所有结点度的最大值 称为树的度。图6.1中,A的度为3,B的度为2,而C的 度为0,整棵树的度为3。称度为0的结点为终端结点或 叶子结点,称度不为0的结点为非终端结点或分支结点。 显然,A、B、D、H均为分支结点,而E、F、C、G、 J、K、I均为叶子结点
在树中采用线段连接两个相关联的结点，如A和B， D和H等。其中A和D是上端结点，B和H是下端结点。 称A、D分别是B、H的双亲（或父母或前件），B和H 分别为A和D的子女（或孩子或后件）。显然，双亲和 子女的关系是相对而言的。图6.1中，B是A的子女， 但又是E和F的双亲。由于E和F的双亲为同一结点，称E 和F互为兄弟。在任何一棵树中，除根结点外，其它任 何一个结点有且仅有一个双亲，有0个或多个子女，且 它的子女恰巧为其子树的根结点。我们将一结点拥有 的子女数称为该结点的度，树中所有结点度的最大值 称为树的度。图6.1中，A的度为3，B的度为2，而C的 度为0，整棵树的度为3。称度为0的结点为终端结点或 叶子结点，称度不为0的结点为非终端结点或分支结点。 显然，A、B、D、H均为分支结点，而E、F、C、G、 J、K、I均为叶子结点
称树中连接两个结点的线段为树枝。在树中,若 从结点K开始沿着树枝自上而下能到达结点K,则 称从K到K存在一条路径,路径的长度等于所经过 的树核的条数。在图61中,从结点A到结点在 条路径,路径的长度为3;从D到K也存在一条路 径,路径的长度为2。仔细观察不难发现,从树根到 树中任何一个结点均存在一条路径。 将从树根到某一结点K的路径中K前所经过的所 有结点称为K的祖先;反之,以某结点K为根的子 树中的任何一个结点都称为K的子孙。图61中 A、D、H均为和K的祖先,而G、H、I、J和K均为 D的子孙
称树中连接两个结点的线段为树枝。在树中，若 从结点Ki开始沿着树枝自上而下能到达结点Kj，则 称从Ki到Kj存在一条路径，路径的长度等于所经过 的树枝的条数。在图6.1中，从结点A到结点J存在 一条路径，路径的长度为3；从D到K也存在一条路 径，路径的长度为2。仔细观察不难发现，从树根到 树中任何一个结点均存在一条路径。 将从树根到某一结点Ki的路径中Ki前所经过的所 有结点称为Ki的祖先；反之，以某结点Ki为根的子 树中的任何一个结点都称为Ki的子孙。图6.1中， A、D、H均为J和K的祖先，而G、H、I、J和K均为 D的子孙
树中结点的层次:从树根开始定义,根结点为第 层,根的子女结点构成第二层,依次类推,若某 结点K位于第层,则其子女就位于第i+1层。称树 中结点的最大层次数为树的深度或高度。图61中 A结点位于第一层,B、C、D位于第2层,E、F、G H和位于第三层等等,整棵树的高度为4。 若树中任意结点的子树均看成是从左到右有次序 的,不能随意交换,则称该树是有序树;否则称之 为无序树。下图63中的两棵树,若看成是有序树 它们是不等价的;若看成是无序树,两者相等
树中结点的层次：从树根开始定义，根结点为第 一层，根的子女结点构成第二层，依次类推，若某 结点Kj位于第i层，则其子女就位于第i+1层。称树 中结点的最大层次数为树的深度或高度。图6.1中， A结点位于第一层，B、C、D位于第2层，E、F、G、 H和I位于第三层等等，整棵树的高度为4。 若树中任意结点的子树均看成是从左到右有次序 的，不能随意交换，则称该树是有序树；否则称之 为无序树。下图6.3中的两棵树，若看成是有序树， 它们是不等价的；若看成是无序树，两者相等