树遍历算法:为什么左节点总是在右节点之前?

[免责声明:我只是在这里陈述我的直觉,所以我不能为我的陈述提供参考。]

搜索 树,其中左子节点的值小于节点中的值,而右子节点中的值则相反。当我们执行按顺序遍历时,我们将按升序获得值。请注意,这里有另一个约定:所有关于bst的文献都说较小的值向左,较大的值向右;但是如果定义中没有这样做,它一点也不会有影响。可能升序被认为有点“自然”排序(我见过的所有库排序函数都是按升序排序的) ).

水平镜像

也许有一个平行的宇宙,在这个宇宙中,人们发展了BSTs的思想,在那里,较小的值向右,如果他们描述他们的遍历算法是在左前右,那么他们的遍历所产生的结果将与我们的“传统”遍历完全相同!

左边和右边的名称是树节点的任意名称。在定义二叉搜索树的情况下,这个约定很重要,其中左子树存储比根小的节点,右子树存储比根大的节点。

在更大的层面上,先左后右的习惯很可能与拉丁字母从左到右的阅读方式有关。