유한 상태 머신으로 이진 트리를 트래버스 할 수 있습니까?

Question

좋은 날,

그냥 재귀 적 또는 반복적 인 해결책을 찾고있는 것이 아닙니다. Wikipedia는 모든 트리의 사전, 순서 및 사후 순회를 구현하기에 충분한 의사 코드를 가지고 있습니다.

저는 바이너리 트리를 통과하는 유한 상태 기계를 만드는 데 관심이 있습니다.

트리는 노드로 구성됩니다. 노드에는 LeftChild, RightChild 및 Parent 속성이 있습니다.

FSM은 주어진 시간에 노드에서 정지하지만, 필요한만큼의 상태를 가질 수 있지만 어떤 종류의 동적 스택도 없습니다 (튜링 기계와 구별됩니다). "GiveNext"입력에서 기계는 다음 노드에서 정지해야합니다 (예 : 선주문 순회).

나는 지금 당분간 노력해 왔지만 가능하지 않다고 생각하지만 나는 그렇지 않습니다. 확실한. 문제는 최근 의사 결정을 추적 할 필요가 있기 때문에 부모를 통해 노드를 다시 방문 할 때 왼쪽 처리가 끝나면 오른쪽으로 돌아갈 수 있습니다.

생각하십니까?

미리 감사드립니다. 허브

Answer 1

내가 누락되었을 수있는 이런 종류의 운동에는 많은 제약이 따릅니다. 나는 이것이 적어도 약간 유용하다고 희망한다.

FSM이 '현재 노드'의 주어진 시간에 '대기'하고 있으므로 현재 노드에 대한 정보로 올바른 0/1 값을 반환하는 입력을 사용할 수 있다고 가정합니다.

입력 : (0, 그렇지 않으면 나는 내 부모 노드의 1 왼쪽 매달려 있어요 경우)

AmIARightChild

• AmIALeftChild (그렇지 않으면 0을 현재 노드가 부모 노드의 왼쪽 매달려 경우 1과 동일)
• HaveLeftChild? (왼쪽 아이가있는 경우 1, 그렇지 않은 경우 0)
• HaveRightChild? (올바른 아이가있는 경우 1, 그렇지 않은 경우 0)

그리고이 3 가지 출력의 지침에 따라 '트래버스'해도됩니까?

출력은 :

• 는
• 모두 제약 경우

  (주어진 시간에 해당 될 수있는 단지 1 3 개 출력) GoUp

을

을 GoToRightChild GoToLeftChild 허용되면 다음과 같은 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 단계 전에 시작 노드에 대한 테스트를 추가하기 만하면됩니다. TRUE이면보고하고 그렇지 않으면 그림과 같이 계속합니다.

개별 행동은 의미 :

• GO LEFT - 모든이있는 경우, 현재 노드의 왼쪽 자식 현재 노드합니다. 성공하면 대답은 OK이고, 그런 노드가 없다면 No Left입니다.
• GO 오른쪽 - 현재 노드의 오른쪽 자식을 현재 노드 (있는 경우)로 만듭니다. 성공하면 대답은 OK이고 노드가 없다면 No Right입니다.
• 위로 이동 - 현재 노드의 부모를 현재 노드로 만듭니다. 결과 상태는 하나뿐입니다. 루트의 경우 부모는 존재하지 않지만 FSM은 루트의 부모를 액세스하려고 시도하지 않습니다.
• I AM LEFT - 현재 노드가 부모 왼쪽 자식인지 테스트합니다. 대답은 참 또는 거짓입니다.
• I AM RIGHT - 현재 노드가 부모 오른쪽 자식인지 테스트합니다. 대답은 참 또는 거짓입니다.
• I AM START - 현재 노드가 시작 노드인지 테스트합니다. 대답은 참 또는 거짓입니다.