c++ - BSTのノードの値を最高から最低まで出力する方法は?

Question

これは簡単だと思っていた質問ですが、最後に間違っていることがわかりました。再帰なしでプログラムを終了できますが、この問題を再帰バージョンで終了できるかどうかを尋ねたいですか?

Answer 1

再帰的な二分探索木トラバーサルは基本的に次のとおりです (これがコースワークである場合の擬似コード):

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

本当にこれでdoSomethingWith()すべてです。実行したいもの (印刷など) に置き換えるだけです。

これは左から右の順序でトラバースするため、左が下を意味するように BST が順序付けられている場合は、2 つの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

Answer 2

もちろん。「より大きい」ノードが右側に、「より小さい」ノードが左側になるように 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
}