第五章树和二叉树 树形结枸是一种非线性结 构,其特点是:树中有且仅有 个无前驱的结点,其余每个 结点最多只有一个前题,但可 以有多个后继。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 第五章 树和二叉树 树形结构是一种非线性结 构，其特点是：树中有且仅有 一个无前驱的结点，其余每个 结点最多只有一个前驱，但可 以有多个后继
51树的概念 N心 树的定义 1.用形式定义方法定义 2数据结构B=(KR称为树是指:K为结点的非空有限集 合,R是满足下列条件的K上的一个关系: (1)有且仅有一个结点无前驱,被称为树根; (2)除树根以外的其余结点,都有且仅有一个前驱 2.用递归方法定义 ●树是结点的非空有限集合T,其中,有一个无前驱被 m(m> 0)个互不 相交的子集T1,T2Tmn,每一个子集又都是一棵树, 并称为树根的子树 武汉理工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 5.1 树的概念 一、树的定义 1.用形式定义方法定义 数据结构B=(K,R)称为树是指：K为结点的非空有限集 合，R是满足下列条件的K上的一个关系： （1）有且仅有一个结点无前驱，被称为树根； （2）除树根以外的其余结点，都有且仅有一个前驱。 2.用递归方法定义 树是结点的非空有限集合T，其中，有一个无前驱被 称为树根的结点，其余结点被分成m（m>=0）个互不 相交的子集T1, , T2 , ….Tm，每一个子集又都是一棵树， 并称为树根的子树
二、树的逻辑结构表示 →1.树的逻辑结构一般采用图示法。根在上子树在下用小 园圈表示结点用称为边的直线段表示结点之间的关系 如图5-1所示其中结点a为树根,它有两棵子树b和c 且b和C又是一棵树。 2.树的逻辑结构的二元组表示 按照树的形式定义方法描述为 tree=(D,R) D=(a,b,c,d,e,f,g,h,,,l) R=(,,,,, , 武工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 二、树的逻辑结构表示 1. 树的逻辑结构一般采用图示法。根在上,子树在下,用小 圆圈表示结点,用称为边的直线段表示结点之间的关系。 如图5－1所示.其中结点a为树根，它有两棵子树b和c 且b和c又是一棵树。 2. 树的逻辑结构的二元组表示 按照树的形式定义方法描述为： tree＝（D,R） D=（a ，b，c，d，e，f，g，h，j，k，l） R=(,,,,,,, ,,）
树根 树叶 图51树的逻辑结构表示 武汉理工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 图5-1 树的逻辑结构表示 a b c d e g j l f h k 树根 树叶
3.树的逻辑结构其它表示法。 (1)文氏图表示法 (2)广义表表示 A(B(EFU,K,G,CD(,I) 表示根 F 表示结点
武汉理工大学华夏学院-信息工程 系 3. 树的逻辑结构其它表示法。 （1) 文氏图表示法 (2)广义表表示 A(B(E,F(J,K),G),C,D(H,I)) H I J K E G C B A D 表示根 F 表示结点
(3)凹入式表示法 B E K D H 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （3) 凹入式表示法 A B E F J K G C D H I
三、树中常用术语 <心 1.双亲与孩子设X与Y为树中的两个结点,若X 是Y的前驱,则称X是Y的双亲,Y是X的孩子。 二2.兄弟与堂兄弟树中的两个结点X与Y存在有 共同的双亲,称X与Y为兄弟,若其双亲为兄弟, 则称为堂兄弟 ≥3.分支结点和终端结点有后继结点的结点称为 分支结点;没有后继结点的结点称为终端结点 或树叶。 4.结点的度结点的后继结点的个数称为该结点 的度显然度为零的结点一定是树叶。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 1. 双亲与孩子设X与Y为树中的两个结点，若X 是Y的前驱，则称X是Y的双亲，Y是X的孩子。 2. 兄弟与堂兄弟树中的两个结点X 与Y存在有 共同的双亲，称X与Y为兄弟，若其双亲为兄弟， 则称为堂兄弟 3. 分支结点和终端结点 有后继结点的结点称为 分支结点；没有后继结点的结点称为终端结点 或树叶。 4. 结点的度结点的后继结点的个数,称为该结点 的度,显然,度为零的结点一定是树叶。 三、树中常用术语
5.树的度树中结点度的最大值称为树的度。 例如:图5-1树的度为3,因为该树中,有度为一的结点、 也有度为二、度为零与度为三的结点,其度的最大值为 三。若一棵树的度为n时,则称该树为n度树。 6.结点的层又称为结点的层次高度,它是从树根开始定 义的:即根结点属于第一层,其余结点的层次高度等于 其双亲的层次+1。 7.树的层次高度树的层次高度等于树中结点的层次的 最大值。(也称为树的深度) 8.森林n(n>=0)棵互不相交的树的集合。注意 当n=0时说明森林中无结点,即森林可以为空。(树不 能为空) 9有序树和无序树:若树中结点从左到右是有序的,则 称该树为有序树,反之为无序树工程
武汉理工大学华夏学院-信息工程 系 5.树的度 树中结点度的最大值,称为树的度。 例如：图5-1树的度为3, 因为该树中，有度为一的结点、 也有度为二、度为零与 度为三的结点，其度的最大值为 三。若一棵树的度为n时，则称该树为n度树。 6. 结点的层 又称为结点的层次高度，它是从树根开始定 义的：即根结点属于第一层，其余结点的层次高度等于 其双亲的层次＋1。 7. 树的层次高度 树的层次高度等于树中结点的层次的 最大值。（也称为树的深度） 8. 森林 n（ n>=0 ）棵互不相交的树的集合。注意： 当n＝0时说明森林中无结点，即森林可以为空。（树不 能为空） 9.有序树和无序树：若树中结点从左到右是有序的，则 称该树为有序树，反之为无序树
四、树的存储结构 当一棵树的逻辑结构确定以后,就应该考虑如何存放 在计算机中,存储一棵树时,不仅要存储树中每个结点 ●的值,而且要存储各结点之间的关系,一般可以用三种 方法实现 1,双亲数组表示方法:用一个一维数组存储树中的结点 数组元素是一个结构体,该结构体中包含两个字段:其 为data字段,用来存放结点的值;其二为 parent字段 用来存储该结点的双亲结点(即该结点的前驱结点)在 数组中的下标地址 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 1.双亲数组表示 方法：用一个一维数组存储树中的结点， 数组元素是一个结构体，该结构体中包含两个字段：其 一为data字段，用来存放结点的值；其二为parent字段, 用来存储该结点的双亲结点（即该结点的前驱结点）在 数组中的下标地址。 四、 树的存储结构 当一棵树的逻辑结构确定以后, 就应该考虑如何存放 在计算机中，存储一棵树时，不仅要存储树中每个结点 的值，而且要存储各结点之间的关系，一般可以用三种 方法实现：
例如:以图5-1所示的三度树为例,存储该树 的双亲数组表示,如图5-2所示。 「23451678910m moa abcd efghiilk rram022“2到3 图5-2图41树的双亲数组存储表示 存储特点:可以根据每一个结点本身的内容直 接读取其双亲结点的地址,但查找孩子结点较 困难。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 例如： 以图5-1所示的三度树为例，存储该树 的双亲数组表示， 如图5-2所示。 1 图5-2 图4-1树的双亲数组存储表示 data 2 parent root 1 3 4 5 6 7 8 9 a b c d e f g h i 0 1 1 2 2 2 3 3 7 10 11 j k 5 5 存储特点：可以根据每一个结点本身的内容直 接读取其双亲结点的地址，但查找孩子结点较 困难