Tree - Java

트리란

• 비선형 자료구조 중 하나이다.
• 비선형은 말 그대로 일직선으로 나타내지 못하는 방식이며, 그 중 트리는 계층적 구조를 띄고 있다.
• ex) 조직도

구조

1. 데이터와 연결 상태를 저장할 클래스 공간(=노드) 생성
2. 각각의 노드들에 값 저장
3. 노드 간 연결 상태 정의

public class Node {
	Object data;
    Node left;
    Node right;
}

Node node1 = tree.addNode(1);
Node node2 = tree.addNode(2);
Node node3 = tree.addNode(3);
node1.addLeft(node2);
node1.addRight(node3);

 

이진 트리

• 자식 노드가 최대 2개인 트리를 이진트리라고 함.
• 순회 방법으로 전위, 중위, 후위 순회가 있음.

이진 탐색 트리 (Binary Search Tree)

• O(logn)의 시간 복잡도를 가짐.
• 이진 트리 구조로 이루어짐.
• 노드의 왼쪽 서브 트리에는 루트 노드보다 작은 값이 들어 있음
• 서브 트리 또한 이진 탐색 트리 구조이다.
• 중복된 값은 일체 없다.
• 중위 순회를 하면 오름 차순으로 숫자를 가져올 수 있다.