22. 이진트리(11-2)

이진트리

1. 이진트리의 기본 개념

2) 이진트리의 특징 

. 모든 노드들이  2개의 서브트리를 갖는 특별한 형태의 트리이며, 자료구조에서 가장 많이 쓰이는 트리구조 중의 하나이다. 

. 노드가 하나도 없는 빈 트리(empty  tree)가 될 수도 있다. 즉, 노드가 하나도 없는 빈 트리이거나 루트노드 하나로만 되어 있거나 두 개 이상의 노드로 되어 있을 때는 각 노드가 자식 노드를 최대한  2개까지만 가질 수 있는 트리를 말한다. 

.  이진트리에서  모든  노드는  왼쪽  자식  노드(left  child  node)와  오른쪽  자식노드(right  child node)를 가지고 있는데, 왼쪽 자식노드나 오른쪽 자식노드 중 하나만 가질 수도 있다. 

. 이진트리는 왼쪽 서브트리와 오른쪽 서브트리로 서브트리의 순서를 구별하지만 일반적인 트리에서는 서브트리의 순서를 구분하지 않는다. 

. 이진트리의 서브 트리들은 모두 이진트리여야 한다. 

정리  03 

트리  T가  i개의 내부정점 을 가진 완전 이진트리라면, 트리  T는  i+1개의 단말노드(잎노드)를 갖는다. 즉, 총  2i+1개의 정점을 가진다. 

[증명] 

T의 정점들은 어떤 부모의 자식인 정점들과 어떤 부모에게도 자식이 아닌 정점들로 구성된다. 

자식이 아닌 정점은 근노드(루트노드) 하나만 존재한다. 따라서 각각  2개의 자식을 갖는  i개의 내부정점이 있으므로,  2i개의 자식이 있게 된다. 그러므로  T의 정점의 총수는  2i+1이고, 잎노드의 수는  (2i+1)-i=i+1 이다. 

2) 연결리스트(linked  list)에 의한 방법 

. 노드가 구조체로 표현되고 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다. 

. 각 노드는 세 개의 필드(왼쪽 포인터, 노드의 값을 저장하는 부분, 오른쪽 포인터)로 구성. 

3. 이진트리의 순회 

이진트리의 순회(traversal) 

. 이진 트리에 속한 모든 노드들을 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것 

. 이진트리의  3가지 순회 방법 

① 전위 순회  (preorder  traversal) 방법 

② 중위 순회  (inorder  traversal) 방법 

③ 후위 순회  (postorder  traversal) 방법 

1) 전위 순회(preorder  traversal)