[Python Algorithms] 트리(Tree) 2 : 순회 알고리즘

트리에서는 네 가지 순회 알고리즘을 가진다.

1) 전위 순회(Pre-Order Traverse)

2) 중위 순회(In-Order Traverse)

3) 후위 순회(Post-Order Traverse)

4) 단계 순위 순회(Level-Order Traverse)

1. 전위 순회

A -> B -> D -> E -> C -> F -> G

 

 

 

2. 중위 순회

D -> B -> E -> A -> F -> C -> G

 

 

3. 후위 순회

D -> E -> B -> F -> G -> C -> A

 

 

 

4. 단계 순위 순회

A -> B -> C -> D -> E -> F -> G

 

 

5.  트리 순회 알고리즘 코드

트리 클래스 구조 코드

eusun0830.tistory.com/45?category=718944

[Python Algorithms] 트리(Tree) 1

 

1) 전위 순회 알고리즘

def preorder_traverse(node):
    
    if node == None: return
    print(node.data, end = ' -> ')
    preorder_traverse(node.left)
    preorder_traverse(node.right)

전위 순회 알고리즘은 매개 변수인 node가 트리의 끝에 위치해 있는 지를 확인해야 한다.

만약 node가 끝에 위치해 있다면 node.data를 출력해준다.

그 이후 재귀함수를 이용해서 node.left가 node 매개변수 자리로 들어와 같은 작업을 반복하고,

이 작업이 끝나면 node.right가 node 매개변수 자리로 들어와 같은 작업을 반복하게 된다.

 

2) 중위 순회 알고리즘

def inorder_traverse(node):
    if node == None: return
    inorder_traverse(node.left)    
    print(node.data, end='->')
    inorder_traverse(node.right)

전위 순회와 비슷하게 재귀적 호출을 사용하고 재귀 함수를 호출하는 위치만 달라진다.

 

3. 후위 순회 알고리즘

def postorder_traverse(node):
    if node == None: return
    postorder_traverse(node.left)
    postorder_traverse(node.right)
    print(node.data, end = '->')

후위 순회 역시 재귀 함수를 사용하고 앞의 두 가지의 순호 알고리즘과 재귀 함수 호출 위치만 달라진다.

 

4. 단계 순회 알고리즘

levelq = []

def levelorder_traverse(node):
    global levelq 
    levelq.append(node)
    while len(levelq) != 0:
       visit_node = levelq.pop(0)
       print(visit_node.data, end = '->')
       
       if visit_node.left != None:
           levelq.append(visit_node.left)
       if visit_node.right != None:
           levelq.append(visit_node.right)

매개변수로 받은 node를 큐 levelq에 담고 큐의 크기가 0이 아니면 pop을 이용해 levelq에서 하나씩 값을 가져온다.

방문한 노드는 visit_node로 정하고 방문한 노드의 왼쪽 노드가 있다면 큐에서 visit_node의 왼쪽 노드를 삽입하고 visit_node의 오른쪽 노드가 존재하면 큐에 저장하고 반복문 while을 통해 코드를 반복한다.

 

 

---

[참고문헌]

1. "트리구조", ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

2. 박선주, 영진닷컴, "필수 알고리즘 with 파이썬"