트리와 이진트리

계층적인 구조를 표현

조직도, 디렉토리, 가계도

트리는 노드(node)와 링크(link)로 구성됨

맨 위의 노드는 루트(root), 노드들을 연결하는 선을 link, edge, branch라고 부름

어떤 노드 A의 아래에 노드 B가 있으면 노드 A는 B의 부모 노드이고 B는 A의 자식 노드이다.

부모가 동일한 노드는 형제(sibling) 관계이다.

루트 노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가진다.

자식이 없는 노드는 리프(leaf) 노드

서브(sub)트리 : 트리의 어떤 부분을 잘라내도 트리다.

레벨 : root 노드의 레벨을 0이라고 하면 아래로 내려갈 수록 1, 2, 3 ... n 레벨이 된다. root 노드의 레벨을 1이라고 하면 아래로 내려갈 수록 2, 3, 4, ... n이 된다.

트리의 성질

노드의 개수가 n개면 이를 연결하는 링크의 개수는 n-1이다.

경로가 중복되지 않는다는 가정하에 어떤 노드에서 루트로 가는 경로는 유일하다. 어떤 두 노드간의 경로도 유일하다.

이진 트리 (binary tree)

모든 노드의 자식이 최대 2개인 트리이다. 자식이 부모의 왼쪽 자식인지, 오른쪽 자식인지 정해져있다.

full and complete binary trees

full binary tree는 모든 자식이 2개씩 꽉 차있어야한다.

complete binary tree는 왼쪽에서부터 자식이 채워져 있다.

높이가 h인 full binary tree는 2^h-1개의 노드를 가진다. 자식은 모두 2개씩이므로 높이가 1 증가할 때마다 2의 지수승으로 노드 수가 증가한다. 그러나 루트는 2개가 아닌 1개이므로 2^h에서 1을 빼준다.

노드가 n개인 full, complete binary tree는 높이가 O(logn)이다. 가장 높아도 logn을 넘지 못한다.

이진 트리의 표현

각 노드에 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식, 부모 노드의 주소를 저장한다.

루트 노드의 주소는 따로 보관해야 한다.

이진트리의 순회 (traversal)

순회 : 이진 트리의 모든 노드를 방문하는 일

중순위(inorder), 선순위(preorder), 후순위(postorder), 레벨오더(level-order)

중, 선, 후는 루트를 기준으로 한다.

중순위 : left -> root -> right

선순위 : root -> left -> right

후순위 : left -> right -> root

root를 기준으로 트리를 방문하게 된다.

이진 트리의 inorder 순회

inorder_tree_walk(x):

  if x!=None:

    inorder_tree_walk(left[x])

    print(key[x])

    inorder_tree_walk(right[x])

preorder_tree_walk(x):

  if x!=None:

    print(key[x])

    preorder_tree_walk(left[x])

    preorder_tree_walk(right[x])

postorder_tree_walk(x):

  if x!=None:

    postorder_tree_walk(left[x])

    postorder_tree_walk(right[x])

    print(key[x])

Level-Order 순회

레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로, 큐를 이용하여 구현

level_order_tree_travaersal():

  visit the root

  Q=root

  while Q != None:

    v=dequeue(Q) #Q에서 나온 애를 v에 넣는다.

    visit child of v #v의 자식을 다 방문한다

    enqueue child of v into Q #Q에 그 자식을 넣는다.