第二次作业 2 --Ch3.3 求证 E=I+2n 求证：对于含有 n 个内节点的二元树，证明 E=I+2n。其中 E、I 分别为外部和内部路径长度。 证明： ⑴ 当 n=0 时，即为空树，此时 E=0，I=0，显然等式成立； ⑵ 一般地，假设 E=I+2k 成立，其中 0≤k＜n. 因为 n＞0，所以根节点一定为内节点。 用 nL、nR、n 分别表示左子树的内节点数、右子树的内节点数及全部内节点数，则有： 用 xL、xR、x 分别表示左子树的外节点数、右子树的外节点数及全部外节点数，则有： nL+nR+1=n xL+xR=x 对 x 与 n 之间的关系作如下推导： 节点总数等于内部节点和外部节点的总和，节点总数的另一种计算方法为：除了根之外 的每个节点，都是某个内部节点的两个子树之一，所以： x+n=2n+1 即 x=n+1 用 EL、ER、E 分别表示左子树的外部路径长度、右子树的外部路径长度及全部外部路 径长度，用 IL、IR、I 分别表示左子树的内部路径长度、右子树的内部路径长度及全部内部 路径长度，则有： 所以有如下关系： EL=IL+2nL ER=IR+2nR E=（EL+xl）+（ER+xR） =（ IL+2nL+xL）+ （IR+2nR+xR） =（IL+nL）+（IR+nR）+（nL+nR）+（xL+xR） =I+（n-1）+x =I+（n-1）+（n+1） =I+2n 得证。