Как вывести значения узлов BST от высшего к низшему?

Question

Как вывести значения узлов BST от высшего к низшему?

Это вопрос, я думал, что это будет легко, но я обнаружил, что ошибаюсь в последнем. Я могу завершить программу без рекурсии, но я хочу спросить, можно ли решить эту проблему в рекурсивной версии или нет?

0

binary-search-tree c++order

Решение

Другие решения

Конечно. Предполагая, что BST отсортирован так, что узлы «больше чем» находятся справа, а узлы «меньше чем» слева, рекурсивная функция, подобная этой, будет работать:

void recurse(Node* node)
{
if (node == nullptr) return;
recurse(node->right); // Explore all the "greater than" nodes first
std::cout << node->value << std::endl; // Then print the value
recurse(node->left); // Then explore "less than" nodes
}

0

Источник

Accepted Answer

Рекурсивный бинарный поиск по дереву в основном (псевдокод, если это курсовая работа):

def traverse (node):
if (node == NULL):
return
traverse (node.left)
doSomethingWith (node.payload)
traverse (node.right)
:
traverse (root)

Вот и все, что нужно сделать, просто заменить doSomethingWith() с тем, что вы хотите сделать (например, печать).

Это будет проходить в порядке слева направо, поэтому, если ваш BST упорядочен таким образом, что слева означает ниже, просто поменяйте местами два traverse звонки.

В качестве примера рассмотрим следующее дерево:

       20
/  \
10    25
/     /  \
5    24    27
/          /
2         28

как воплощено в этом примере программы C:

#include <stdio.h>

typedef struct s {
int payload;
int left;
int right;
} tNode;

tNode node[] = {  // Trust me, this is the tree from above :-)
{20,  1,  4}, {10,  2, -1}, { 5,  3, -1}, { 2, -1, -1},
{25,  5,  6}, {24, -1, -1}, {27, -1,  7}, {28, -1, -1}};

static void traverse (int idx) {
if (idx == -1) return;
traverse (node[idx].right);
printf ("%d ", node[idx].payload);
traverse (node[idx].left);
}

int main (void) {
traverse (0);
putchar ('\n');
return 0;
}

Запуск этой программы дает следующий вывод:

28 27 25 24 20 10 5 2

2