《关于丰满二叉树节点与树枝间的关系问题答薛问天先生》由会员分享，可在线阅读，更多相关《关于丰满二叉树节点与树枝间的关系问题答薛问天先生（12页珍藏版）》请在金锄头文库上搜索。
1、关于丰满二叉树节点与树枝间的关系问题答薛问天先生沈卫国本文是回答薛问天先生“为什么二叉树遍历节点不能遍历所有的无穷枝？”一文的。薛先生在该文的最后总结说：“你要使该节点对应一个无穷枝，就必须选择某种性质，从这无穷枝中按照此性质选择其中一个无穷枝。但是最后导致的结果是你遍历的无穷枝都具有此性质，从而遍历不了不具有此性质的无穷枝，也就是说你遍历不了全体无穷枝。当然这只是一种举例和解释，严格意义上这还够不上无穷枝集合不可数的证明。要证明无穷枝集合不可数还要使用对角线方法。”首先，薛先生的上述说法，会导致矛盾。他说只证明了我未证明实数可数，而他只是“举例和解释”，不能说证明了实数不可数。但是，如果真的
2、“只能”如薛先生那样，选定特殊的枝去与树中节点对应，那就意味着必有树中的其它枝不能再与节点对应，而树的全部节点当然可数，于是，这实际不就是证明了实数不可数（总有枝数多于节点数）？何须再有康托对角线法？或者说，此法实际本质上与对角线法是同构的。而如果情况并不是“只能如此”，而是仅仅他所列举的这些特殊的定义的、刻意安排的枝与树中所有节点一一对应后，才会有其它枝不能再去与节点对应（节点已经“用完”。有意思的是，这里本质上与对角线法是一回事：对角线法本质上（尽管康托没有明说或者根本没有意识到）说的是“如果”有个特殊的前提，即一位（即树中的一层）仅仅可以对应于一个实数，必有多余的实数不能再与位再对应上，
3、因为位已经“被”“用完”了。你也可以这么看，事先选定一个实数（对角线上后来“产生”的那个），就是“令其”不会被任何位对应上（对应上的是其它实数）；而薛先生这里，是选出一些特殊形态的枝（实数），令它们与所有已经数到的层的所有节点一一对应上，于是我们没有“选到”的其它那些一般形态的枝，必然不会再能与已经“名花有主”的那些节点去“一一对应”了。从另一个角度，我们是不是也可以这么看，就是你实际是“选定”了另一些你原先“选定”的那些特殊形态枝之外的枝，反正使它们不会再去与已经“被用完”节点去对应？所以二者本质是一回事），也就是说，我们还有“可能”有其它方法可以使所有枝与节点一一对应上，具体说就是对于与节
4、点对应而言，薛先生没有“选上”的那些枝，或者说“故意”不去选的那些枝（也可以说“故意”选一些枝不去与任何节点对应。本质一回事。），在其它对应方式下，其实完全是“有可能”可以和节点对应上的。也就是有可数的“可能”，也就是薛先生并没有“证明”我的“二叉树法”“并未证明”实数可数。总之，如果薛先生认为他的办法是绝对的，那他已经证明了实数不可数，而无需再像他所说的再去用对角线法；而如果薛先生认为他的方法是相对的，那他就没有如其所愿地“证明”我没有证明“实数可数”。也就是，他横竖要陷于矛盾之中。薛问天先生认为，丰满二叉树的每一个节点，都对应无穷枝，所以，树上的每一个节点是可以遍历到的，而枝不行。也就是不
5、可数。但薛先生显然忘记了，丰满二叉树上的每一枝，同样也有无穷多个节点。此外，究竟有没有我们可以数到某一个树枝上的所有节点（穷尽所有节点），但却数不到此枝的情况？也就是，我们在数到此枝上的任何一个节点时，所对应的被认为数到的枝，都是“路过”此节点的其它枝。这在什么情况下才可以发生？因为要确定这个（或这些）“其它枝”不是那个预先选定的“某一枝”，必然在那个导致这两个枝“分道扬镳”的那个层的节点以后的下一层的这两个树枝上的相应的两个节点（分属这两个不同的树枝上的）的数值必然是不同的。这要求导致两枝“分道扬镳”的那个“分叉”节点之后，还有节点，也就是该层之后，还要有层。这在有限情况当然是如此的。就如任
6、何具体的自然数后面还有自然数一样。但如果对于实无穷而言，如果无穷层后面居然还有层，也就是不能认为该树枝的所有节点，所有层都能被穷尽，这实际是一种潜无穷的观点。这不符合康托可数、不可数概念的实无穷要求。另一种看法，就是我们已经“穷尽”了该枝的所有节点，但仍旧不能数到该枝，那么，只有一种可能，就是此树的其它枝比该枝长。而这显然不符合丰满二叉树的定义。树中的各枝，都是“等长”的，没有谁比谁长的问题。于是，我们如果采取实无穷的观点（与康托一致），同时承认树上的枝没有长短之分，那么，如果我们有某一枝我们没有数到，就只能是该枝的起码某一个节点没有被数到。而这不可能。于是没有树中的任何一枝会被遗漏(随着节点
7、的被穷尽)。薛先生自己也说，他假设的那两种特殊定义的枝，不但依赖于选定某层，还要依赖于在该层“之后”要确定该两枝的特殊形态。由薛先生定义的这两种特殊的枝构成的树，不是丰满树了，是非丰满树。薛先生用丰满树中的所有节点去与这样的（非丰满）枝去对应，只能要么取与康托完全不一致的潜无穷观点，要么认为在可以穷尽所有枝上的节点的前提下（实无穷观点），他定义的这两种特殊形态的枝的长度，还要长于其它他认为的不会被数到的枝。不采取这两种态度之一，薛先生根本不可能把他的那种树枝与节点的对应方式进行下去。总而言之，薛先生误认为我们在操作某层的节点时，既然可以“数到”那些无穷层的枝，那么，当在层趋于无穷时，仍旧还像有
8、限时的情况一样，总还有枝的层要大于操作的层。这实际是个误解。在实无穷和丰满树的观点下，已经趋于无穷的“操作的”层与树枝的所谓其它层，二者实际归一，是一回事，它们当然“同步”地趋于无穷。只是在有限情况时二者不同。这是讨论整个问题的前提，也就是我们必须在这个前提下去讨论整个问题。为什么？因为康托就是如此做的，我们应该与他保持“高度的一致”（你们不是说他的原则不可动摇的吗）。也就是康托在“构造”那个对角线上的著名的序列（表）外的实数时，是在数到n位时（或涉及到。“数”太具有“操作性”，仅仅是一个形象化的表述），仅仅保证该实数的前n位的排列组合方式，与所数过（涉及）的前n个其它的实数的前n位的排列组合
9、方式都不一样而已。此时并没有涉及n+1、n+2等等位（层）的情况。康托如此，我辈何能不如此，作为康托的铁杆拥趸的薛先生又为什么“刻意”地不去如此？话已经说到这个份上，应该打住了。但我现在确实确实成了“话唠”，行文相当的啰嗦。连我自己都感到特别地是如此。原因是数学、逻辑文章本来应该具备的点到为止，在现实中根本就行不通。我即使如此繁复地从各个角度、方面去论述，面对如此显然的事实，几乎就没有一个真正搞清楚我的意思的。原本不过是一个不超出形式逻辑范畴、难度的问题，由于成了一个著名人物的著名定理，就成了如此难的问题（我先把话放这里：早晚有一天，这件事要成为研究人类思想、思维、概念更替方面的一个典型“案例
10、”）。薛、朱这样的“保守派”就不必说了，即使何、吕这样的“改革派”，我们也没少讨论。因此，我这里不妨再啰嗦啰嗦（生怕对于各位的实际理解力，上面没有讲的太清楚。尽管实际已经很清楚了）。总之，像薛先生所做的，用定义、构造特殊形态的树枝的方法去证明什么，或证明没有证明什么，都等于无意中承认了这棵树是“不丰满”的。而你去用一个不丰满的树的枝去对应一个丰满树的节点，当然可以。两个可数无穷集合的元素，当然是“可以”一一对应上的，但如此就算证明了一个丰满树的所有枝，永远不能用任何办法去与其所有节点一一对应了吗？如果这样，就是证明了实数不可数。而薛先生也清楚，他没有做到这点。那么好，薛先生就没有排除这种对应的
11、可能性，也就是他并没有用这种非丰满树的办法，如他所愿地证明二叉树法证明实数可数的不可能性。也就是薛先生的“沈先生用二叉树法证明实数可数不可能，但实数不可数也没有被证明，要证明还要有劳康托对角线法”的说法本身就不成立。因为有逻辑矛盾。具体说，薛先生的做法，等于承认在数到树中的第n层时，没有能够穷尽丰满树的前n层的所有组合形态（这些没有涉及、也就是没有被薛先生定义的枝（组合形态）在该非丰满树上不存在）。我们为了明晰起见，可以设想两棵树，一棵是丰满的，另一棵就是薛先生定义的那些特殊的树枝构成的非丰满树。我们去用丰满树的所有n层前的节点，去一一对应那棵非丰满树的枝（两个都是可数集合，当然可以），看看出
12、现了什么情况？你还能像康托在其对角线法中所做的那样，虽然位数（也就是这里的树中的层数）n为任意，但一旦选定或论及一个特定的n时，我们所能确定的，仅仅是n、及其之前的位（层）的状态组合形态及与之对应的那张表中的前n个实数吗？显然不能。薛先生自己也说，其定义的那两种特殊的树枝形态（实数形态），是要依赖于大于当时所涉及的那个层数n的，理由当然是显然的：在一棵丰满树上，能够与n及其前面的各层的所有节点一一对应的，只能是可以确定前n+1层（位）的所有状态的所有枝（此时不算n+1层上的节点了。或者也可以这样等价地去看：n层的所有枝或端节点，总数等于n-1层以上的所有层的节点数）。按照这样的节点与枝的对应方
13、式，我们只要逐层数下去，只能是在这棵丰满树上，所有节点，对应了所有枝，不会有遗漏。否则就请你具体指出来，究竟哪个枝没有被数到。特别应该再一次强调，我们这里所使用的原则，与康托在其对角线法中使用的实际完全一样：在康托那里，是当我们逐位操作直到把所有位看成穷尽了一个实无穷的整体时，就（才）认为最终“产生”了那个著名的对角线上的无穷位的实数。这里我们也一样，当所涉及的层（也就是位）逐位做下去直到可以看成穷尽了所有层时，这些枝就是无穷层的枝。而不会像有些人认为的到多少层，只可以数到涉及该层的有限位的枝（此位以下全为零的枝，对应于有理数集合的一个子集合）。因为很简单，如果是这样，就同时也违法了康托的做法
14、。你如果声称完全拥护康托的做法，就没有理由否定这里的本质上同样的做法。我们再回过头来看看薛先生的做法。薛先生的定义：定义两个实数：令=1/3=0.010101，=2/3=0.101010。显然和的任何位的值均不相同。我们把小数点后第n位与不相同但是从此位以后各位全与各位值相同的无穷枝称为n类无穷枝；把第n位与不相同但是从此位以后全与各位相同的无穷枝称为n类无穷枝。另外规定和分别称为0类和0类无穷枝。薛先生的遍历方法：遍历方法下面我们详细地给出由遍历节点从而遍历所有类无穷枝和类无穷枝的方法。逐层遍历二叉树上的节点。让0层节点对应两个无穷枝和。以后各层的每个节点只对应一个无穷枝。对应的规则是：对于
15、每层的2n个节点，凡是节点的标注同的该位相同（即1,3,5,奇数层为0，而2,4,6,偶数层为1）的那一半（2n-1个）节点，对应与在该位以后各位全与相同的无穷枝，这样对应的无穷枝相当于所有n类无穷枝；凡是节点的标注同该位相同（即奇数层为1，偶数层为0）的那一半（2n-1个）节点，对应与该位以后各位全与相同的无穷枝。这样对应的无穷枝相当于所有n类无穷枝。这样一来。在遍历二叉树上第n层的2n个节点时，就刚好遍历了对应的全部2n-1个n类无穷枝和全部2n-1个n类无穷枝。由上面薛先生的原话可以看到，他无论是在定义中，还是在具体的遍历也就是对应方式中，都不能不涉及“该位以后各位”这样的用语。这当然并
16、不奇怪，我前面已经提到了，涉及某层的节点与可以确定该层前各层的形态的所有枝是可以一一对应的，薛先生要想以较少的枝（薛先生也说这是一个枝的子集）去对应该层前的所有节点，当然只能把该层下面的各层的形态也定义出来，确定下来。而这显然是违反康托对角线法的原则的。请去仔细体会对角线法的做法。对角线法中，我们能不能在涉及（数到）n位（层）时，就可以确定n+1、n+2.等等那些位（层）的取值？不能吧？如果可以，还有什么对角线法？当你认为对角线上产生的那个实数的前n位的组合形态与数过的前n个表中的实数的前位的组合都不一样时，却可以定义、确定大于n位那些组合。如此，等于承认当n趋于无穷时，总有比n更大的位的值可以被确定（这不能不说一个潜无穷的过程），如此，你还能认为在n趋于无穷时，只能保证n前的不同的情况的对应方式下才能得到的结论，会在总有大于n的对应方式下也被得到？这种对应方式下，实际康托对角线法也会无效。得不到任何结论。因为康托所认为与对角线上的那个新产生的实数的前
