전위, 중위, 후위 순회

전위 순회를 위한 사고 순서

전위 : 루트 노드 → 왼쪽 자식 → 오른쪽 자식
중위 : 왼쪽 자식 → 루트 노드 → 오른쪽 자식
후위 : 왼쪽 자식 → 오른쪽 자식 → 루트 노드

1. 이 노드를 "방문해도 되는 상태"인지 체크해야 해

• 트리에서는 이미 방문한 노드는 다시 방문하면 안 돼
• 그리고 노드가 없다는 표시 (".")인 경우도 넘겨야 돼

→ 따라서 “이 노드를 방문할 필요가 없다면 바로 return”

즉, 너가 쓴 if self.visit[node] == True or ...는

"이 노드를 방문하면 안 되는 이유가 뭐지?" 를 생각하고 있는 거야

이 사고를 일반화하면:

• "이미 방문했는가?"
• "존재하지 않는 노드인가?" (예: ".")
• → 그럼 "아무것도 하지 말고 리턴"

사고 패턴 ①:

💭 "이 노드를 처리하지 않아야 할 조건이 뭔가?" → 방어 코드부터 작성하자

---

2. 현재 노드를 "처리"한다

• 전위 순회니까 지금 이 노드에서 뭔가를 해야 해
  • 출력하거나
  • 리스트에 넣거나
  • 어떤 연산을 하거나

사고 패턴 ②:

💭 "이 노드를 방문했다고 간주하면, 어떤 작업을 해야 하지?"

---

3. 왼쪽 자식, 오른쪽 자식으로 내려간다

• 재귀로 왼쪽 먼저, 그다음 오른쪽으로

사고 패턴 ③:

💭 "이제 자식 노드로 가려면, 그 자식이 있는지 어떻게 확인하지?"

보통 트리는 self.graph[node] 형태로 [left, right] 를 가지고 있으니까:

left, right = self.graph[node]
self.preorder(left)
self.preorder(right)

---

입력 트리:

       A
      / \
     B   C

내가 preorder('A') 호출했다고 가정하면:

1. "A"는 방문하지 않았고, .도 아님 → OK
2. "A"를 출력 or 처리
3. "A"의 왼쪽 자식 "B"로 재귀 호출
4. "B"도 같은 방식으로 처리
5. 다시 돌아와서 "A"의 오른쪽 "C"로 재귀

---

preorder 구현

def preorder(self, node):
        if node == '.' or self.visit[node]:
            return
        
        self.visit[node] = True
        print(node, end=' ')
        left_ch, right_ch = self.graph[node]        

        self.preorder(left_ch)
        self.preorder(right_ch)

inorder 구현

if node == '.' or self.ino_visit[node]:
            return
        
        self.ino_visit[node] = True
        left_ch, right_ch = self.graph[node]        

        self.inorder(left_ch)
        print(node, end='')
        self.inorder(right_ch)

postorder 구현

if node == '.' or self.pto_visit[node]:
            return
        
        self.pto_visit[node] = True
        left_ch, right_ch = self.graph[node]        

        self.postorder(left_ch)
        self.postorder(right_ch)
        print(node, end='')

마무리 팁

• 무작정 코드를 외우거나 복붙하지 말고, 지금처럼 "내가 왜 이걸 해야 하지?" 라고 계속 물어봐
• 그게 너를 진짜 문제 푸는 사람으로 성장시킬 거야

---