人民邮政出版社：《数据结构》课程教学资源（PPT课件）第6章 树型结构

第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中的两棵树，若看成是有序树， 它们是不等价的；若看成是无序树，两者相等

(D E 图63有序树和无序树的比较 由m(m≥0)棵互不相交的树构成的集合称为森林。 森林和树的概念十分相近,一棵树中每个结点,其 子树的集合即为一个森林;而在森林中的每棵树之 上加一个共同的根,森林就成为了一棵树

D C E F A B D E F A B 由m (m≥0)棵互不相交的树构成的集合称为森林。 森林和树的概念十分相近，一棵树中每个结点，其 子树的集合即为一个森林；而在森林中的每棵树之 上加一个共同的根，森林就成为了一棵树。 C 图6.3 有序树和无序树的比较

树型结构的其他表示方法: A(B(E,F), C,D(G,HO, K), D) (a)图61的括号表示法 A B G H E K (b)图6.1的嵌套集合表示法

树型结构的其他表示方法： A(B(E,F),C,D(G,H(J,K),I)) (a) 图6.1的括号表示法 B H J K G I E F D C A (b)图6.1的嵌套集合表示法

ELlE F/∠ D[/∠ GH K (O图61的凹入表示法

A B E F C D G H J K I (C)图6.1的凹入表示法

62树类的定义 ADT tree i 数据对象D:具有相同性质的数据元素构成的有限 集 数据关系R:如果D为空或D仅含一个元素,则R为 空;否则D中存在一个特殊的结点root,称 之为根结点,其无前驱;其它结点被分成互 不相交的m(m≥0)个集合,分别构成root的m 棵子树;若这些子树非空,则它们的根结点 root均称为整棵树根结点root的后继结点 而每棵子树也是一棵树,因而它们中数据元 素间的关系也同样满足R的定义。 树的基本操作如下 (1)Inittree(T (2)Cleartree(T

6.2 树类的定义 ADT tree { 数据对象D：具有相同性质的数据元素构成的有限 集合。 数据关系R：如果D为空或D仅含一个元素，则R为 空；否则D中存在一个特殊的结点root，称 之为根结点，其无前驱；其它结点被分成互 不相交的m(m0)个集合，分别构成root的m 棵子树；若这些子树非空，则它们的根结点 rooti均称为整棵树根结点root的后继结点； 而每棵子树也是一棵树，因而它们中数据元 素间的关系也同样满足R的定义。 树的基本操作如下： （1）Inittree(T) （2）Cleartree(T)

(3)Emptytree(T 4)Root(T) (5) Child(t, a (6)Parent(T, a) 7)Degree(T, a (8)Depth(T) 9)Choose(T, c) 10)Addchild (t,a, i, t1) 11)Delchild(t, a, i 12) Createtree(a, F) 13)Equaltree(T1, T2) (14)Numofnode T 15) preorder(T) 16) postorder(T) 17)levelorder(t) 18)Destroytree(T) 1 ADT Tree

（3）Emptytree(T) （4）Root(T) （5）Child(T, a, i) （6）Parent(T, a) （7）Degree(T, a) （8）Depth(T) （9）Choose(T , C) （10）Addchild（T,a, i, t1） （11）Delchild(T,a,i) （12）Createtree(a, F) （13）Equaltree(T1,T2) （14）Numofnode(T) （15）preorder(T) （16）postorder(T) （17）levelorder(T) （18）Destroytree(T) } ADT Tree