如何將BST的節點值從最高位輸出到最低位？

Question

這是一個問題，我認爲這很容易，但我發現我錯了。我可以在不遞歸的情況下完成程序，但是我想問一下這個問題是否可以在遞歸版本中完成？

Answer 1

遞歸二叉樹遍歷基本上（如果僞代碼，這是課程）：

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 

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 
}