•
개념
◦
루트 노드를 중심으로 두 개의 서브 트리로 나뉘며, 그 서브 트리도 이진 트리인 형태다.
◦
이진 트리는 공노드도 허용하는데, 루트 노드에 자식 노드가 하나만 있더라도 나머지 자식 노드의 자리에 공노드가 있다고 생각한다.
◦
트리는 배열이나 연결리스트로 구현하는 것이 보편적이다.
▪
배열로 트리를 구현할 때는, 노드 넘버링의 용이성을 위해서 통상적으로 인덱스 1번부터 시작한다.
◦
이진 트리의 종류
▪
전체 이진 트리(Full Binary Tree) : 이진트리가 완전히 차있는 것이다.
▪
완전 이진 트리(Complete Binary Tree) : 이진트리가 왼쪽부터 차곡차곡 쌓인 것이다.
•
순회
◦
이진 트리의 모든 노드를 방문하는 것이다.
◦
종류
▪
중위 순회
•
left - root - right
▪
후위 순회
•
left - right - root
▪
전위 순회
•
root - left - right
•
구현
◦
이진 트리를 구현할 때는 배열이나 연결리스트 등을 이용하는 것이 보편적이다.
▪
이진 트리의 길이를 알고 있다면 배열, 길이를 알기 힘들다면 연결리스트가 나을 것 같다.
◦
연결리스트
public static class Node {
private T data;
private Node left;
private Node right;
public Node(T data) {
this.data = data;
}
}
C#
복사
◦
배열
char[] arr = new char[(int) Math.pow(2, 27)];
arr[1] = 'A';
C#
복사
