二叉搜索树 - 排序？
Binary Search Tree - Sorted?
我不明白为什么二叉搜索树总是被定义为"sorted"。我得到一个二进制堆的数组表示，你有一个完全排序的数组。我还没有看到二叉搜索树的数组表示如此难以让我看到它们像数组一样排序，例如 [0,1,2,3,4,5]，而是根据每个节点排序。从概念上考虑 BST 是 "sorted" 的正确方法是什么？
这有帮助吗？这是一个二进制堆，显示为数组
它与数组排序的意义不同"sorted"（树，除了堆，无论如何很少表示为数组），但它们有一个结构，可以让你轻松地遍历按排序顺序排列的元素：简单地通过 depth-first 搜索遍历 BST 的节点，并在查看其左侧 child （如果有）但在查看其右侧之前输出每个节点的值child（如果有的话）。
顺便说一句，存储堆的数组几乎总是未排序。堆本身也可以不说是"sorted"，因为它没有足够的结构能够很容易地按排序顺序产生元素而不用连续破坏堆删除顶部元素。例如，虽然您确实知道顶部元素比它的两个 children 都大（或更小，具体取决于堆类型），但您无法提前知道哪个 child 比另一个小.
二叉搜索树有很多种。它们都有一个共同点：它们满足一个支持二进制搜索的不变量，即 一种顺序关系，树中的每个元素都可以与树中的任何其他元素进行比较，在 total preorder.
这是什么意思？
让我们考虑教科书上关于 BST 不变量的典型陈述，即每个节点的键大于其左侧的所有键 sub-tree，且小于其右侧的所有键 sub-tree.我们省略了比较相等的键的冲突解决细节。
我向 three-year-olds 的 class 解释它的方法是尝试将所有节点折叠到叶子的底层，让它们掉下来。或者，对于 high-schoolers，从每个 node/key 画一条线将它们投射到 x-axis 上。完成后，很明显键已经按（升序）顺序排列。
这个想象中的偶然观察是否类似于我们对排序序列的定义？是的。由于 BST 的元素满足总预序，BST 的 in-order 遍历必须按顺序生成这些元素（例如：证明）。
相当于说如果我们通过in-order遍历将一个BST的key存储在一个数组中，那么这个数组就会被排序。
因此，根据我们对 BST 的初始定义，in-order 遍历是将一个遍历视为 "sorted".
的直观方式
就数据结构（数组、树、链表等）而言，"sorted" 意味着按顺序遍历所有元素，您会发现它们的值是根据某种规则排序的（ >、<、<= 等）。
对于数组，这很容易理解，因为它是一种线性数据结构。
但是，树并没有通过 BST 进行迭代，您会注意到所有元素都是根据规则排序的，左值 <= 节点值 < 右值（或类似的东西）；排序数据结构的定义。
我不明白为什么二叉搜索树总是被定义为"sorted"。我得到一个二进制堆的数组表示，你有一个完全排序的数组。我还没有看到二叉搜索树的数组表示如此难以让我看到它们像数组一样排序，例如 [0,1,2,3,4,5]，而是根据每个节点排序。从概念上考虑 BST 是 "sorted" 的正确方法是什么？
这有帮助吗？这是一个二进制堆，显示为数组
它与数组排序的意义不同"sorted"（树，除了堆，无论如何很少表示为数组），但它们有一个结构，可以让你轻松地遍历按排序顺序排列的元素：简单地通过 depth-first 搜索遍历 BST 的节点，并在查看其左侧 child （如果有）但在查看其右侧之前输出每个节点的值child（如果有的话）。
顺便说一句，存储堆的数组几乎总是未排序。堆本身也可以不说是"sorted"，因为它没有足够的结构能够很容易地按排序顺序产生元素而不用连续破坏堆删除顶部元素。例如，虽然您确实知道顶部元素比它的两个 children 都大（或更小，具体取决于堆类型），但您无法提前知道哪个 child 比另一个小.
二叉搜索树有很多种。它们都有一个共同点：它们满足一个支持二进制搜索的不变量，即 一种顺序关系，树中的每个元素都可以与树中的任何其他元素进行比较，在 total preorder.
这是什么意思？
让我们考虑教科书上关于 BST 不变量的典型陈述，即每个节点的键大于其左侧的所有键 sub-tree，且小于其右侧的所有键 sub-tree.我们省略了比较相等的键的冲突解决细节。
我向 three-year-olds 的 class 解释它的方法是尝试将所有节点折叠到叶子的底层，让它们掉下来。或者，对于 high-schoolers，从每个 node/key 画一条线将它们投射到 x-axis 上。完成后，很明显键已经按（升序）顺序排列。
这个想象中的偶然观察是否类似于我们对排序序列的定义？是的。由于 BST 的元素满足总预序，BST 的 in-order 遍历必须按顺序生成这些元素（例如：证明）。
相当于说如果我们通过in-order遍历将一个BST的key存储在一个数组中，那么这个数组就会被排序。
因此，根据我们对 BST 的初始定义，in-order 遍历是将一个遍历视为 "sorted".
的直观方式就数据结构（数组、树、链表等）而言，"sorted" 意味着按顺序遍历所有元素，您会发现它们的值是根据某种规则排序的（ >、<、<= 等）。
对于数组，这很容易理解，因为它是一种线性数据结构。 但是，树并没有通过 BST 进行迭代，您会注意到所有元素都是根据规则排序的，左值 <= 节点值 < 右值（或类似的东西）；排序数据结构的定义。