二进制搜索树与字符串
Mar*_*sen 3 binary-tree binary-search-tree
我有一本书以非常糟糕的方式解释二元搜索树背后的理论我知道左右两个孩子的顺序有一些东西,但我仍然无法得到一个大于另一个前一个级别的想法.
以这个字符串树为例:
(抱歉我的油漆)这个例子直接来自我的书:)
有人可以向我解释订单吗？这背后的逻辑是什么？
在BST中,每个节点最多只有一个左孩子和一个右孩子.给定节点左侧的每个节点都小于它,并且给定节点右侧的每个节点都大于它.其中一个后果就是你不能有重复的值,所以我不确定这个例子是否与书中的具体相符.
在您的示例中,字符串按字母顺序排序.以根节点为例,鲍勃来到凯伦面前,所以鲍勃走向凯伦的左边.汤姆跟凯伦走来,所以汤姆走向卡伦的右边.从整个树看,你可以看到Karen左边的每个节点(Bob,Alan,Ellen)按字母顺序排在Karen之前,而Karen右边的每个节点(Tom,Wendy)按照字母顺序排在Karen之后.无论您查看哪个节点,此模式都是相同的.