07-03 이진 트리(Binary Tree)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

1.이진 트리(Binary Tree)

 1)정의

  -트리의 노드가 두 개의 자식까지만 가질 수 있는 트리.

  -이진 트리 노드의 자식노드는 0,1,2 중에 하나다.

 2)종류 및 용어

  -포화 이진 트리(Full Binary Tree) :잎 노드를 제외한 모든 노드가 2개의 자식 노드를 가지고 있는 트리

  -높이 균형 트리(Height Balanced Tree):뿌리 노드를 기준으로 왼쪽과 오른쪽 트리간의 높이가 2이상

   차이 나지 않는 트리.

  -완전 높이 균형 트리(Completely Height Balanced Tree):뿌리 노드를 기준으로 왼쪽과 오른쪽 트리간의

   높이가 같은 트리.

2.이진트리의 순회(Traversal)

 1)정의

   -트리 안에서 노드 사이를 이동하는 연산.

 2)종류

   -전위순회(Preorder Traversal): [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회

   -중위순회(Inorder Traversal): [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회

 

 

   -후위순회(Postorder Traversal):[왼쪽 자식 - 오른쪽 자식 - 루트]순으로 순회.