满二叉树各种节点数目的计算 |
您所在的位置:网站首页 › 完全二叉树的结点计算公式 › 满二叉树各种节点数目的计算 |
1. 二叉树的基本性质
二叉树的第i层至多有2i-1个结点(i>=1)
证明:(归纳法) 归纳基:i=1时,只有一个结点,2i-1=20=1; 归纳假设:假设对所有的i命题成立; 归纳证明:二叉树中每个结点最多有两个子树,则第i+1层的结点数为2*2i-2=2i-1. 深度为h的二叉树至多有2h-1个结点(h>=1)证明:n=20+21+...+2h-1=2h-1.(等比数列) 对于一棵二叉树,若含有n0个叶子结点,n2个度为2的结点,则必存在关系式:n2=n0-1证明:设二叉树的结点总数为n=n0+n1+n2; 二叉树上的分支总数为b=n1+2n2; 又b=n-1; 故:n2=n0-1. 具有n个结点的完全二叉树的深度为[log2n]+1.[]表示取整证明:设完全二叉树的深度为k,则:2k-1 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |