Morris Inorder Tree Traversal (모리스 중위 순회)

재귀도 스택도 안 쓰고, 임시 스레딩(threading) 으로 O(1) 추가 메모리만으로 중위순회 하는 기법

개념

• 각 노드 cur의 중위 선행자¹ pred의 right 포인터를 잠깐 cur로 연결(스레딩)²해 두고, 왼쪽 서브트리 처리가 끝났을 때 그 스레드를 따라 원 위치로 복귀한다

• 방문(visit) 규칙은 중위순서 그대로: Left → Node → Right

• 순회가 끝나면 모든 임시 연결을 원래대로 복구하므로 트리는 변하지 않는다

특징

• 시간복잡도: O(n) (각 간선이 최대 2번(내려갈 때/복귀할 때) 사용)

• 공간복잡도: O(1) (재귀 스택/명시적 스택 불필요)

• 트리 보존: 임시 스레딩을 반드시 되돌리는 것이 핵심

• 장단점

  • 장점: 스택 없이 중위순서 보장, 깊은 트리에서도 스택 오버플로우 위험 없음

  • 단점: 순회 중 포인터를 건드리므로 동시 접근/불변 구조에는 부적합, 구현 실수 시 복구 누락 위험

동작 흐름(중위)

1. cur가 왼쪽 자식이 없으면: cur를 방문하고 cur = cur->right

2. 왼쪽 자식이 있으면:

   1. pred = cur->left에서 시작해 pred->right가 nil(또는 cur)일 때까지 오른쪽으로 최대로 진행해 pred를 찾는다

   2. pred->right가 nil이면 스레딩 생성(pred->right = cur) 후 cur = cur->left

   3. pred->right가 cur이면 스레딩 해제(pred->right = nil) → cur 방문 → cur = cur->right

이 과정을 cur가 nil이 될 때까지 반복

코드 예시

// 모리스 순회 (중위 순회 에디션)
while (cur != t->nil) {
    if (cur->left == t->nil) {
        // 각주 대신 cur 배열에 push하는 거 넣기
        cur = cur->right;
    } 
    else {
        node_t *pred = cur->left;
        while (pred->right != cur && pred->right != t->nil) {
        pred = pred->right;
        }
        if (pred->right == t->nil) {
        pred->right = cur;
        cur = cur->left;
        } else {
        pred->right = t->nil;
        // 각주 대신 cur 배열에 push하는 거 넣기
        cur = cur->right;
        }
    }
}
return 0;

쓰고 싶다면 각주 부분에 배열에 삽입하는거나 프린트 넣어서 쓰면된다