如何找到非二叉樹中的第n個節點？

我知道如何遍歷一棵二叉樹using the answer here，但是如果我想停在預先遍歷的第10個節點上，我該怎麼做？如何找到非二叉樹中的第n個節點？

2014-12-08 Doug Smith

難道你不會只重複遍歷遍歷n次的樹嗎？您在預訂遍歷中看到的每個節點都會增加計數器，並且當計數器== n停止獲取當前節點時。

當然是根的前序遍歷的第一個，最左邊的孩子遞歸調用，接下來最左邊的孩子遞歸調用，...，最右邊的孩子遞歸調用

2014-12-08 04:12:36 Freestyle076

你如何保持n個軌道有關係嗎？給定的遍歷實現使用遞歸，這使得它在這方面變得複雜。 – 2014-12-08 04:36:02

@DougSmith：一種可能性：遞歸函數需要一個額外的參數，它是要遍歷的元素的最大數量，並返回實際遍歷的元素數量（可能會少一些）。另一種可能性是：訪問者對象維護包含剩餘計數的狀態，並返回一個布爾值來指示導線是否應該繼續。（在這種情況下，遞歸遍歷也必須返回相同的布爾指標。） – rici 2014-12-08 04:48:12

那麼，在語言不可知的算法中，我們只需在遞歸算法之外追蹤它，從算法中遞增算法。語言不可知的算法不會被迫考慮內存管理。如果我們想獲得具體的實現，大多數語言將支持基於參數的計數器和n變量的傳遞，或者可以使用全局變量來跟蹤這兩個變量 – Freestyle076 2014-12-08 04:53:14

如何找到非二叉樹中的第n個節點？

回答

相關問題