二分搜索树的弱智提问

Question

为什么每个节点的键值大于左孩子，小于右孩子。那么这个节点就会大于整个左子树呢？这个节点的左孩子的右孩子为什么不能大于这个节点的键值？还是说这只是一种规定？

Answer 1

liuyubobobo 2017-02-28 16:20:11

这个问题并不弱智，是个很好的问题。这里我的定义不够明确。

严格的说，如果按照“每个节点的键值大于左孩子，小于右孩子”这个定义，是存在这样的二分树，其中左子树中存在节点，大于这个节点本身的，比如下面的这棵二分搜索树。8大于5，但是是符合这个定义的。

    5
   / \
  3   6
 / \
1   8

不过，在我们实际生成这棵树的过程中。8这个节点到来，看到根节点是5，自然就会跑到5的右侧。所以，按照这个定义的逻辑创造的二分搜索树，一定有这样的性质：这个节点的值大于整个左子树；小于整个右子树。

尽管如此，我们这个定义确实不够严谨。更严谨的定义二分搜索树的方式，是直接定义：每一个节点的左子树所有节点都小于这个节点；右子树所有节点都大于这个节点；且左右子树均为二分搜索树。在这个定义下，就不存在你说的这个问题了：）

感谢你指出这个问题，有时间我会更新以下课程和相关的课件的。抱歉！

• 提问者 qq__5197 #1

  谢谢老师的回答！看您视频收获良多！非常感谢！