关于丰满二叉树节点与树枝间的关系问题答薛问天先生

《关于丰满二叉树节点与树枝间的关系问题答薛问天先生》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于丰满二叉树节点与树枝间的关系问题答薛问天先生沈卫国本文是回答薛问天先生“为什么二叉树遍历节点不能遍历所有的无穷枝？”一文的。薛先生在该文的最后总结说：“你要使该节点对应一个无穷枝，就必须选择某种性质，从这无穷枝中按照此性质选择其中一个无穷枝。但是最后导致的结果是你遍历的无穷枝都具有此性质，从而遍历不了不具有此性质的无穷枝，也就是说你遍历不了全体无穷枝。当然这只是一种举例和解释，严格意义上这还够不上无穷枝集合不可数的证明。要证明无穷枝集合不可数还要使用对角线方法。”首先，薛先生的上述说法，会导致矛盾。他说只证明了我未证明实数可数，而他只是“举例和解释”，不能说证明了实数不可数。但是，如果真

2、的“只能”如薛先生那样，选定特殊的枝去与树中节点对应，那就意味着必有树中的其它枝不能再与节点对应，而树的全部节点当然可数，于是，这实际不就是证明了实数不可数（总有枝数多于节点数）？何须再有康托对角线法？或者说，此法实际本质上与对角线法是同构的。而如果情况并不是“只能如此”，而是仅仅他所列举的这些特殊的定义的、刻意安排的枝与树中所有节点一一对应后，才会有其它枝不能再去与节点对应（节点已经“用完”。有意思的是，这里本质上与对角线法是一回事：对角线法本质上（尽管康托没有明说或者根本没有意识到）说的是“如果”有个特殊的前提，即一位（即树中的一层）仅仅可以对应于一个实数，必有多余的实数不能再与位再对应

3、上，因为位已经“被”“用完”了。你也可以这么看，事先选定一个实数（对角线上后来“产生”的那个），就是“令其”不会被任何位对应上（对应上的是其它实数）；而薛先生这里，是选出一些特殊形态的枝（实数），令它们与所有已经数到的层的所有节点一一对应上，于是我们没有“选到”的其它那些一般形态的枝，必然不会再能与已经“名花有主”的那些节点去“一一对应”了。从另一个角度，我们是不是也可以这么看，就是你实际是“选定”了另一些你原先“选定”的那些特殊形态枝之外的枝，反正使它们不会再去与已经“被用完”节点去对应？所以二者本质是一回事），也就是说，我们还有“可能”有其它方法可以使所有枝与节点一一对应上，具体说就是对

4、于与节点对应而言，薛先生没有“选上”的那些枝，或者说“故意”不去选的那些枝（也可以说“故意”选一些枝不去与任何节点对应。本质一回事。），在其它对应方式下，其实完全是“有可能”可以和节点对应上的。也就是有可数的“可能”，也就是薛先生并没有“证明”我的“二叉树法”“并未证明”实数可数。总之，如果薛先生认为他的办法是绝对的，那他已经证明了实数不可数，而无需再像他所说的再去用对角线法；而如果薛先生认为他的方法是相对的，那他就没有如其所愿地“证明”我没有证明“实数可数”。也就是，他横竖要陷于矛盾之中。薛问天先生认为，丰满二叉树的每一个节点，都对应无穷枝，所以，树上的每一个节点是可以遍历到的，而枝不行。

5、也就是不可数。但薛先生显然忘记了，丰满二叉树上的每一枝，同样也有无穷多个节点。此外，究竟有没有我们可以数到某一个树枝上的所有节点（穷尽所有节点），但却数不到此枝的情况？也就是，我们在数到此枝上的任何一个节点时，所对应的被认为数到的枝，都是“路过”此节点的其它枝。这在什么情况下才可以发生？因为要确定这个（或这些）“其它枝”不是那个预先选定的“某一枝”，必然在那个导致这两个枝“分道扬镳”的那个层的节点以后的下一层的这两个树枝上的相应的两个节点（分属这两个不同的树枝上的）的数值必然是不同的。这要求导致两枝“分道扬镳”的那个“分叉”节点之后，还有节点，也就是该层之后，还要有层。这在有限情况当然是如此

6、的。就如任何具体的自然数后面还有自然数一样。但如果对于实无穷而言，如果无穷层后面居然还有层，也就是不能认为该树枝的所有节点，所有层都能被穷尽，这实际是一种潜无穷的观点。这不符合康托可数、不可数概念的实无穷要求。另一种看法，就是我们已经“穷尽”了该枝的所有节点，但仍旧不能数到该枝，那么，只有一种可能，就是此树的其它枝比该枝长。而这显然不符合丰满二叉树的定义。树中的各枝，都是“等长”的，没有谁比谁长的问题。于是，我们如果采取实无穷的观点（与康托一致），同时承认树上的枝没有长短之分，那么，如果我们有某一枝我们没有数到，就只能是该枝的起码某一个节点没有被数到。而这不可能。于是没有树中的任何一枝会被遗

7、漏(随着节点的被穷尽)。薛先生自己也说，他假设的那两种特殊定义的枝，不但依赖于选定某层，还要依赖于在该层“之后”要确定该两枝的特殊形态。由薛先生定义的这两种特殊的枝构成的树，不是丰满树了，是非丰满树。薛先生用丰满树中的所有节点去与这样的（非丰满）枝去对应，只能要么取与康托完全不一致的潜无穷观点，要么认为在可以穷尽所有枝上的节点的前提下（实无穷观点），他定义的这两种特殊形态的枝的长度，还要长于其它他认为的不会被