在 BST 中，假设作为比较器，需要哪种遍历才能按降序访问所有键？

Question

在 BST 中，假设作为比较器，需要哪种遍历才能按降序访问所有键？答案是反向输入—— 我想知道为什么会这样。

如果是按递增顺序访问所有键怎么办，下面的答案是什么？ 1. In- 2.Pre- 3.Post- 4. Reverse In- 5. Reverse Pre- 6. Reverse Post-

Answer 1

我假设左子树包含小于根的元素，右子树包含大于根的元素。

先回答你的第二个问题：中缀遍历。这首先递归地访问左侧（较小）child，然后是项目本身，然后递归地访问右侧（较大）child。不难看出，这个方法是按升序访问所有元素的。

但是按降序访问所有项目必须做相反的事情，因此反向中缀。这将首先递归地访问较大的元素，然后是元素本身，然后递归地访问较小的元素。

Answer 2

中缀遍历将按升序打印键。

Answer 3

按顺序表示左-根-右（递增）。

void ascending(BST* root)
{
    if(root == NULL) return;
    ascending(root->left);
    std::cout<<root->data<<" ";
    ascending(root->right);
}

你也可以做右根左（Reverse In for decreasing）。就是遍历的方式，就是这样！！

void descending(BST* root)
{
    if(root == NULL) return;
    descending(root->right);
    std::cout<<root->data<<" ";
    descending(root->left);
}

In BST, which traversal is required to visit all keys in decreasing order, assuming as a comparator?