二分搜索树的弱智提问
来源：
qq__5197
2017-02-28
为什么每个节点的键值大于左孩子，小于右孩子。那么这个节点就会大于整个左子树呢？这个节点的左孩子的右孩子为什么不能大于这个节点的键值？还是说这只是一种规定？
写回答
1回答
-
这个问题并不弱智，是个很好的问题。这里我的定义不够明确。
严格的说，如果按照“每个节点的键值大于左孩子，小于右孩子”这个定义，是存在这样的二分树，其中左子树中存在节点，大于这个节点本身的，比如下面的这棵二分搜索树。8大于5，但是是符合这个定义的。
5 / \ 3 6 / \ 1 8
不过，在我们实际生成这棵树的过程中。8这个节点到来，看到根节点是5，自然就会跑到5的右侧。所以，按照这个定义的逻辑创造的二分搜索树，一定有这样的性质：这个节点的值大于整个左子树；小于整个右子树。
尽管如此，我们这个定义确实不够严谨。更严谨的定义二分搜索树的方式，是直接定义：每一个节点的左子树所有节点都小于这个节点；右子树所有节点都大于这个节点；且左右子树均为二分搜索树。在这个定义下，就不存在你说的这个问题了：）
感谢你指出这个问题，有时间我会更新以下课程和相关的课件的。抱歉！
1012017-02-28
相似问题