数据结构与算法设计（第二版）课件 6章 树与二叉树.pptx

第六章树与二叉树西安科技大学计算机学院张小艳数据结构与算法设计

族谱就是一个家族所有人员构成的大名单，是一个用血缘联系起来的系统。通过绘制家谱树，记录家族成员的相互关系。家谱树，是一种描绘家庭关系的树状结构图，树中的每个成员可以清楚的知道自己的家族起源、家族关系以及其他成员的基础信息。通过家谱，可使子孙后辈知悉祖先的渊源、人口、迁徙、分布、名人传略、故事传说、先贤史迹等等。通过家谱，可激励子孙后辈传承家族美德，发扬优良传统，赓续家族源流。要记得自己来自于哪里？根在哪里？爱父母、爱自己的家，热爱我们的大家-中国，我们拥有一个强大的国家，无论走到哪里，我们的根永远在中国。引例家谱族谱系统

把每一个成员都视为系统的一个要素，他们按照“祖—父—子—孙”的关系构成了树状结构。引例家谱族谱系统

引例组织架构

在树中，我们把数据元素称之为结点数据元素的关系层次分明，A第一层、BCD在的二层、EFGHIJ在第三层、KLM在第四层。树及二叉树--基本概念T3第一层第二层第三层第四层根结点结点A为树T的根结点，除根结点A之外的其余结点分为三个不相交的集合：T1T2抽象透过现象看本质

类似于线性表，我们把树定义为一个二元组：Tree=（D,R）其中：D是具有相同特性的数据元素的集合；R是关系集合。如果D=NULL,称这棵树为空树；如果D只包含一个数据元素，则R为空集；树及二叉树--基本概念否则：关系描述R定义为：(1)在D中存在唯一的一个特殊的元素称为树的根结点root，根结点root没有前驱结点。(2)若D-{root}！=NULL，D-{root}=D1∪D2∪…∪Dm，D1∩D2∩…∩Dm=∮对于任意一个Di,ti∈Di,root,ti∈R，root就有m个直接后继。(3)对应集合D1，D2，…，Dm，有R1,R2,…，Rm个关系，其中每一组二元组Ti=（Di,Ri）又是一棵满足上述定义的树。树T1，T2，…，Tm称为这个根结点root的子树。透过现象看本质

森林:是零棵或多棵树组成的集合。树也可定义为：n(n≥0)个结点的有限集，若n=0，则为空树；否则，树由一个根结点和m(m≥0)棵树组成的森林构成。森林中的每棵树都是根的子树。树及二叉树--基本概念具有下面两个特点：(1)树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。(2)树中所有结点可以有零个或多个后继结点。

树及二叉树--基本概念1）关于结点的概念根结点B、C、D是A的儿子结点A是B、C、D的双亲结点B、C、D互为兄弟B有两个儿子EFF是叶子结点度不为零的结点称为分支结点F和G之间是堂兄弟关系结点A的度就是三拥有子树的个数就是该结点的度。树中各个结点度的最大值称为这棵树的度度为0的结点称为叶结点度不为0的结点称为分支结点，或者称为非终端结点，A,B,C,DE,H是分支结点

2）结点的层数及树的深度树及二叉树--基本概念结点在树中的层数约定为：树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。若某个结点的层次为k，则其孩子结点的层次为k+1。树中叶结点的最大层次数定义为树的深度。如果一棵树的一串结点n1,n2,…,nk，如果结点ni是ni+1的双亲结点(1≤i＜k)，就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。树分：有序树和无序树。如果一棵树中结点的各子树从左到右是有次序的，这棵树就是有序树；反之，则称为无序树。

结点的层数及树的深度结点在树中的层数约定为：树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。树中叶结点的最大层次数定义为树的深度。如果一棵树的一串结点n1,n2,…,nk，如果结点ni是ni+1的双亲结点(1≤i＜k)，就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。KBCDEFGHIJALM