[Java/자료구조] 트리 순회(Tree Traversal)

트리를 순회하는 방법(Tree traversal)에는 3가지 방법이 있다.

첫 번째는 전위 순회(preorder traversal), 두 번째는 중위 순회(inorder treversal), 세 번째는 후위 순회(postorder traversal)이다.

이는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다.

첫 번째로 전위 순회는 루트를 먼저 방문한 뒤 왼쪽 서브 트리, 그 다음으로 오른쪽 서브 트리를 방문한다.

두 번째로 중위 순회는 왼쪽 서브 트리를 먼저 방문하고 그 다음으로 루트와 오른쪽 서브 트리를 순서대로 방문한다.

마지막으로 후위 순회는 모든 서브 트리를 방문한 뒤, 제일 마지막에 루트를 방문하는 구조이다.

이를 Java로 구현하게 되면

이러한 트리가 있다고 가정해보자.

트리를 표현할 노드가 클래스 구조체로 표현된다.

class Node {
	int data; // 노드 값
    Node left; // 왼쪽 자식 노드 참조 값
    Node right; // 오른쪽 자식 노드 참조 값
    
    
    public Node(int data) {
    	this.data = data;
        setLeft(null);
        setRight(null);
    }
    
    public int getData() {
    	return data;
    }
    
    public Node getLeft() {
    	return left;
    }
    
    public Node getRight() {
    	return right;
    }
    
    public void setData(int data) {
    	this.data = data;
    }
    
    public void setLeft(Node left) {
    	this.left = left;
    }
    
    public void setRight(Node right) {
    	this.right = right;
    }
}

트리를 구성하기 위한 트리 클래스를 만든다.

트리 클래스를 구성하는 메서드는 아래와 같다.

1. 값을 추가하는 createNode() 메서드

2. 값이 있는지 없는지 탐색하는 contains() 메서드

3. 전위 순회(preOrder), 중위 순회(inOrder), 후위 순회(postOrder) 메서드

public class TreeOrderClass {
	public Node root; // 초기 root 는 null
    public TreeOrderClass() {
    	root = null;
    }
    
    public void createNode(int data) {
    }
    
    public boolean contains(int data){
    }
    
    public void preOrder(Node node) {
    }
    
    public void inOrder(Node node) {
    }
    
    public void postOrder(NOde node) {
    }
}

1. createNode()

트리가 생성되기 전 초기 root 값은 null이다.
root와 비교해서 값이 작으면 왼쪽 서브 트리에, 값이 크면 오른쪽 서브 트리에 값을 추가해준다.

public void createNode(int data) { // 왼쪽, 오른쪽 자식 노드가 null이며 data의 값이 저장된 새 노드 생성
    if (root == null) { // 트리가 비어있을 때
    	root = new Node;
        return;
    }	
    if (root.data == data) return; // 중복일 때 정지
    
    Node currentNode = root;
    Node parentNode = null;
    
    while (true) {
    	parentNode = currentNode;
        
        if (data < currentNode.getData()) { // 해당 노드보다 작을 경우
        	currentNode = currentNode.getLeft();
            if (currentNode == null) {
            	parentNode.setLeft(newNode);
                return;
            }
            else if (currentNode.data == newNode.data) return;
        }
        else { // 해당 노드보다 클 경우
        	currentNode = currentNode.getRight();
            if (currentNode == null) {
            	parentNode.setRight(newNode);
                return;
            }
            else if (currentNode.data == newNode.data) return;
        }
    }
}

2. contains()

public boolean contains(int data) {
	Node currentNode = root;
    while (currentNode != null) {
    	// 찾는 data값이 노드의 data와 일치하면 true 리턴
        if (currentNode.data == data) {
        	return true;
        }
        
        if (current.data > data) {
        	// 찾는 data가 노드의 data 보다 작다면, 현재 노드를 left로 변경 후 반복
        	currentNode = currentNode.left;
        }
        else {
       		// 찾는 data가 노드의 data 보다 크다면, 현재 노드를 right로 변경 후 반복
        	currentNode = currentNode.right;
        }
    }
    return false;
}

3.1. 전위 순회(preOrder())

public ArrayList<Integer> preOrder(Node root, int depth, ArrayList<Integer> list) {
	if (root != null) {
    	list.add(root.getData());
        preOrder(root.getLeft(), depth + 1, list);
        preOrder(root.getRight(), depth + 1, list);
    }
    return list;
}

3.2. 중위 순회(inOrder())

public ArrayList<Integer> inOrder(Node root, int depth, ArrayList<Integer> list) {
	if (root != null) {
        inOrder(root.getLeft(), depth + 1, list);
        list.add(root.getData());
        inOrder(root.getRight(), depth + 1, list);
    }
    return list;
}

3.3. 후위 순회(postOrder())

public ArrayList<Integer> postOrder(Node root, int depth, ArrayList<Integer> list) {
	if (root != null) {
        postOrder(root.getLeft(), depth + 1, list);
        postOrder(root.getRight(), depth + 1, list);
        list.add(root.getData());
    }
    return list;
}

이런 식으로 구현이 가능하다.

코드 자체는 간단하지만 코드의 내용을 이해하는 데는 시간이 좀 걸렸던 거 같다.

참고 사이트

https://minhamina.tistory.com/83