河南中医药大学：《数据结构与算法》课程PPT教学课件（C#语言描述）第6章 树和二叉树

第6章树和二叉树 6.1树 61.1树的定义 树是由n(心0)个结点组成的有限集合(记为T)。如 果n=0,它是一棵空树,这是树的特例;如果灬>0,这n个结 点中存在(有仅存在)一个结点作为树的根结点(root), 其余结点可分为m(m0)个互不相交的有限集T、T2…、 Tm,其中每个子集本身又是一棵符合本定义的树,称为根 结点的子树

第6章 树和二叉树 6.1 树 6.1.1 树的定义 树是由n（n≥0）个结点组成的有限集合（记为T）。如 果n=0，它是一棵空树，这是树的特例；如果n>0，这n个结 点中存在（有仅存在）一个结点作为树的根结点（root）， 其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、 Tm，其中每个子集本身又是一棵符合本定义的树，称为根 结点的子树

树是一种非线性数据结构,具有以下特点 它的每一结点可以有零个或多个后继结点,但有且只有 个前驱结点(根结点除外);这些数据结点按分支关系组 织起来,清晰地反映了数据元素之间的层次关系。可以看出, 数据元素之间存在的关系是一对多的关系

树是一种非线性数据结构，具有以下特点： 它的每一结点可以有零个或多个后继结点，但有且只有 一个前驱结点（根结点除外）；这些数据结点按分支关系组 织起来，清晰地反映了数据元素之间的层次关系。可以看出， 数据元素之间存在的关系是一对多的关系

抽象数据类型树的定义如下: ADT Tree 数据对象: D={a11si≤n,n≥0,a为 Elemtype类型} /假设 ElemType为 string 数据关系: R={r} r={|a1a;∈D,1≤i,j≤n,其中每个结点最多只有一个前驱结点、 可以有零个或多个后继结点,有且仅有一个结点即根结点没有前驱结点} 基本运算: bool CreateTreeo:由树的逻辑结构表示建立其存储结构。 string DispTreeo:输出树。 string GetParent(inti):求编号为的结点的双亲结点 string getsons(inti):求编号为的结点的所有孩子结点

