CS/자료구조

[자료구조](11)[트리의 순회]

황올뱀 2025. 5. 5. 21:54

순회

트리의 모든 노드를 중복 없이 모두 방문하기

예시 트리

 

전위순회

루트 -> 왼쪽 노드 -> 오른쪽 노드 순서
예) 위 트리를 전위순회로 탐방하면
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

 

중위순회

왼쪽 노드 -> 루트 -> 오른쪽 노드 순서
예) 위 트리를 중위순회로 탐방하면
     4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

  • 스택을 이용한 중위순회 구현
    스택의 특성을 이용해 중위순회를 구현할 수 있다.
    1. 리프노드까지 스택에 노드를 넣으면 왼쪽으로 탐색
    2. 스택에서 노드를 뺄 때 오른쪽 자식 노드 탐색
      예) 위의 트리에서 스택 S로 중위순회를 한다 하면
          S = {1, 2, 4}로 넣어놓고,
           4를 pop하고 4는 리프노드이므로 오른쪽 자식 없음, S = {1, 2}
           2를 pop하고 2의 오른쪽 자식 5를 스택에 집어넣음 S = {1, 5}
           5를 pop하고 5는 리프노드이므로 오른쪽 자식 없음, S = {1}
           1을 pop하고 2의 오른쪽 자식 3을 스택에 집어넣음 S = {3}
           3의 왼쪽 자식 6을 집어넣음 S = {3, 6}
           6을 pop하고 6은 리프노드이므로 오른쪽 자식 없음, S = {3}
           3을 pop하고 5는 오른쪽 자식 7을 스택에 집어넣음, S = {7}
           7을 pop하고 7은 리프노드이므로 오른쪽 자식 없음, S = {}
           스택이 비었으므로 탐색 종료
           pop한 것을 순서대로 나열하면
           4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

 

후위순회

왼쪽 노드 -> 오른쪽 노드 -> 루트 순서
예) 위 트리를 후위순회로 탐방하면
    4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
    (루트 노드가 제일 마지막!)

레벨순회

레벨이 작은 순, 왼쪽 순으로 이동
예) 위 트리를 레벨순회로 탐방하면
     1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

  • 큐를 이용한 레벨순회 구현
    큐의 특성을 이용해 레벨순회를 구현할 수 있다.
    1. dequeue하는 노드의 왼쪽자식, 오른쪽 자식 순으로 큐에 넣는다
      예)위의 트리에서 큐 Q로 레벨순회를 한다 하면
           Q = {1}로 넣어두고
           1을 dequeue하고 자식노드 2, 3 enqueue Q = {2, 3}
           2를 dequeue하고 자식노드 4, 5 enqueue Q = {3, 4, 5}
           3을 dequeue하고 자식노드 6, 7 enqueue Q = {4, 5, 6, 7}
           4를 dequeue하고 4는 리프노드이므로 Q = {5, 6, 7}
           5를 dequeue하고 5는 리프노드이므로 Q = {6, 7}
           6을 dequeue하고 6은 리프노드이므로 Q = {7}
           7을 dequeue하고 7은 리프노드이므로 Q = {}
           큐가 비었으므로 탐색 종료
           dequeue한 것을 순서대로 나열하면
           1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
728x90
반응형