3. 이진 트리

이진 트리

모든 노드의 차수가 2이하인 트리.

 

완전 이진 트리

 노드 수가 n개일 때 트리의 인덱스가 각각의 노드 인덱스와 일치 하는 트리. 쉽게 말하면 앞에서부터 순서대로 잘 채워진 이진 트리이다.

 

완전 이진 트리의 특성

- 부모의 인덱스 : i/2

- 좌측 자식의 인덱스 : 2*i, 우측 자식의 인덱스 2*i +1

 

- 1차원 배열로 표현

- 링크의 형태로 표현

​

---

순회

트리의 모든 노드를 방문하는 알고리즘

 

1. 전위 순회

root, left subtree, right subtree 순으로 탐색하는 알고리즘

 

2. 중위 순회

left subtree, root, right subtree 순으로 탐색하는 알고리즘

 

3. 후위 순회

left subtree, right subtree, root 순으로 탐색하는 알고리즘

 

void Tree::preorder() 
// 전체 트리를 순회하는 Driver는 Workhorse를 호출하며 
//  Driver는 Tree 클래스의 공용 멤버 함수로 선언됨. 
{ 
   preorder(root); 
} 
void Tree::preorder(Node *CurrentNode) 
// Node(이진 트리의 한 노드에 대한 포인터)를 루트로 
// 하는 서브 트리를 순회한다. Tree 클래스의 전용 멤버 함수
 // 로 선언됨. 
{  if (CurrentNode) { 
    cout << CurrentNode->data; 
    preorder(CurrentNode->LeftChild); 
    preorder(CurrentNode->RightChild); 
  } 
}