二叉樹中節點的路徑

我想遞歸地顯示一個二叉樹中給定節點的路徑，其中該方法將以下列方式輸出所需的路徑：「左，右，左」。這是我到目前爲止有：二叉樹中節點的路徑

public static void pathToNode(BTNode p, char target, String res){ 
    if(p.data == target){ 
     res = res + p.data; 
     System.out.println(res); 
     return; 
    }else if(res != null){ 
     if(res.charAt(0) == 'S'){ 
     res = res + p.data; 
     } 
    }else{ 
     pathToNode(p.leftLink, target, res); 
     pathToNode(p.leftLink, target, res); 
    } 

}

此代碼是爲了剛剛打印出像這樣的路徑：「ABCD」。完成此操作後，我打算根據每個節點遍歷的正確選項，將方法打印到右邊的左邊。有任何想法嗎？

來源

2012-11-16 Simon Hillary

你會得到什麼結果？這是如何被稱爲？你卡在哪裏？ – EdC

所以我這是一個二進制搜索，你打印出你檢查的字符？ –

@EdC即時獲取StringIndexOutOfBounds異常， –

當您在第一個if子句中找到要查找的目標時，您正在打印結果。或者，您應該嘗試樹的左右兩個分支，在最後一個子句中您（幾乎都是左轉彎）做的。

我不知道什麼是第二子句應該做的，但刪除它，並在遞歸調用添加p.data到res應確保「當前」步驟是保存在res變量：

if (p.data == target) { 
    res = res + p.data; 
    System.out.println(res); 
} else { 
    pathToNode(p.leftLink, target, res + p.data); 
    pathToNode(p.rightLink, target, res + p.data); 
}

這樣，您就使用了遞歸算法常用的傳統基本情況+遞歸情況。

來源

2012-11-16 10:17:59 akaIDIOT

非常感謝，它在開始時稍作修改，首先檢查p == null，如果是，返回。避免空指針異常！ –

@SimonHillary完全取決於你如何打電話給你的方法，你沒有指定:) 另外，不要忘記接受你認爲最好回答你的問題的答案;） – akaIDIOT

對不起，我的錯！任何想法如何修改這個打印出'左'或'右'基於是否遍歷到左或右節點爲了達到目標？ –

我認爲你試圖從根目錄找到路徑。另外我假設樹只有一條路徑可以達到目標。我的意思是相同的元素不能在樹中的不同位置。

此代碼將工作，

public static void pathToNode(BTNode p, char target, String res){ 
    if(p.data == target){ 
     res += p.data; 
     System.out.println(res); 
     return; 
    } 
    else{ 
     if(res==null){ 
      res=""; 
     } 
     res += p.data; 
     pathToNode(p.leftLink, target, res); 
     pathToNode(p.rightLink, target, res); 
    } 
}

但是，這將是非常低效和內存成本的簡單的解決方案。請閱讀有關樹遍歷的更多信息，以獲得一個好的解決方案。

來源

2012-11-16 10:17:49 andunslg

你的代碼對我來說有點不清楚。 'S'應該是根有效載荷？另外，你應該嘗試使用更多的變量名。

public static String pathToNode(BTNode p, char target) { 
    // termination rules 
    if (p.data == target) { 
     // success 
     return p.data;  
    } 
    // failure: p is not the target AND is a leaf. 
    if (p.leftLink == null && p.rightLink == null) return null; 

    // recursion: if p is in the subtree, this will find it. 
    return (pathToNode(p.leftLink, target) == null) ? (p.data + pathToNode(p.rightLink), target) : (p.data + pathToNode(p.leftLink, target)); 

}

編輯：這可能，當然，畢竟返回null，如果目標不是在樹中。另外，我忘了實際打印路徑。它現在在那裏。

來源

2012-11-16 10:23:21

對不起，'S'應該是目標字符，我正在使用它作爲測試用例 –

仍然沒有看到'目標'如何適合那裏。但無論如何，這個travert（滑稽？）將有所有這些字符串連接的神經可怕的性能縮放。記住這一點。 –

好吧，這是我對問題的第五個「解決方案」，我想我已經搞得一團糟了。二叉樹只有大約50個節點，所以性能不是主要問題！ –

二叉樹中節點的路徑

回答

相關問題