[자료 구조] 트리 : 이진 트리

 트리는 Node와 Edge로 구성된 자료 구조로 계층적인 구조를 나타낼 때 주로 사용된다. ex) 폴더 구조, 조직도, 가계도 

하나의 노드에서 다른 노드로 이동하는 경로는 유일하며, 노드가 N개일 때 트리 전체의 엣지의 수는 N-1개이다. 또한

Cycle이 존재하지 않고,모든 노드는 서로 연결되어 있으며, 하나의 엣지를 끊으면 2개의 sub-tree가 되는 것이 특징이다.

이 중 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 특별한 형태의 트리이다. 

 

이진 트리의 종류

 

- 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리

- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

 

 

- 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

- 편향 트리(Skewed Binary Tree) : 한쪽으로 기울어진 트리

 

- 균형 이진 트리(Balaced Binary Tree) : 모든 노드의 좌우 서브 트리가 높이가 1이상 차이 나지 않는 트리

 

이진 트리의 순회

모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산

순회의 종류 4가지 

 - 전위 순회, 중위 순회, 후위 순회 - > DFS

 - 레벨 순회 -> BFS

 

⊙ 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문 (현재 노드 -> 왼쪽 노드-> 오른쪽 노드)
⊙ 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문 (왼쪽 노드 -> 현재 노드 -> 오른쪽 노드)
⊙ 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문 (왼쪽 노드 -> 오른쪽 노드 -> 현재 노드)
⊙ 레벨 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문(위쪽 레벨부터 왼쪽 노드 -> 오른쪽 노드)

  

위와 같은 트리가 있다고 한다면 각각 순회방법은 다음과 같다.

전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6 
중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6 
후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0
층별 순회 : 0->1->2->3->4->5->6->7->8->9->10->11

 

구현

 

배열로 구현

 

전위 순회 구현

void preOrder(int idx){

	int left = 2*idx + 1;
	int right = 2* idx +2;
	print(arr[idx]);
	if(left < 배열의 범위){
	
		preOrder(left);
	}

	if(rigth < 배열의 범위){
	
		preOrder(rigth);
	}
}

중위 순회 구현

 

void inOrder(int idx){

	int left = 2*idx + 1;
	int right = 2* idx +2;
	print(arr[idx]);
	if(left < 배열의 범위){
	
		inOrder(left);
	}

	if(rigth < 배열의 범위){
	
		inOrder(rigth);
	}
}

후위 순회 구현

void postOrder(int idx){

	int left = 2*idx + 1;
	int right = 2* idx +2;
	print(arr[idx]);
	if(left < 배열의 범위){
	
		postOrder(left);
	}

	if(rigth < 배열의 범위){
	
		postOrder(rigth);
	}
}

레벨 순회 구현

 

배열에서는 전체 배열을 순서대로 출력하면 됨.

 

LinkedList로 레벨 순회 구현

 

Queue 자료 구조에 노드들을 하나씩 넣으면서 노드를 뺄 때 자식 노드들을 Queue에 넣어주는 구조로 구현할 수 있다.

 

public void levelOrder(Node node){

Queue<Node> queue = new LinkedList<>();
Queue.add(node);

while(!queue.isEmyty()){
	Node cur = queue.poll();
    
    System.out.println(cur.data);
    if(cur.left !=null){
   	 queue.offer(cur.left);
     }
     
    if(cur.right !=null){
   	 queue.offer(cur.right);
     }
     }
}