Java-자료구조 5주차 Tree 4 - 7 ~ 10

5주차 Tree

4-7. 트리: 완전트리/정트리

• Complete 트리
  
  :이진트리 형태에서 자식 노드가 left->right 순으로 노드가 채워지는 트리로, 마지막 level은 완전히 채워지지 않은 형태여도 가능
  -노드의 개수 n < 2^h -1, h 는 높이

• Full 트리
  
  :이진트리 형태에서 마지막 level까지 자식 노드의 child가 2개이거나 0개인 트리
  -2 * height + 1 <= 노드의 개수 n <= 2^(height+1) - 1

Complete 트리와 Full 트리의 차이: leaf(child이 없는 노드)의 유무

+)Perfect 트리(포화 트리)

:이진트리 형태에서 마지막 level까지 자식 노드가 채워진 트리

그 외)
(Un)Blanced Tree, Binary Search Tree, Binary Tree등이 존재
생각해보기)-완전 트리와 진 트리의 공통점과 차이점은 무엇인가요?

4-8. 트리: 순회
traversal은 root,left,right로 노드가 있으면 노드를 찾아가는 방식

• 순회(traversal)의 종류: 전위/중위/후위 traversal
  순회 구분 기준) root를 언제 찾아가는가

(1) 전위 순회,Pre order traversal
순서) root -> left -> right
[응용]

모든 노드에 접근하기 전에 root를 먼저 접근한다

(2) 중위 순회,In order traversal
순서) left -> root -> right
[응용]

(주황색 영역-중위 순회)

(3) 후위 순회,Post order traversal
순서) left -> right -> root
[응용]

그 외)
너비 우선 순회(Breadth first traversal),
레벨 순서 순회(Level order traversal)
: 모두 루트에서 시작하여 모든 level에서 left->right순으로 순회하는 방법, 일부 알고리즘에 적용된다
ex)

생각해보기)-전위, 중위, 후위 순회는 반복적인 규칙을 갖고 있습니다. 이를 코드로 구현하려면 어떻게 해야 할까요? 여기서도 재귀함수 응용
코드) 참고: https://minhamina.tistory.com/83

//전위순회 Preorder : Root -> Left -> Right
public void preOrder(Node node) {
	if(node != null) {
		System.out.print(node.data + " ");
		if(node.left != null) preOrder(node.left);
		if(node.right != null) preOrder(node.right);
	}
}

//중위 순회 Inorder : Left -> Root -> Right
public void inOrder(Node node) {
	if(node != null) {
		if(node.left != null) inOrder(node.left);
		System.out.print(node.data + " ");
		if(node.right != null) inOrder(node.right);
	}
}

//후위순회 Postorder : Left -> Right -> Root
public void postOrder(Node node) {
	if(node != null) {
		if(node.left != null) postOrder(node.left);
		if(node.right != null) postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

4-9. 트리: 표현(순회 응용)

• 순회에 따라 표기할 때 달라진다
  ex1)
  
  전위 순회로 표기: 2 3
  중위 순회로 표기: 2 3
  후위 순회로 표기: 2 3 * => 일반적으로 계산기에서 많이 사용

ex2)

전위 순회로 표기: - + / 22 11 3 + 6 5 50
중위 순회로 표기: (((22 / 11) + 3) (6 + 5)) - 50
후위 순회로 표기: 22 11 / 3 + 6 5 + * 50 -

생각해보기)-복잡한 식을 후위 표기식으로 표현하였을 때의 장점은 무엇인가요?
답: 이미 입력값이 들어온 상태이므로 들어온 입력값에 대해서 찾을 필요가 없다

4-10. 트리: 노드 클래스

• 트리의 구조
  기준) parent
  parent보다 작은 데이터: left child
  parent보다 큰 데이터: right child
  => heap과 다르게 parent를 기준으로 크기 비교를 하며, 이로 인해 루트를 기준으로 비교하면 루트보다 작은 데이터는 left child쪽에, 루트보다 큰 데이터는 right child쪽에 위치

'어떤 수 찾기'를 할 때, 전체 데이터의 반은 무시되어 시간복잡도는 logn이 된다

트리에서는 parent가 될 노드에서 left와 right가 될 포인터를 가진다
+) child이 되는 노드는 parent, left, right로 포인터를 3개 가진다
형태: left-data-right

<노드 형성 코드>

class Node<E> {
	E data;
	Node <E> left, right; // 
	public Node(E obj){
		this.data = obj;
		left=right=null;
	}
}