论文部分内容阅读
[摘要]二叉树中E=I+2n公式在查询等领域有着广泛的应用。一般对它采用数学归纳法来证明，且仅限于公式的直接应用。直接证明方法在充分利用二叉树定义的迭代关系基础之上，分析二叉树中E与I之间的密切关系，据此提出该公式的另一种证明方法并进行严格的证明。该方法能更多地了解每一边、每一结点上的具体情况，因而具有广泛意义。
[关键词]扩充二叉树 内部结点 外部结点 外部路径长度 满二叉树
中图分类号：O29 文献标识码：A 文章编号：1671－7597（2008）0310071－01
定理：对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足E=I+2n关系，其中n是内部结点个数。二叉树中E=I+2n公式主要应用在查询领域。其证明通常采用归纳法，该方法不能清楚地表达每一条边或每一个结点与E、I之间的内在关系。对公式进行直接证明的方法是建立在分析清楚这些情况的基础之上，而该关系的分析又要充分利用二叉树的定义。
一、证明方法的分析
如图所示，设1、2、3、4、5和6代表一棵二叉树的内部结点（图1中用实心的圆表示），a、b、aa、ab和bb代表边（图1中用实心的边表示），则I中:经过边a的个数是3，用AI表示；经过边b的个数是2，用BI表示；经过边aa的个数是1，用AAI表示；经过边ab的个数是1，用ABI表示；经过边bb的个数是1，用BBI表示。即：
其中I'表示内部路径长度I经过的各路径；Ii表示二叉树中T中任一结点i与其子女直接相连的边在I中经过的次数，如点1直接相连的两边分别是a、b，I1就表示I中过a、b两边的次数；如果i是叶结点，所以左右子女个数为0，所以经过i与其左右子女直接相连的边的次数为0。
又设E中含有通过边a的次数分别为AE；通过边b的次数分别为BE；通过边aa的次数分别为AAE；通过边ab的次数分别为ABE；通过边ba的次数分别为BAE；通过边bb的次数分别为BBE；通过边aaa的次数分别为AAAE；通过边aab的次数分别为AABE；通过边aba的次数分别为ABAE；通过边abb的次数分别为ABBE；通过边bbb的次数分别为BBBE。我们知道图中所示情况时:
其中E'表示E经过的路径。由上式可推出如下式，其中0表示：某点是叶结点，该点对应边是扩展边，I中经过该边的次数是0。
由图1也得如下关系，其中I4、I5、I6为0，因为点4、5、6是叶结点，内部路径长度I中经过该点到子女的边是扩展边；Ei表示E中从i直接到左右子女的边的次数。
二、E=I+2n公式证明
不失一般性，任一棵二叉树T中设其结点按1、2、3…（N为自然数）编号，设任一结点i左子孙的个数为ni左，右子孙的个数为ni右，从该点直接到左子女的边在I中的次数为AiI，从该点直接到右子女的边在I中的次数BiI，若此，从该点直接到左右子女的边在I中次数为Ii，并且有：Ii=AiI+BiI。根据二叉树路径长度定义，I是根结点到所有子孙结点的路径和，路径定义又是一点到另一子孙结点的边的和。所以有：AiI=ni左、BiI=ni右、 。因而，对任一点i有关系：Ii=AiI+BiI=ni左+ni右。
又任一二叉树T中，设任一结点出度为i，其子孙结点个数为Ni、空域（指向子女的指针域为空）个数为Ni空、非空的域的个数为Ni非，由二叉树的性质知如下式成立:①N0+N1+N2=n；
二叉树T中设任一结点为i，E中从i直接到左右子女的边的次数Ei，由E的定义知Ei=Ni Ei=Ni非+2。由I的定义知：Ii=Ni非，所以得⑧i=Ii+2。由E的定义有：
证毕。
三、结论
证明的方法主要是：1.把每一条边经过的次数的规律找到。I中经过该边次数是其下结点的个数、E中经过该边次数是其下空域的个数。而每条边之下的空域个数又是n+1个（n表示其下结点个数），如图2所示。2.获得I中每一结点到左右子女的边的经过它的次数。也就是把直接连接左右子女的边的经过它们的次数相加，如图3所示。
在上述第一点中获得的每一边的信息对同一父结点相加。3.把所有结点的到左右子女的边的经过它们的次数相加就得关系E=I+2n。每个结点与其直接相连的边的之间的关系如二叉树的定义，具有迭代关系，所以上述第二点得到的关系对每一点都成立。该证明方法是建立在对每一点、每一边的具体分析之上，所以能更多地掌握每一结点、每一边与I与E中的关系，因而有更广泛应用。
参考文献：
[1]张乃孝,算法与数据结构C语言描述(第2版)北京:高等教育出版社,2006.
[2]Duane A.Bailey. Java Structuresta Structures in Java for the Principled Programmer(second edition).McGraw Hill Companies inc, 1999.
[3]许卓群、张乃孝、杨冬青、 唐世渭，数据结构. 北京: 机械工业出版社，1987.
[4]A.V.Aho， J.E.Hopcroft， J.D.Ullman. Data structures and Algorithm. Addison.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]扩充二叉树 内部结点 外部结点 外部路径长度 满二叉树
中图分类号：O29 文献标识码：A 文章编号：1671－7597（2008）0310071－01
定理：对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足E=I+2n关系，其中n是内部结点个数。二叉树中E=I+2n公式主要应用在查询领域。其证明通常采用归纳法，该方法不能清楚地表达每一条边或每一个结点与E、I之间的内在关系。对公式进行直接证明的方法是建立在分析清楚这些情况的基础之上，而该关系的分析又要充分利用二叉树的定义。
一、证明方法的分析
如图所示，设1、2、3、4、5和6代表一棵二叉树的内部结点（图1中用实心的圆表示），a、b、aa、ab和bb代表边（图1中用实心的边表示），则I中:经过边a的个数是3，用AI表示；经过边b的个数是2，用BI表示；经过边aa的个数是1，用AAI表示；经过边ab的个数是1，用ABI表示；经过边bb的个数是1，用BBI表示。即：
其中I'表示内部路径长度I经过的各路径；Ii表示二叉树中T中任一结点i与其子女直接相连的边在I中经过的次数，如点1直接相连的两边分别是a、b，I1就表示I中过a、b两边的次数；如果i是叶结点，所以左右子女个数为0，所以经过i与其左右子女直接相连的边的次数为0。
又设E中含有通过边a的次数分别为AE；通过边b的次数分别为BE；通过边aa的次数分别为AAE；通过边ab的次数分别为ABE；通过边ba的次数分别为BAE；通过边bb的次数分别为BBE；通过边aaa的次数分别为AAAE；通过边aab的次数分别为AABE；通过边aba的次数分别为ABAE；通过边abb的次数分别为ABBE；通过边bbb的次数分别为BBBE。我们知道图中所示情况时:
其中E'表示E经过的路径。由上式可推出如下式，其中0表示：某点是叶结点，该点对应边是扩展边，I中经过该边的次数是0。
由图1也得如下关系，其中I4、I5、I6为0，因为点4、5、6是叶结点，内部路径长度I中经过该点到子女的边是扩展边；Ei表示E中从i直接到左右子女的边的次数。
二、E=I+2n公式证明
不失一般性，任一棵二叉树T中设其结点按1、2、3…（N为自然数）编号，设任一结点i左子孙的个数为ni左，右子孙的个数为ni右，从该点直接到左子女的边在I中的次数为AiI，从该点直接到右子女的边在I中的次数BiI，若此，从该点直接到左右子女的边在I中次数为Ii，并且有：Ii=AiI+BiI。根据二叉树路径长度定义，I是根结点到所有子孙结点的路径和，路径定义又是一点到另一子孙结点的边的和。所以有：AiI=ni左、BiI=ni右、 。因而，对任一点i有关系：Ii=AiI+BiI=ni左+ni右。
又任一二叉树T中，设任一结点出度为i，其子孙结点个数为Ni、空域（指向子女的指针域为空）个数为Ni空、非空的域的个数为Ni非，由二叉树的性质知如下式成立:①N0+N1+N2=n；
二叉树T中设任一结点为i，E中从i直接到左右子女的边的次数Ei，由E的定义知Ei=Ni Ei=Ni非+2。由I的定义知：Ii=Ni非，所以得⑧i=Ii+2。由E的定义有：
证毕。
三、结论
证明的方法主要是：1.把每一条边经过的次数的规律找到。I中经过该边次数是其下结点的个数、E中经过该边次数是其下空域的个数。而每条边之下的空域个数又是n+1个（n表示其下结点个数），如图2所示。2.获得I中每一结点到左右子女的边的经过它的次数。也就是把直接连接左右子女的边的经过它们的次数相加，如图3所示。
在上述第一点中获得的每一边的信息对同一父结点相加。3.把所有结点的到左右子女的边的经过它们的次数相加就得关系E=I+2n。每个结点与其直接相连的边的之间的关系如二叉树的定义，具有迭代关系，所以上述第二点得到的关系对每一点都成立。该证明方法是建立在对每一点、每一边的具体分析之上，所以能更多地掌握每一结点、每一边与I与E中的关系，因而有更广泛应用。
参考文献：
[1]张乃孝,算法与数据结构C语言描述(第2版)北京:高等教育出版社,2006.
[2]Duane A.Bailey. Java Structuresta Structures in Java for the Principled Programmer(second edition).McGraw Hill Companies inc, 1999.
[3]许卓群、张乃孝、杨冬青、 唐世渭，数据结构. 北京: 机械工业出版社，1987.
[4]A.V.Aho， J.E.Hopcroft， J.D.Ullman. Data structures and Algorithm. Addison.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”