完全二叉树结点问题设一棵完全二叉树共有700个结点,则在该二叉树中有?个叶子结点?

1个回答

  • 首先注意完全二叉树数的特点:

    完全二叉树的特点是:(1)深度为k的完全二叉树的叶子结点都出现在第k层或k-1层.(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+1.

    这样意味着,度为1的结点只能为0个或1个!

    设度为0的结点(叶子结点)有n0个,设度为1的结点有n1个,设度为2的结点有n2个

    则总的结点数n=n0+n1+n2,另一方面,度为结点有两个分支,度为1的结点有一条分支

    每个结点都有一条分支和其相连,除了根结点,所以有n=2*n2+n1+1;

    这样就有:

    n2=n0-1;

    从而可推出:

    n=2n0-1+n1;

    现在回到问题,共有700结点:

    701=2n0+n1

    而n1只能取0或1,从该题看,只能取1;

    所以可得:

    n0=700/2=350;

    所以共有350个叶子结点