[자료구조] 트리 순회 (+코드 구현 with Python)

💡트리 순회(Tree traversal)

트리의 모든 노드를 한 번씩 방문하는 것을 말한다.

데이터를 어떤 순서로 볼 것이냐에 따라서 전위순회, 중위순회, 후위순회로 나눠진다.

 

☝전위 순회 

루트 노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드 
1. 루트 노드 A에서부터 시작, A가 루트 노드이므로 A 먼저, A 기준으로 봤을 때 왼쪽 자식노드는 B이므로 B 방문.
2. B로 와서 B가 다시 루트 노드라고 생각하면 B의 왼쪽 자식노드는 C이므로 C를 방문.
3. C의 왼쪽 자식노드, 오른쪽 자식노드가 없기 때문에  다시 B의 오른쪽 노드인 D를 방문.
4. D가 방문할 수 있느 노드가 없기 때문에 B로 다시오면 B에서 방문할 수 있는 노드는 이미 방문완료. 따라서 A의 오른쪽 자식노드 E 방문.
5. E의 왼쪽 자식 노드 F방문 후 , 오른쪽 자식 노드 G방문.

코드 예시 

def preorder(self):
        def _preorder(node):
            print(node.item, end=' ')
            if node.left:
                _preorder(node.left)
            if node.right:
                _preorder(node.right)
        _preorder(self.root)

 

 

✌ 중위 순회

왼쪽 자식노드 -> 루트 노드 -> 오른쪽 자식노드 
1. A에서 왼쪽 자식노드인 B 방문했는데 B도 왼쪽 자식노드가 있으므로 가장 왼쪽 자식노드인 C부터 처음에 방문.
2. C는 왼쪽 자식노드가 없으므로 루트 노드인 D방문, 다음으로 오른쪽 자식노드인 D방문.
3. D를 방문한 후 더이상 방문할 노드가 없으므로, A루트로 돌아와서 방문.
4. A에서 왼쪽 자노드를 이미 다 방문했으니 오른쪽 자식노드인 E로 가서 왼쪽 자식노드인 F 방문.
5. F 방문 후, 루트 노드인 E로 돌아가서 방문 후 , 오른쪽 자식노드인 G 방문.  

코드 예시 

def inorder(self):
    def _inorder(node):
        if node.left:
            _inorder(node.left)
        print(node.item, end=' ')
        if node.right:
            _inorder(node.right)
    _inorder(self.root)

 

✌☝ 후위 순회 

왼쪽 자식노드 -> 오른쪽 자식노드 -> 루트 노드 
1. A에서 왼쪽 자식 노드 끝까지 내려가서 C부터 방문.
2. 왼쪽 자식노드 C 방문 후 오른쪽 자식노드 D 방문. 
3. 루드 노드인 B 방문.
4. A의 기준에서 왼쪽 자식 노드 다 방문 하였으니 오른쪽 자식노드 방문하러 감. E의 왼쪽 자식노드 F부터 방문.
5. 왼쪽 자식 노드 F 방문 후 오른쪽 자식노드 G방문.
6. 루트 노드 E 방문 후 A 루트 노드 방문.  

코드 예시

def postorder(self):
    def _postorder(node):
        if node.left:
            _postorder(node.left)
        if node.right:
            _postorder(node.right)
        print(node.item, end=' ')
    _postorder(self.root)

 

 

전체 코드 예시 

from collections import deque

class Node(object):
    def __init__(self, item):
        self.item = item
        self.left = self.right = None
        
class BinaryTree(object):
    def __init__(self):
        self.root = None
    #전위 순회
    def preorder(self):
        def _preorder(node):
            print(node.item, end=' ')
            if node.left:
                _preorder(node.left)
            if node.right:
                _preorder(node.right)
        _preorder(self.root)
    #중위 순회
    def inorder(self):
        def _inorder(node):
            if node.left:
                _inorder(node.left)
            print(node.item, end=' ')
            if node.right:
                _inorder(node.right)
        _inorder(self.root)
    #후위 순회
    def postorder(self):
        def _postorder(node):
            if node.left:
                _postorder(node.left)
            if node.right:
                _postorder(node.right)
            print(node.item, end=' ')
        _postorder(self.root)