《大学计算机基础》课程教学资源（二级考试培训资料）第一章 数据结构与算法 1.6、树与二叉树 1.7、查找技术 1.8、排序技术

第一章数据结构与算法1.6、数与二叉树树的基本概念树（tree）是一种非线性结构。在树这种数据结构中，所有数据图表示了一棵一般的树元素之间的关系具有明显的层次特点。香成盛高朝家族网大瑞现实世界中酒次1二欢四中印胡西五世武山八山民山武山元三次久t孔91皮进六世多舞绒航自音长囍板有文欢民健中总武玻政成5教技-H门大廣庆廣底廣廣廣廣鹿廣廣康庆庆廣大参北银湾

树的基本概念 树（tree）是一种非线性结构。在树这种数据结构中，所有数据 元素之 间的关系具有明显的层次特点。图 表示了一棵一般的树。 第一章 数据结构与算法 1.6、数与二叉树 现实世界中：

第一章数据结构与算法H--

第一章 数据结构与算法

第一章数据结构与算法HM

第一章 数据结构与算法

第一章数据结构与算法树的基本术语父结点：在树结构中，每一个结点只有一个前件，没有前件的结点只有一个称为根结点（简称根）子结点：每一个结点可以有多个后件结点，称为该结点的子结点，没有后件“叶子结点”结点的结点称之为根结点：A子结点：BCDEFGHIG叶子结点：EFGHI

父结点：在树结构中，每一个结点只有一个前件，没有前件的结点只有一个 ，称为根结点（简称根）。 第一章 数据结构与算法 树的基本术语 子结点：每一个结点可以有多个后件结点，称为该结点的子结点，没有后件 结点的结点称之为“叶子结点”。 根结点：A 子结点：BCDEFGHI 叶子结点：EFGHI

第一章数据结构与算法树的基本术语树中某个结点的后件的个数称为该节点的度树中所有结点的最大的度为树的度以某结点的一个子结点为根构成的树称为该结点的一棵子树G

第一章 数据结构与算法 树的基本术语 树中某个结点的后件的个数称为该节点的度 树中所有结点的最大的度为树的度 以某结点的一个子结点为根构成的树称为该结点的一棵 子树

第一章数据结构与算法树的基本术语-----结点的层次和树的深度树中的每个结点都处在一定的层次上结点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层，以此类推树中结点的最大层次称为树的深度23H4K深度为4的树

第一章 数据结构与算法 树的基本术语-结点的层次和树的深度 树中的每个结点都处在一定的层次上， 结点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层,以此类推 树中结点的最大层次称为树的深度

第一章数据结构与算法1.6、数与二叉树2.二叉树的基本概念是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成五种基本形态②只含根①空树③只舍左子树④只含右子树③含左右子树

2．二叉树的基本概念 第一章 数据结构与算法 1.6、数与二叉树 是一个有限的结点集合， 该集合或者为空， 或者由一个根结点及其两棵互不相交 的左、 右二叉子树所组成 五种基本形态

第一章数据结构与算法1.6、树与二叉树2.二叉树具有以下两个特点①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。注意A的左子树和右子树

① 非空二叉树只有一个根结点； ② 每一个结点最多有两棵子树，且分别称为该结点的左 子树与右子树。注意A的左子树和右子树。 2．二叉树具有以下两个特点 第一章 数据结构与算法 1.6、树与二叉树

第一章数据结构与算法1.6、 树与二叉树3.二叉树基本性质性质1在二叉树中，第i层的结点数最多为2i-1个（i≥1）性质2在深度为m的二叉树中，结点总数最多为2m-1个（k≥1）。设每层结点达到最大结点数，则总结点数第1层：21-1=1第2层：1+22-1=1+2=3=22-1个第3层：1+22-1+23-1=7=23-1个第4层：1+22-1+23-1+24-1=15=24-1个第m层：1+22-1+23-14-12m-1=2m1个

性质1 在二叉树中，第i层的结点数最多为2 i-1个（i≥1）。 性质2 在深度为m的二叉树中，结点总数最多为2m-1个（k≥1）。 3．二叉树基本性质 第一章 数据结构与算法 1.6、树与二叉树 第1层：2 1-1=1 第2层：1+22-1=1+2=3=22 -1个 第3层：1+22-1+23-1=7=23 -1个 第4层：1+22-1+23-1+24-1=15=24 -1个 设每层结点达到最大结点数,则总结点数： 第m层：1+22-1+23-1+24-1+.+2m-1=2m-1个

第一章数据结构与算法1.6、树与二叉树3.二叉树基本性质性质3在任意一个二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一n---总的结点数no---叶子结点的个数n1---度为1的结点的个数n=no+n1+n2no=n2+1n2---度为2的结点的个数设所有进入分支总数为mn=m+1因除根外，每个结点有且只有一个分支进入n=n+2n2+1因m个进入分支由非叶子结点射出m=n度为1的结点射出1个分支度为2的结点射出2个分支

性质3 在任意一个二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个 3．二叉树基本性质 第一章 数据结构与算法 1.6、树与二叉树 n-总的结点数 n0 -叶子结点的个数 n1 -度为1的结点的个数 n2 -度为2的结点的个数 n=n0+n1+n2 设所有进入分支总数为m 因除根外，每个结点有且只有一个分支进入 n=m+1 因m个进入分支由非叶子结点射出 度为1的结点射出1个分支 度为2的结点射出2个分支 m=n1+2n2 n=n1+2n2+1 n0=n2+1