給定最小值和最大值的二叉樹遞歸遍歷

-1

問題（必須遞歸）：編寫一個函數，該函數採用二叉樹的根，最小值和最大值，並查找樹中所有落在這些值，至少可能訪問其他節點給定最小值和最大值的二叉樹遞歸遍歷

public boolean inRange(Node node, int max, int min) 
{ 
    return root.element() < max && root.elemnt() > min; 
} 
public void inRangeFinder(Node root, int max, int min) 
{ 
    if (root == null) return; //break 
    if(inRange(root, max, min)) 
     visit(root); //mark as found 
    finder(root.leftChild()); 
    finder(root.rightChild()); 
}

我的問題，是第一個if語句的必要嗎？它會導致我的左和右子樹遍歷問題？最重要的是這種方法的訪問次數最少？

來源

2013-12-16 user3106433

當然這是必要的。你還會如何處理葉子？在問之前，您是否沒有嘗試過使用一些測試用例來測試代碼？ – Noich

更新：對不起，未知您的程序是用java編寫的。我不是Java用戶，所以也許答案是不正確的。請原諒我。

是的，第一條if語句是必要的。如果您忽略了if語句，則您的程序將會遇到一些運行時錯誤，以便訪問空指針。

這基本上是一個左手側的第一個dfs搜索，所以它每次只訪問一次節點。如果你的樹沒有組織，這種方法花費最少的訪問。但如果樹是有組織的樹, 你必須重新定義你的方法來適應特定的樹型獲得最少的訪問。

爲了遞歸，您應該一致地定義函數名稱。
public void finder(Node root, int max, int min) 
      //^^^^^ be the same with your recursive call 
{ 
    if (root == null) return; //break 
    if(inRange(root, max, min)) 
     visit(root); //mark as found 
    finder(root.leftChild(),max,min); 
          //^^same arguments 
    finder(root.rightChild(),max,min); 
          //^^ 
} 

來源

2013-12-16 07:57:53

如果這是在簡單的方式組織比你沒有一個if語句，使一棵樹。

這真的取決於你的樹實現。

爲僞序樹

-find value with min key. 
-travers in order 
    - and check if result of 
     in order traversal result meets max condition

在我opionion你甚至不用檢查特定的範圍。

例如

爲了意味着遍歷每個節點只使用左側的時間葉子

因此，要找到範圍之間的specfic seuence。執行Inorder查找比執行最小值。執行它只要你的實現找到最大的inorder值。

但嘗試保存此過程的結果以獲得您想要的序列。

希望它可以幫助一點點

來源

2013-12-16 07:59:19 Diversity

給定最小值和最大值的二叉樹遞歸遍歷

回答

相關問題