现在的位置: 首页 > 综合 > 正文

树中叶节点数边数度数之间关系

2014年09月29日 综合 ⁄ 共 602字 ⁄ 字号 评论关闭
程序员最喜欢的衬衫

普通树:

由n个节点构成的二叉树的形态总数为:Cn2n/(n+1).

节点数、 度数(分叉数) 、叶节点数、 边数 之间的关系

  1. 总节点数 = 总边数+1;

  2. 总边数 = 总度数 = 总分叉数​

    ​例子:设树T的度为4,其中度为1,2,3,4的节点个数分别为4,2,1,1,则T中的叶子数为?

    ​总节点数=1*4+2*2+3*1+4*1 +1 =16

    ​叶节点数= 节点数 - 总分叉数 = 16 - 4-1-1-2 = 8

二叉树:

  1. 第i层最多有 2^(i-1)个节点

  2. 深度为k的二叉树最多有 2^(k) - 1 个节点

  3. 二叉树中叶节点数 n0 度为2的节点数为 n2 则 n0=n2+1

  4. m个节点的完全二叉树 深度 n=log m[下取整] + 1;

    ​例子:699个节点的完全二叉树的叶子节点数位多少?

    解法1:

    ​​深度为 n = log699+1 = 10;

    ​深度为10的满二叉树节点数为2^10-1=1023>699,故叶子节点出现在9、10 两层;

    ​第10曾叶节点个数为:699 - 2^9+1 = 189;

    ​第9曾叶节点个数为:2^(9-1) - 189/2[上取整] = 161;

    ​共189+161=350个叶节点

    ​解法2:

    ​n=n0+n1+n2

    ​n0=n2+1;

    ​又完全二叉树度为1的节点个数只可能为0或1;

    ​故n0=n/2或(n+1)/2  即n0=n/2[上取整]

所以叶节点数为 [699]/2=350

抱歉!评论已关闭.