이진트리의 종류와 성질.

1. 포화 이진트리

- 포화이진트리(full binary tree)는 트리의 각 레벨에 노드가 가득 차있는 이진트리.

• 높이 k의 이진트리의 노드의 수 :

2^(1-1) + 2^(2-1) + . . . + 2^(k-1) = 2^k - 1

2. 완전 이진트리

- 완전이진트리(complete binary tree) 는 높이가 k 인 트리에서 레벨1 ~ k-1까지는 노드가 모드 채워져 있고, 마지막 k 에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리. 마지막 레벨에서는 노드가 꽉차있지 않아도 되지만 중간에 빈곳이 있으면 안된다. 따라서, 포화이진트리는 완전이진 트리 이지만, 그 역은 항상 성립 X.

힙(heap) 은 완전이진트리의 대표적인 예이다.

성질 : n개의 노드를 가진 트리는 n-1개의 edge를 갖는다.

표현법 : 배열 표현법, 링크 표현법.

이진 트리의 연산

순회(traversal)

• 트리 순회를 왜할까?
  -> 트리에 속하는 모든 노드를 한 번씩 방문하여 노드의 데이터를 목적에 맞게 처리 할 수 있기 때문.

• 대충 처음부터 끝까지 하면 되지 않나?
  -> 선형 자료구조에서는 항목들이 일렬도 되어 있으니까 순회 방법이 간단하다. 그러나 트리에서는 단순 하지 않다.

• 그럼 어떻게 순회하나?
  -> 이진트리의 표준순회는 3가지 방법이 있다.

1. 전위순회(preorder traversal)

순서 : 루트 -> 왼쪽 -> 오른쪽

def preorder(n):
	if n is not None:
    	print(n,data, end=" ")
        preorder(n.left)
        preprder(n.right)

2. 중위순회(inorder traversal)

순서 : 왼쪽 -> 루트 -> 오른쪽

def inorder(n):
	if n is not None:
        inorder(n.left)
        print(n,data, end=" ")
        inprder(n.right)

3. 후위순회(postorder traversal)

순서 : 왼쪽 -> 오른쪽 -> 트리

def postorder(n):
	if n is not None:
        postorder(n.left)
        postprder(n.right)
        print(n,data, end=" ")

• 어떤 순회 방법을 써야 되는 건가?
  -> 순서 상관 없으면 아무거나 써도된다.

• 후위순회 : 자식노드 처리하고, 부모노드 처리.
• 전위순회 : 부모노드 처리하고, 자식노드 처리.