North China Electric Power University I 二叉树的基本形态: 空)巷想想 树 右子树 左子树 树 具有三个结点的二叉树具有以下五种基本形态
North China Electric Power University 二叉树的基本形态： (空) 根 根 左 子 树 根 右 子 树 根 左 子 树 右 子 树 具有三个结点的二叉树具有以下五种基本形态：
North China Electric Power University I 两种特殊形态的二叉树 1.满二叉树 若一棵二叉树中的结点 或者为叶结点,或者具有两 Q 棵非空子树并且叶结点都集 中在二叉树的最下面一层这 样的二叉树为满二叉树 2完全二叉树 若一棵二叉树中只有最下 面两层的结点的度可以小于2 并且最下面一层的结点(叶结 点)都依次排列在该层从左至 右的位置上。这样的二叉树为 ○○○ 完全二叉树
North China Electric Power University 两种特殊形态的二叉树 若一棵二叉树中的结点, 或者为叶结点， 或者具有两 棵非空子树,并且叶结点都集 中在二叉树的最下面一层.这 样的二叉树为满二叉树. 1. 满二叉树 若一棵二叉树中只有最下 面两层的结点的度可以小于2, 并且最下面一层的结点(叶结 点)都依次排列在该层从左至 右的位置上。这样的二叉树为 完全二叉树. 2.完全二叉树
North China Electric Power University I 二叉树的性质 1一棵非空二叉树的第层最多有2个结点(≥1) 证明采用归纳法) (1).当i=1时结论显然正确。非空二叉树的第1层有且 仅有一个结点即树的根结点 (2)假设对于第层(1i1)结论也正确即第层最多 有2个结点 (3)由定义可知二叉树中每个结点最多只能有两个 孩子结点。若第i-1层的每个结点都有两棵非空子 树则第层的结点数目达到最大而第i1层最多 有2个结点已由假设证明于是应有 证毕 2×212=2i
North China Electric Power University 1. 一棵非空二叉树的第i 层最多有2 i–1个结点(i1)。 证明(采用归纳法) (1).当i=1时,结论显然正确。非空二叉树的第1层有且 仅有一个结点,即树的根结点. (2).假设对于第j层(1ji–1)结论也正确,即第j层最多 有2 j-1个结点. (3).由定义可知, 二叉树中每个结点最多只能有两个 孩子结点。若第i–1层的每个结点都有两棵非空子 树,则第i层的结点数目达到最大. 而第i–1层最多 有2 i–2个结点已由假设证明,于是,应有 22 i–2 = 2i–1 证毕. 二叉树的性质
North China Electric Power University I 2深度为h的非空二叉树最多有2-1个结点 证明 由性质1可知若深度为h的二又树的每一层的结点数 目都达到各自所在层的最大值则二叉树的结点总数一定 达到最大。即有 20+21+22+,+2i1++2h-1=2h-1 证毕 /华电计算机系
North China Electric Power University 2. 深度为h 的非空二叉树最多有2 h -1个结点. 证明: 由性质1可知,若深度为h的二叉树的每一层的结点数 目都达到各自所在层的最大值,则二叉树的结点总数一定 达到最大。即有 2 0+21+22+…+2i-1+ …+2h-1 = 2h -1 证毕. 华电计算机系
North China Electric Power University I 3.若非空二叉树有n个叶结点有n2个度为2的结点 no=n2+1 证明: 设该二叉树有叫个度为1的结点结点总数为n有 n-notnitn 设二叉树的分支数目为B有 B=n-1 (2) 这些分支来自于度为1的结点与度度为结点即 B=n1+2n2 m -(3) 联列关系(1),(2)与(3)可得到 证毕 n0=n2+1 「推论;n=n2+2n3+3n4+…+(m-1)nm+1 4具有n个结点的完全二叉树的深度hn+1. 证明:
North China Electric Power University 3. 若非空二叉树有n0个叶结点,有n2个度为2的结点, 则 n0=n2+1 证明: 设该二叉树有n1个度为1的结点,结点总数为n,有 n=n0+n1+n2 --------(1) 设二叉树的分支数目为B,有 B=n-1 --------(2) 这些分支来自于度为1的结点与度度为2结点,即 B=n1+2n2 --------(3) 联列关系(1),(2)与(3),可得到 n0=n2+1 证毕. 4. 具有n个结点的完全二叉树的深度h=log2n+1. 证明: (略) 推论： n0=n2+2n3+3n4+ +(m-1)nm +1