第一章数据结构与算法树的基本术语-----结点的层次和树的深度树中的每个结点都处在一定的层次上结点的层次从树根开始定义，根节点为第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