抽象数据类型树的定义如下： ADT Tree { 数据对象： D={ai | 1≤i≤n,n≥0,ai为ElemType类型} //假设ElemType为string 数据关系： R={r} r={ | ai ,aj∈D, 1≤i，j≤n，其中每个结点最多只有一个前驱结点、 可以有零个或多个后继结点，有且仅有一个结点即根结点没有前驱结点} 基本运算： bool CreateTree()：由树的逻辑结构表示建立其存储结构。 string DispTree()：输出树。 string GetParent(int i)：求编号为i的结点的双亲结点。 string GetSons(int i)：求编号为i的结点的所有孩子结点。 … }

6.12树的逻辑结构表示方法 D B IK K (a)树形表示法 (b)文氏图表示法

6.1.2 树的逻辑结构表示方法 A C G J B E D F H I K L M H L D I K M C G J E B F （a）树形表示法 （b）文氏图表示法 A

F G J D A(B(E,F, C(G(), D(H, IK, L, MD) H K M (c)凹入表示法 (d)括号表示法

F C A B D E G J H I K L M （c） 凹入表示法 （d）括号表示法 A(B(E,F),C(G(J)),D(H,I(K,L,M)))

6.1.3树的基本术语 度为3 1.结点的度与树的度:树中某 度为2 个结点的子树的个数称为该结点的 度。树中各结点的度的最大值称为@④ 树的度,通常将度为m的树称为m 次树。 2.分支结点与叶结点:度不为零的结点称为非终端结点, 又叫分支结点。度为零的结点称为终端结点或叶结点。在分 支结点中,每个结点的分支数就是该结点的度。如对于度为 1的结点其分支数为1,被称为单分支结点;对于度为2的结 点,其分支数为2,被称为双分支结点,其余类推

6.1.3 树的基本术语 1. 结点的度与树的度：树中某 个结点的子树的个数称为该结点的 度。树中各结点的度的最大值称为 树的度，通常将度为m的树称为m 次树。 2. 分支结点与叶结点：度不为零的结点称为非终端结点, 又叫分支结点。度为零的结点称为终端结点或叶结点。在分 支结点中，每个结点的分支数就是该结点的度。如对于度为 1的结点,其分支数为1，被称为单分支结点；对于度为2的结 点，其分支数为2，被称为双分支结点，其余类推。 A B C D E F G J H I K L M 度为3 度为2

3.路径与路径长度:对于任意 两个结点4和4,着树中存在一个结 点序列d,dl1,d2…,dnd,使得序列中 除d外的任一结点都是其在序列中的 前一个结点的后继,则称该结点序 列为由到的一条路径,用路径所画 通过的结点序列(ddh,1,…,4表示 这条路径。 路径长度等于路径所通过的结点 A到K的路径为A,D,L,K 其长度为3 数目减1(即路径上分支数目)

3. 路径与路径长度：对于任意 两个结点di和dj，若树中存在一个结 点序列di ,di1 ,di2 ,…,din,dj，使得序列中 除di外的任一结点都是其在序列中的 前一个结点的后继，则称该结点序 列为由di到dj的一条路径，用路径所 通过的结点序列(di ,di1 ,di2 ,…,dj )表示 这条路径。 路径长度等于路径所通过的结点 数目减1（即路径上分支数目）。 A B C D E F G J H I K L M A到K的路径为A,D,I,K， 其长度为3

4.孩子结点、双亲结点和兄弟结点: 在一棵树中,每个结点的后继,被称 作该结点的孩子结点(或子女结点)。 相应地,该结点被称作孩子结点的双◎ 亲结点(或父母结点)。 具有同一双亲的孩子结点互为兄弟 结点。进一步推广这些关系,可以把 每个结点的所有子树中的结点称为该 结点的子孙结点。 从树根结点到达该结点的路径上经 过的所有结点被称作该结点的祖先结

4. 孩子结点、双亲结点和兄弟结点： 在一棵树中，每个结点的后继，被称 作该结点的孩子结点（或子女结点）。 相应地，该结点被称作孩子结点的双 亲结点（或父母结点）。 具有同一双亲的孩子结点互为兄弟 结点。进一步推广这些关系，可以把 每个结点的所有子树中的结点称为该 结点的子孙结点。 从树根结点到达该结点的路径上经 过的所有结点被称作该结点的祖先结 点。 A B C D E F G J H I K L M

5.结点的层次和树的高度:树 中的每个结点都处在一定的层次上。 结点的层次从树根开始定义,根结 点为第1层,它的孩子结点为第2层, 以此类推,一个结点所在的层次为其 双亲结点所在的层次加1。树中结 点的最大层次称为树的高度(或树@画 3 的深度)。 ③③◎4 6.有序树和无序树:若树中各 结点的子树是按照一定的次序从左 向右安排的,且相对次序是不能随 意变换的,则称为有序树,否则称 为无序树

5 . 结点的层次和树的高度： 树 中的每个结点都处在一定的层次上 。 结点的层次从树根开始定义 ，根结 点为第 1 层 ，它的孩子结点为第 2 层 , 以此类推 ,一个结点所在的层次为其 双亲结点所在的层次加 1 。树中结 点的最大层次称为树的高度 （或树 的深度 ） 。 6 . 有序树和无序树：若树中各 结点的子树是按照一定的次序从左 向右安排的 ，且相对次序是不能随 意变换的 ，则称为有序树 ，否则称 为无序树 。 A B C D E F GJ H I K L M 1 2 3 4

7.森林:n(n>0)个互不相交的树的集合称为森林。 森林的概念与树的概念十分相近,因为只要把树的根结 点删去就成了森林。反之,只要给n棵独立的树加上 个结点,并把这n棵树作为该结点的子树,则森林就变 成了树

7. 森林：n（n＞0）个互不相交的树的集合称为森林。 森林的概念与树的概念十分相近，因为只要把树的根结 点删去就成了森林。反之，只要给n棵独立的树加上一 个结点，并把这n棵树作为该结点的子树，则森林就变 成了树