这种练习可能会有很多限制,我可能会错过。我希望这至少有一点有用。
我假设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”应该是相互排斥的。但我正在用这种方式写出来,以节省一点时间。如果你不明白我的意思,请问。
你看过Morris Inorder Traversal吗? https://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading – msandiford
谢谢@msandiford。一个线程化的二叉树([link](https://en.wikipedia.org/wiki/Threaded_binary_tree))在按顺序访问树时将会很棒。不幸的是,改变树布局是没有问题的。由于树是一个前缀树(aka Patricia trie),访问它的最明智的方式是预定。出于纯粹的好奇心(因为我无法改变树布局):没有线程二叉树用于预先遍历,或者是否存在? – Herb