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

Question

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

Answer 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个叶子结点