[자바로 구현하고 배우는 자료구조] 4. 힙(Heap) & 트리(Tree) (3)

---

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

완전 트리(Complete Tree)는 잎 노드가 아닌 모든 노드가 두 개의 자식 노드를 가지고 있고, 마지막줄은 왼쪽에서 오른쪽의 순서로 꽉 차있다. 정 트리(Full Tree)는 잎 노드가 아닌 모든 노드가 두 개의 자식 노드를 가지고 있고, 모든 잎 노드가 같은 레벨이다.

 

4-8. 트리: 순회

모든 노드를 순회하는 순서를 정하는데 여러가지 방법이 있다. 루트의 순서에 따라 전위 순회(Pre-order Traversal), 중위 순회(In-order Traversal), 후위 순회(Post-order Traversal)이 있다. (루트의 순서에 따라로 정한건 내가 순회 외울 때 쓰던 방법이다)

전위 순회

- 루트로 간다.

- 왼쪽 자식으로 간다.

- 오른쪽 자식으로 간다.

전위 순회는 가장 먼저 루트를 찾는다.

EX) 루트 1 다음으로 왼쪽 자식 2로 간다. 2는 3과 6 사이의 루트 노드인 셈으로 다시 왼쪽 노드인 3으로 이동한다.

중위 순회

- 왼쪽 자식으로 간다.

- 루트로 간다.

- 오른쪽 자식으로 간다.

중위 순회는 가장 먼저 왼쪽 노드를 찾고 그 다음에 루트를 찾는다.

EX) 루트에서부터 가장 왼쪽 자식 노드 1을 찾는다. 그 다음 왼쪽 자식 노드의 부모 노드인 루트 2로 가고, 그 다음 오른쪽 노드 3으로 간다. 

후위 순회

- 왼쪽 자식으로 간다.

- 오른쪽 자식으로 간다.

- 루트로 간다.

후위 순회는 가장 먼저 왼쪽, 오른쪽 노드를 찾고 마지막으로 루트를 찾는다. 

EX) 루트에서부터 가장 먼저 왼쪽 자식 노드 1을 찾고 같은 부모 노드의 오른쪽 노드 2, 그리고 마지막으로 루트 노드 3으로 간다.

 

너비 우선 순회

- 루트 노드에서부터 아래로, 왼쪽에서 오른쪽의 순서로 간다.

 

4-9. 트리: 표현

트리를 이용하여 표현식도 표현할 수 있다. 왼쪽 트리의 경우 전위 순회를 하면 * 2 3, 중위 순회를 하면 2 * 3, 후위 순회를 하면 2 3 *이다. 전위 순회는 지우셨는데 왜 지웠는지 이유를 설명 안 해주신다. 

위 트리를 각각 중위 순회와 후위 순회를 이용하면 다음과 같다. 

- 중위 순회 : 22 / 11 + 3 * 6 + 5 - 50 = ((( 22 / 11 ) + 3 ) * ( 6 + 5 )) - 50

- 후위 순회 : 22 11 / 3 + 6 5 + * 50 -

 

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

부모 노드를 기준으로 왼쪽 자식 노드는 부모 노드보다 작아야하고, 오른쪽 자식 노드는 부모 노드보다 커야 한다. 따라서 노드를 추가할 때, 삭제할 때 왼쪽, 오른쪽 노드가 필요하기 때문에 연결리스트의 next 포인터처럼 트리의 노드도 left, right 포인터를 갖는다.

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

 

4-11. 트리: 재귀 함수

public void add(E obj, Node<E> node){
	if(((Comparable<E> obj).compareTo(node.data))>0){
    	//노드의 오른쪽 자식 노드가 null이면 오른쪽 자식 노드 자리에 추가한다.
    	if(node.right) == null{
        	node.right = new Node<E>(obj);
            return;
        }
        //노드의 왼쪽 자식 노드가 null이면 왼쪽 자식 노드 자리에 추가한다.
        if(node.left == null){
        	node.left = new Node<E>(obj);
            return;
        }
        // 재귀를 이용하여 null인 노드를 찾기위해 이동한다.
        return add(obj, node.left);
    }
}    
// add 메소드를 오버라이딩
public void add(E obj){
	if(root == null){
		root = new Node<E>(obj);
	}else{
		add(obj, root);
	}
	currentSize++;
}