数据结构树和二叉树.pptx

第六章树和二叉树

树的有关概念01二叉树02二叉树的遍历03遍历的应用04*线索二叉树（简单介绍）05树和森林06哈夫曼树及应用07第六章树和二叉树第六章树和二叉树

第六章树和二叉树6.1树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作

6.1树的有关概念1．树的定义定义：树是n个结点的有限集合。在任一棵非空树中：

（1）有且仅有一个称为根的结点；。

（2）其余结点可分为m个互不相交的有限集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE树结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。

6.1树的有关概念JIAHG从逻辑结构看：

树中只有根结点没有前趋；

除根外，其余结点都有且仅一个前趋；树的结点，可以有零个或多个后继；

除根外的其他结点，都存在唯一条从根到该结点的路径；树是一种分枝结构BECFD

6.1树的有关概念树的应用

树可表示具有分枝结构关系的对象例1．家族族谱例2．单位行政机构的组织关系、系统功能模块图

012）树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。026.1树的有关概念

MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………

6.1树的有关概念3、树的基本术语1）结点的度：结点所拥有的子树的个数。2）树的度：树中各结点度的最大值。CGBDEFKLHMIJADA=3DB=2DC=1DG=0DTree=3

6.1树的有关概念3）叶子结点：度为0的结点，也称为终端结点。4）分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA叶子结点：{K,L,F,G,M,I,J}分支结点：{A,B,C,D,E,H}

6.1树的有关概念5）孩子、双亲：树中结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；6）兄弟：具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA孩子结点：{B,C,D}双亲结点：{A}兄弟结点：{E，F}

6.1树的有关概念7）路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲，则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA结点序列：{nA,nB,nE,nK}路经长度=3

6.1树的有关概念8）祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。CGBDEFKLHMIJA

6.1树的有关概念9）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。10）树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC

6.1树的有关概念11）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的（即不能互换），称这棵树为有序树；反之，称为无序树。ACBGFEDACBGFED数据结构中讨论的一般都是有序树

6.1树的有关概念12）森林：m(m≥0)棵互不相交的树的集合。CBDEFKLHJA树中每一个结点的子树的集合即为森林。

6.1树的有关概念树结构和线性结构的比较线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多

6.1树的有关概念4、树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）InitTree(T);//构造空树T2）DestroyTree(T);//销毁树T3）CreateTree(T,definition);//按definition构造树T4）ClearTree(T);//将树T清为空树5）TreeEmpty(T);//判断树T是否为空树6