有限状態マシンでバイナリツリーを走査することは可能ですか？

Question

良い一日、

ちょうど明確にするために：私は、再帰的または反復的な解決策を捜しているわけではないが、ウィキペディアは、任意の木の、前インおよびポストオーダートラバースを実装するのに十分な擬似コードを持っています。

私は、バイナリツリーを走査する有限状態機械の構築に興味があります。

ツリーはノードで構成されています。ノードには、LeftChild、RightChild、およびParentプロパティがあります。

FSMは、任意の時点でノードで停止し、必要な数の状態を持つことができますが、これはチューニングマシンと区別される任意の種類の動的スタックではありません。入力 "GiveNext"では、マシンは次のノードで停止する必要があります（たとえば、ツリーの先行予約をトラバースするなど）。

私はかなり長い間試してきましたが、確かに。問題は、最近の決定を追跡する必要があるため、親を介してノードを再訪する際に、左が処理されたときに右に回ることができるようにすることです。

思考？

ありがとうございます！ ハーブ

Answer 1

この種の練習には欠点があるかもしれません。私はこれが少なくとも役に立つと思っています。

私は、FSMが「現在のノード」上の任意の時点で「立っている」と考えています。したがって、この現在のノードに関する情報で正しい0/1の値を返す利用可能な入力があります。

入力：

• AmIALeftChild（現在のノードがそれ以外の場合は0、その親ノードの左ぶら下がっている場合は1に等しい）
• AmIARightChild（1私はそれ以外の場合は0、私の親ノードの左にぶら下げていた場合）
• HaveLeftChild？ （私は左の子があれば1、そうでなければ0）
• HaveRightChild？ （私には正しい子供がいれば1、それ以外の場合は0）

そして、これらの3つの出力の説明に従って「トラバース」するのはいいですか？

出力：

• GoToLeftChild
• GoToRightChild
• GoUp

（のみ1~3出力の任意の時点で真であることができる）

両方の制約がある場合

：許可され、その後、あなたはこのような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ステップの前に、ちょうど開始ノードのためのテストを追加します。私は、START AM。 TRUEの場合はReport、そうでない場合は図のように続行します。

個々のアクションは意味：

• GO LEFTは - もしあれば、現在のノードの左の子現在のノードにします。成功すればOK、そうでない場合はNoを返します。
• GO RIGHT - 現在のノードの右の子が存在する場合、現在のノードを現在のノードにします。そのようなノードが存在しない場合は答えが成功すればOK、または権利です。
• GO - 現在のノードの親を現在のノードにします。結果の状態は1つだけです。ルートの場合、親は存在しませんが、FSMはルートの親にアクセスしようとしません。
• I AM LEFT - 現在のノードが親の左の子であるかどうかをテストします。答えは真または偽です。
• I AM RIGHT - 現在のノードが親の右の子であるかどうかをテストします。答えは真または偽です。
• I AM START - 現在のノードが開始ノードであるかどうかをテストします。答えは真または偽です。