使用遞歸進行二叉搜索樹遍歷

Question

問：關於使用遞歸和返回的二叉搜索樹遍歷，我有疑問。我必須按照按升序排列鍵的BST，然後「倒轉」它，這樣所有鍵都按降序排列，正如您在圖片中看到的那樣。

根據我的下面的代碼的瞭解，我認爲步驟是：

->reverseKeys (10) ->reverseKeys (2) 
    ->reverseKeys (null): return 
    ->reversekeys(null): return 
    ->BSTNODE <T> ptr = root.left; 
    ->root.left = root.right; 
    ->root.right = ptr; 

我想我誤解的代碼。有人能夠擴展這個代碼如何將左邊的圖片更改爲右邊？我將不勝感激任何幫助。

25     25 
/\    /\ 
10 40  ---> 40 10 
/\ /\   /\/\ 
2 20 30 45  45 30 20 2 
/ \   / \ 
15 35   35 15 

public static <T extends Comparable<T>> 
void reverseKeys(BSTNode<T> root) { 
    if (root == null) { 
     return; 
    } 
    reverseKeys(root.left); 
    reverseKeys(root.right); 
    BSTNode<T> ptr = root.left; 
    root.left = root.right; 
    root.right = ptr; 
} 

Answer 1

檢查BST - 反向下面的代碼

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

// Search with a valid node returned, assuming int 

public Node traverse (Node root, int data){ // What data are you looking for again? 
    if(root.data == data) { 
     return root; 
    } 
    if (root.left != null){ 
     return traverse (root.left, data); 
    } 
    if (root.right != null){ 
     return traverse (root.right, data); 
    } 
    return null; 
} 

Answer 2

這些線路只是交換左，右子樹的節點序遍歷（RVL）。由於對方法的遞歸調用，當方法執行時，每個節點都有左右子樹交換。

BSTNode<T> ptr = root.left; 
root.left = root.right; 
root.right = ptr;