트리와 이진트리

강의 사이트

• http://www.kocw.net/home/search/kemView.do?kemId=1148815

트리와 이진트리

1. 트리 (Tree)

• 계층적인 구조를 표현

• 트리는 Node들과 노드들을 연결하는 링크(linke)들로 구성됨
• 맨 위 노드를 root라고 함.
• 부모가 동일한 노드들을 형제 관계(sibling)관계라고 부름.
• 자식이 없는 노드를 leaf 노드라고 부름
• 리프노드가 아닌 노드를 내부(internal) 노드라고 부름.
• 부모-자식 관계를 확장한 것이 조상-자손 (ancestor-descendant) 관계이다.

• 트리에서 어떤 한 노드와 그 노드 의 자손들로 이루어진 트리를 부트리(subtree)

• 레벨 : 트리의 각 층
• 높이 : 트리의 총 레벨
• 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.
• 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건하에).

2. 이진 트리(Binary Tree)

• 이진 트리에서 각 노드는 최대 2개의 자식을 가진다.

• 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자신인지가 지 정된다. (자식이 한 명인 경우에도)

2.1 Expression Tree

2.2 Huffman Code

2.3 Full and Complete Binary Trees

2.4 이진트리의 표현

3. 이진 트리의 순회

• 순회 : 이진 트리의 모든 노드를 방문하는 일
• 중순위(inoder)
• 선순위(preorder)
• 후순위(postorder)
• 레벨오더(level-order)

3.1 Inorder - 순회

3.2 Postorder와 Preorder 순회

3.3 Level - order 순회