插曲一–记《数据结构与问题求解（Java语言版）（第4版）》翻译问题

在该书的527页中18.6理论题中,书中这样写道”完全结点是指每个结点都有两个孩子.证明,完全二叉树的结点数加1等于叶子树.” 初看此题目,本人觉得很纳闷,再细细想之,发现似乎是个伪命题.

后来把原版书拿过来,发现书中是这样写的:”A full node is a node with two children. Prove that in a binary tree the number of full nodes plus 1 equals the number of leaves.”

细品之下,发现应该翻译如下:”完全结点是有两个孩子的结点.证明在一个二叉树中完全结点数加1等于叶子树.”

　　请各位看官,对比两段红字的区别.现在是不是好理解了呢,希望翻译英文的人员细心细心再细心,因为你们是在做一项造福的事业.

　　题目来了,那么我就引用严蔚敏的《数据结构(C语言版)》证明方式:

证明:

　　二叉树分为两个子结点的结点即完全结点,一个子结点的结点和无子结点的结点即叶子.故N_总=N₂+N₁+N₀,①

　　从分支的角度来看,除了根结点,其他结点都是由一个分支来进入的,而这些分支都是由完全结点和一个子结点的结点射出来的,故

　　N_总=N₁+2N₂+1,②

　　将二式减一式N₀=N₂+1

问题得证.