二叉树中序遍历怎么看 数据结构之二叉树的性质

数据结构之二叉树的性质  

二叉树的特殊形态

　　满二叉树（Full Binary Tree） 一棵深度为k且有 k 个结点的二叉树 　　特点 二叉树的所有分支结点都存在左子树和右子树 　　特点 二叉树的所有叶子结点都在同一层上

　　完全二叉树（Complete Binary Tree） 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从 至n的结点一一对应   　　特点 叶子结点只可能在层次最大的两层上出现 　　特点 对任一结点 若其右分支下的子孙的最大层次为L 则其左分支下的子孙的最大层次必为 L 或 L+

二叉树的性质

性质 在二叉树的第i层上至多有 i 个结点（i≥ ） 证明 归纳法　　i= 时 只有一个根结点 显然 i = = 是对的 　　现在假定对所有的j ≤j＜i 命题成立 即第j层上至多有 j 个结点 那么 可以证明j=i时命题也成立 　　由归纳假设 第i 层上至多有 i 个结点 由于二叉树的每个结点的度至多为 故在第i层上的最大结点数为第i 层上的最大结点数的 倍 即 × i = i

性质 深度为k的二叉树至多有 k 个结点（k≥ ） 证明 　　由性质 可见 深度为k的二叉树的最大结点数为

性质 对任何一棵二叉树T 如果其终端结点数为n 度为 的结点数为n 则　　　　　n =n ＋ 证明:　　设n 为二叉树T中度为 的结点数 　　∵ 二叉树中所有结点的度均小于或等于 　　∴ n=n +n +n 　　　　　　　　　　　　　　　　　　　　( )　　设B为分支总数 则n=B+ 　　∵ 这些分支是由度为 或 的结点射出的　　∴ B=n + n 　　∴ n=n + n + 　　　　　　　　　　　　　　　　　　　　( )　　由式( )和( )得　　　　n =n +