트리 순회에 대해 논하기

트리의 정의

• 1개 이상의 유한한 개수의 노드, 또는 vertex의 집합을 말한다.
• 루트 노드와 0개 이상의 겹치지 않는 하위 나무 구조들의 집합으로 이루어져 있다.
• 트리는 node와 edge라는 것으로 표현된다.
  • 원소가 들어있는 경우가 바로 node이며, 여기에 특정한 정보를 저장한다.
  • 그 node들 끼리 잇는 선을 edge라고 부르며 정보들간의 관계를 나타낸다.
• node, edge만큼은 아니지만 사용하는 용어가 좀 더 있다.
  • path는 edge에 의해 연결 된 node들의 집합을 말한다.
  • root node는 최상위의 노드를 말한다.
  • parent, children, siblin, grand-는 기준이 되는 것의 직계 상위, 아래층, 같은 부모의 노드 등을 정의한다.
  • leaf는 자식이 없는 node를 말한다.
  • subtree는 큰 tree에 속한 작은 tree를 말한다.
  • node의 degree는 하위 subtree의 갯수를 말한다.
  • node의 level은 root node 부터 최하위 node 까지의 중첩되지 않은 path의 node 갯수를 말한다.
• Binary Tree에 대해 알아보자.
  • 이진 트리라고 부르는 이 집합은 모든 내부 node들이 둘 이하의 자식 node를 갖는 트리이다.
  • 이 경우, 노드가 하나도 없는 공집합이거나, root node를 기준으로 왼쪽 이진나무, 오른쪽 이진나무로 이루어진 집합을 말한다.
    
    
  • Complete Binary Tree : 완전 이진트리
    • 가장 마지막 level의 node를 제외한 모든 node들이 꽉 차있어야 한다.
    • 마지막 level은 왼쪽부터 마지막 node까지 빈 칸이 없는 경우의 트리여야 한다.
      
      
  • Full Binary Tree : 포화 이진트리
    • 마지막 level까지 완전히 꽉 차 있는 이진 트리를 말한다.
      
      
      
  • 이진 트리 순회하기 : Tree Traverse
    • 전위 순회(Preorder traverse) : 주어진 뿌리, L node, R node 중 뿌리를 먼저 방문한다.
    • 중위 순회(Inorder traverse) : 왼쪽 하위 트리를 모두 방문 한 뒤 뿌리를 방문한다.
    • 후위 순회(Postorder traverse) : 하위 트리를 모두 방문 한 뒤에 뿌리를 방문한다.
    • 층별 순회(Level order traverse) : 위 쪽 node들 부터 아래 방향으로 차례로 방문 한다.

어딘가에서 가져옴

전위 순회시 경로	0 - 1 - 3 - 7 - 8 - 4 - 9 - 10 - 2 - 5 - 11 - 6
중위 순회시 경로	7 - 3 - 8 - 1 - 9 - 4 - 10 - 0 - 11 - 5 - 2 - 6
후위 순회시 경로	7 - 8 - 3 - 9 - 10 - 4 - 1 - 11 - 5 - 6 - 2 - 0
층별 순회시 경로	0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11

그렇다면 이것을 code 영역에서 구현해보도록 하자. 구현 언어는 파이썬이다.

    # left, right는 가상의 명칭을 한 것이며, 실제로는 tuple 등의 사용이 필요하다.

def preorder(node):
    if (node != tail):
        visit(node)
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if (node != tail):
        inorder(node.left)
        visit(node)
        inorder(node.right)

def postorder(node):
    if (node != tail):
        postorder(node.left)
        postorder(node.right)
        visit(node)