是否可以使用有限狀態機遍歷二叉樹？

Question

美好的一天，

只是要清楚：我不尋找遞歸或迭代解決方案，維基百科有足夠的僞代碼來實現任何樹的前，後和後序遍歷。

我有興趣構建一個有限狀態機來遍歷二叉樹。

樹由節點組成。節點有一個LeftChild，一個RightChild和一個Parent屬性。

FSM在任何給定的時間停止在一個節點上，並且可以具有所需的狀態，但沒有任何類型的動態堆棧（它與圖靈機區分開來）。在輸入「GiveNext」時，機器應停止在下一個節點上（例如遍歷樹預訂。）

我已經嘗試了很長一段時間，懷疑這是不可能的，但我不是當然。問題在於需要跟蹤最近的決定，因此在重新訪問通過父節點的節點時，可以在左側處理完畢後右轉。

想法？

在此先感謝！ 香草

Answer 1

這種練習可能會有很多限制，我可能會錯過。我希望這至少有一點有用。

我假設FSM在'當前節點'上的任何給定時間'站立'是可以接受的，因此它有可用的輸入返回正確的0/1值與關於這個當前節點的信息。

輸入：

• AmIALeftChild（等於1如果當前節點是懸留下了他們的父節點，否則爲0）
• AmIARightChild（1，如果我掛離開我的父節點，否則爲0）
• HaveLeftChild？ （如果我有左孩子，則爲1，否則爲0）
• HaveRightChild？ （如果我有一個正確的孩子，則爲1，否則爲0）

可以按照這3個輸出中的說明「遍歷它」嗎？

輸出：

• GoToLeftChild
• GoToRightChild
• GOUP

（只有3個輸出的1可以在任何給定的時間爲真）

如果兩個約束是允許，那麼你可以建立一個像這樣的FSM：

名

美國

• 啓動
• NormalTraverse
• GoBackFromLeft
• GoBackFromRight
• 成品

這是國家機器：

 
Start -> just go to NormalTraverse state (assuming we are on the root, right) 

NormalTraverse -> 
    If HaveLeftChild=1 Then 
     Set GoToLeftChild=1 (and others outputs to 0) 
     Go to NormalTraverse 
    ElseIf HaveRightChild Then 
     Set GoToRightChild=1 
     Go to NormalTraverse 
    ElseIf AmIALeftChild Then 
     Set GoUp=1 
     Go to GoBackFromLeft 
    ElseIf AmIARightChild Then 
     Set GoUp=1 
     Go to GoBackFromRight 
    Else 
     Go to Finished. 

GoBackFromLeft -> 
    If HaveRightChild Then 
     Set GoToRightChild=1 
     Go to NormalTraverse. 
    ElseIf AmIALeftChild Then 
     Set GoUp=1 
     Go to GoBackFromLeft 
    ElseIf AmIARightChild Then 
     Set GoUp=1 
     Go to GoBackFromRight 
    Else 
     Go to Finished. 

GoBackFromRight 
    If AmIALeftChild Then 
     Set GoUp=1 
     Go to GoBackFromLeft 
    ElseIf AmIARightChild Then 
     Set GoUp=1 
     Go to GoBackFromRight 
    Else 
     Go to Finished. 

現在請原諒我的英語，請注意代碼不是程序性的，「正確地」'正確''擴展'它們之後，「IF」應該是相互排斥的。但我正在用這種方式寫出來，以節省一點時間。如果你不明白我的意思，請問。

Answer 2

這是我拿出來的許多紙張，價值半棵樹後，主要是繪製許多二叉樹（尤其是退化的樹），以驗證FSM正常工作。

可訪問所有的時間要求的唯一的變量是開始節點。這可以是樹中的任何節點：FSM僅遍歷此子樹。

假設開始節點已經被處理（或者不需要處理）。但是，如果不適用於您的應用程序，它將很容易整合：在GO LEFT步驟之前，只需爲起始節點添加一個測試：I AM START。如果爲TRUE，則報告，否則繼續如圖所示。

單獨行動的意思是：

• 向左走 - 使當前節點的左子當前節點，如果有的話。如果成功，答案是肯定的;如果沒有這樣的節點，答案是否定。
• 正確 - 使當前節點的右側子節點成爲當前節點（如果有）。如果成功，答案是肯定的;如果沒有這樣的節點，答案是否定。
• GO UP - 使當前節點的父節點成爲當前節點。只有一個結果狀態。對於根目錄，父目錄不存在，但FSM永遠不會嘗試訪問根目錄的父目錄。
• 我左邊 - 測試當前節點是否是其父親的左孩子。答案是真或假。
• 我是正確的 - 測試當前節點是否是其父親的右孩子。答案是真或假。
• I AM START - 測試當前節點是否爲開始節點。答案是真或假。