В BST, какой обход требуется для посещения всех ключей в порядке убывания, считая в качестве компаратора?

Question

В BST, какой обход требуется для посещения всех ключей в порядке убывания, предполагая в качестве компаратора? Ответ Reverse In- И мне было интересно, почему это так.

А что, если нужно, чтобы все ключи в порядке возрастания, , что будет отвечать на следующее? 1. In- 2.Pre- 3.Post- 4. Обратный инвертор 5. Обратный пре- 6. Обратный пост

Answer 1

Я предполагаю, что левое поддерево содержит элементы, меньшие, чем корневые и правые элементы поддерева больше, чем корень.

Чтобы ответить на ваш второй вопрос сначала: это был бы обход границы. Сначала он рекурсивно посещает левого (меньшего) дочернего элемента, а затем сам элемент, затем правый (больший) рекурсивно. Нетрудно видеть, что этот метод посещает все элементы в порядке возрастания.

Но тогда посещение всех предметов в порядке убывания должно сделать обратное этому, следовательно, обратный инфикс. Сначала это будет рекурсивно посещать более крупные элементы, затем сам элемент, а затем рекурсивно меньшие элементы.

Answer 2

Обход Infix будет печатать ключи в порядке возрастания.

Answer 3

В порядке означает левое право-право (увеличение).

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

Вы также можете сделать правое правое левое (Обратное In для уменьшения). Это просто путь обхода, вот и все!

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