是否可以使用有限状态机遍历二叉树？

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 - 测试当前节点是否为开始节点。答案是真或假。