2.二叉树的相关概念 中(1)结点的度。结点所拥有的子树的个数称为该结点 的度。 (2)叶结点。度为0的结点称为叶结点,或者称为终端 结点 (3)分枝结点。度不为0的结点称为分支结点,或者称 为非终端结点。一棵树的结点除叶结点外,其余的都是分 支结点 (4)左孩子、右孩子、双亲、兄弟。树中一个结点的 子树的根结点称为这个结点的孩子。在二叉树中,左子树 的根称为左孩子,右子树的根称为右孩子。这个结点称为 它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄 弟 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 2．二叉树的相关概念 (1）结点的度。结点所拥有的子树的个数称为该结点 的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端 结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称 为非终端结点。一棵树的结点除叶结点外，其余的都是分 支结点。 （4）左孩子、右孩子、双亲、兄弟。树中一个结点的 子树的根结点称为这个结点的孩子。在二叉树中，左子树 的根称为左孩子，右子树的根称为右孩子。这个结点称为 它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄 弟
(5)路径、路径长度。如果一棵树的一串结点 n1n2…n有如下关系:结点n是n+1的父结点(1≤ik), 就把n,n2,n称为一条由n至n的路径。这条路径的长 度是k-1 (6)祖先、子孙。在树中,如果有一条路径从结点M 到结点N,那么M就称为N的祖先,而N称为M的子孙。 (7)结点的层数。规定树的根结点的层数为1,其余 结点的层数等于它的双亲结点的层数加1。 (8)树的深度。树中所有结点的最大层数称为树的深 度 (9)树的度。树中各结点度的最大值称为该树的度。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 （ 5 ） 路 径 、 路 径长 度 。 如 果 一棵 树 的 一 串 结 点 n1 ,n2 ,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）, 就把n1 ,n2 ,…,nk称为一条由n1至nk的路径。这条路径的长 度是k-1。 （6）祖先、子孙。在树中，如果有一条路径从结点M 到结点N，那么M就称为N的祖先，而N称为M的子孙。 （7）结点的层数。规定树的根结点的层数为1，其余 结点的层数等于它的双亲结点的层数加1。 （8）树的深度。树中所有结点的最大层数称为树的深 度。 （9）树的度。树中各结点度的最大值称为该树的度
(10)满一叉权 在一棵二叉树中,如果所有分支结点都存在左子树 和右子树,并且所有叶子结点都在同一层上,这样的 棵二叉树称作满二叉树。如图所示,(a)图就是 棵满二叉树,(b)图则不是满二叉树,因为,虽然其 所有结点要么是含有左右子树的分支结点,要么是叶 子结点,但由于其叶子未在同一层上,故不是满二叉 树。 B c 5 6@7 D4@506⊙7 B60000 891011 12131415 (a)一棵满二叉树 (b)一棵非满二又树 满二叉树和非满二叉树示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 （10）满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树 和右子树，并且所有叶子结点都在同一层上，这样的 一棵二叉树称作满二叉树。如图所示，（a）图就是一 棵满二叉树，（b）图则不是满二叉树，因为，虽然其 所有结点要么是含有左右子树的分支结点，要么是叶 子结点，但由于其叶子未在同一层上，故不是满二叉 树
(11)完全二叉树。 棵深度为k的有n个结点的二叉树,对树中的结点按从 止上至下、从左到右的顺序进行编号,如果编号为i( ≤i≤n)的结点与满二叉树中编号为的结点在二叉树中 的位置相同,则这棵二叉树称为完全二叉树。完全二叉树 的特点是:叶子结点只能出现在最下层和次下层,且最下 层的叶子结点集中在树的左部。显然,一棵满二叉树必定 是一棵完全二叉树,而完全二叉树未必是满二叉树。如图 所示(a)为一棵完全二叉树,(b)不是完全二叉树 (a)一棵完全二叉树 b)一棵非完全二叉树 完全二又树和非完全二叉树示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 (11) 完全二叉树。 一棵深度为k的有n个结点的二叉树，对树中的结点按从 上至下、从左到右的顺序进行编号 ，如果编号为i（ 1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中 的位置相同，则这棵二叉树称为完全二叉树。完全二叉树 的特点是：叶子结点只能出现在最下层和次下层，且最下 层的叶子结点集中在树的左部。显然，一棵满二叉树必定 是一棵完全二叉树，而完全二叉树未必是满二叉树。如图 所示（a）为一棵完全二叉树，（b）不是完全二叉树
6.1.2二叉树的主要性质 ◆性质1一棵非空二叉树的第层上最多有21个结点 (i≥1)。 该性质可由数学归纳法证明。证明略。 ◆性质2一棵深度为k的二叉树中,最多具有2k-1个结 点。 证明设第层的结点数为X(1≤i≤k),深度为k的二 叉树的结点数为M,X最多为21,则有: M=∑x221=2-1 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 6.1.2 二叉树的主要性质 性质1 一棵非空二叉树的第i层上最多有2 i-1个结点 （i≥1）。 该性质可由数学归纳法证明。证明略。 性质2 一棵深度为k的二叉树中，最多具有2 k－1个结 点。 证明 设第i层的结点数为xi（1≤i≤k），深度为k的二 叉树的结点数为M，xi最多为2 i-1 ，则有：