第五章树和二叉树 树形结枸是一种非线性结 构,其特点是:树中有且仅有 个无前驱的结点,其余每个 结点最多只有一个前题,但可 以有多个后继。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 第五章 树和二叉树 树形结构是一种非线性结 构，其特点是：树中有且仅有 一个无前驱的结点，其余每个 结点最多只有一个前驱，但可 以有多个后继
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=(<b>,<,C>,<b,d,<b,e>,<b/,C,g>,<C,h>, <e>,<,> 武工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 二、树的逻辑结构表示 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=(<a,b>,<a,c>,<b,d>,<b,e>,<b,f>,<c,g>,<c,h>, <e,j>,<e,k>,<g,l>）
树根 树叶 图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 表示结点