在二叉樹中查找循環

如何在二叉樹中查找循環？我正在尋找一種解決方案，而不是將訪問節點標記爲已訪問或進行地址散列。有任何想法嗎？在二叉樹中查找循環

2012-07-05 novice

二叉樹不包含循環。如果他們這樣做，他們首先不是樹木。

2012-07-05 21:01:11 amb

如果最後一個節點指向根節點，那該怎麼辦......多數民衆贊成循環權...如果它已被錯誤地執行......那麼你將如何檢測它？ – novice 2012-07-05 21:03:05

最後一個節點被稱爲葉子，它們不指向其他節點。你在說什麼，是圖形而不是樹。如果你有一棵樹（無論是二進制，紅黑，AVL等），它將不包含循環。樹的構建禁止循環。 – amb 2012-07-05 21:06:33

正如我所說的，它是由於一些錯誤而發生的......爲你的便利讓我們放下d字樹n假設它是一些像結構一樣的樹有一個循環......現在你會怎麼做？ – novice 2012-07-05 21:08:19

正如前面提到的那樣：樹不包含循環（循環）。

要測試您向圖包含（已加入到樹節點引用）的循環，你可以遍歷槽樹並添加每個節點的訪問列表（或它的哈希值，如果你比較喜歡），並檢查每個新節點是否在列表中。大量用於圖表中循環檢測的算法只是谷歌搜索而已。

2012-07-05 21:29:22 mariusnn

假設你有一棵二叉樹，但你不信任它，你認爲它可能是一個圖，一般情況下會記錄下被訪問的節點。從圖中構建最小生成樹的方法有點相同，這意味着空間和時間的複雜性將成爲一個問題。

另一種方法是考慮保存在樹中的數據。考慮你有一些哈希值，所以你可以比較。

甲僞代碼將測試該條件：

每個節點必須具有最大2個孩子和1個父（最多3個連接）的。多於3個連接=>不是二叉樹。
父母不能是孩子。
如果一個節點有兩個子節點，那麼左邊的子節點的值比父節點的值小，右邊的子節點有更大的值。因此，考慮到這一點，如果葉子或內部節點具有較高級別上的某個節點（如父母的父節點），則可以根據這些值確定一個循環。如果一個孩子是一個正確的節點，那麼它的值必須大於父母的值，但是如果該孩子形成一個循環，這意味着他來自父母的左邊部分或右邊部分。

3.a.所以，如果它是從左邊的部分，那麼它的價值比它的兄弟姐妹小。所以=>不是二叉樹。這個想法對另一部分來說也是一樣的。

測試之外，在什麼樣的形式是，你要測試的樹？記住每個節點都有一個指向它的父節點的指針。這個指針指向單親。因此，根據樹的格式，您可以從中獲益。

2012-07-05 21:45:00 amb

如果可能存在循環，那麼它只是平常的圖形。有很多種方法可以找到循環： Finding all cycles in a directed graph

2012-08-08 08:51:51 mvnukov

雖然這可能在理論上回答這個問題，但[這將是更可取的]（// meta.stackoverflow.com/q/8259）在這裏包括答案的基本部分，並提供了供參考的鏈接。 – 2016-08-30 17:09:06

回答