파이썬 자료구조 -트리 : 전위, 중위, 후위 순회

 

전위 순회(preorder)는 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

중위 순회(inorder)는 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

후위 순회(postorder)는 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문으로 스캔한다.

 

A,B,C만 있는 트리를 가지고 설명해보면, 

전위 순회 : A->B->C

중위 순회 : B->A->C

후위 순회 : B->C->A

로 움직인다.

 

조금 더 설명해보자면

전위 순회는 가장 처음에 A를 방문,

중위 순회는 B에서 C로 가는 도중에 방문,

후위 순회는 B와 C를 방문하고 나서 A를 방문한다.

 

 

전체 트리를 보며 생각해보자.

전위 순회 : A->B->D->E->H->C->F->G->I

중위 순회 : D->B->E->H->A->F->C->I->G

후위 순회 : D->H->E->B->F->I->G->C->A

 

 

코드를 알아보자.

재귀를 사용하므로 이해하기 매우 어렵지만 찬찬히 살펴보면 조금씩 이해가 된다.

어렵다면 재귀에 대해 공부할 것을 추천한다.

 

class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

    def addLeft(self, Node):
        self.left = Node
        
    def addRight(self, Node):
        self.right = Node   

class BinaryTree:
    def __init__(self,root):
        self.root = root

    def preOrder(self,n):
      print(n.item, ' ', end=' ')
      if n.left:
        self.preOrder(n.left)
      if n.right:
        self.preOrder(n.right)

    def inOrder(self, n):
      if n.left:
        self.inOrder(n.left)
      print(n.item, ' ', end=' ')
      if n.right:
        self.inOrder(n.right)

    def postOrder(self, n):
        if n.left: 
          self.postOrder(n.left)
        if n.right: 
          self.postOrder(n.right)    
        print(n.item,' ', end=' ')

 

저번 코드에서 BinaryTree에서 순회 알고리즘을 추가한 것이다.

 

colab에서 돌려보니 결과가 옳게 나왔다.