完全二叉树计算叶子结点数 |
您所在的位置:网站首页 › 完全二叉树的节点计算 › 完全二叉树计算叶子结点数 |
1. 首先看下完全二叉树的定义: 一棵深度为k,且有个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。 2.一条规则: 对任何一棵二叉树T,如果其终端结点数为,度为2的结点数为,则。 推导过程: n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数。 则分支数=2n2+n1 (每个n2节点有2个分支,每个n1结点有1个分支) 另外又有:分支数=n0+n1+n2-1 (每个结点上面对应一个分支,除了根节点上面没有分支) 2n2+n1=n0+n1+n2-1 得 n0=n2+1 3.假设n为完全二叉树的结点总数,则有:n=n0+n1+n2 结合2的结论有:n0=(n-n1+1)/2 4.由于n1=1或者0,则 当n1=0时(即度为1的节点为0个时,此时n为奇数)或者n为奇数时n0= (n+1)/2; 当n1=1时(即度为1的节点为1个时,此时n为偶数)或者n为偶数 n0= n/2;
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |