[자료구조] Tree(트리) - 이진 트리

이진 트리(Binary Tree)는 모든 노드가 2개의 서브 트리를 가지는 트리이다. 

각 노드는 최대 2개까지의 자식노드를 가질 수 있고 그 자식노드가 공집합이어도 된다.

 

* 이진 트리의 성질

• n개의 노드, n-1개의 간선
• 높이가 h인 이진 트리에서 노드는 최대 2^h-1개 가질 수 있고, 최소 h개를 가진다.
• 노드가 n개인 이진 트리에서 높이는 최대 n까지, 최소┌log(n+1)┓를 가질 수 있다.

 

* 이진 트리의 종류

• 포화이진트리(Full Binary Tree) : 높이가 k인 이진 트리에서 2^k-1개의 노드를 가지는 트리
• 완전이진트리(Complete Binary Tree) : 높이가 k인 이진 트리에서 높이 k-1까지 노드가 모두 채워진 트리
• 기타

 

 

* 이진 트리의 표현

• 배열 이용

 

이진 트리를 배열로 표현하면 다음과 같다.

배열 인덱스가 0이 아닌 1부터 시작하며 부모와 자식 노드의 인덱스 간의 규칙이 있다.

• i의 부모 노드의 인덱스 = i/2
• i의 왼쪽 자식 노드의 인덱스 = 2i
• i의 오른쪽 자식 노드의 인덱스 = 2i + 1

 

 

• 연결 리스트 이용

 

typedef struct TreeNode {
	int data;
    	struct TreeNode *left, *right;
} TreeNode;

트리의 구조체를 하나 만들어 주면 된다.

 

---

참고

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=das135&logNo=220616042075