[자료구조] Binary Tree의 3가지 순회방법

출처 : https://www.techyloud.com/why-do-students-need-help-with-a-data-structure-assignment/

 

[자료구조 알고리즘] Binary Tree의 3가지 순회방법 구현하기

본 포스팅은 위의 영상을 정리한 글로 개인 공부를 목적으로 작성되었습니다.

---

Binary Tree의 3가지 순회방법

바이너리 트리를 판단하면서 트리의 모든 데이터를 가져오는 방법에는 세 가지가 있다.

- Inorder(Left -> Root -> Right)

- Preorder(Root -> Left -> Right)

- Postorder(Left -> Right -> Root)

 

 

예제

Inorder (Left, Root, Right) : 4 2 5 1 3

1. 루트 노드를 시작으로 왼쪽으로 먼저 향한다. 

2. 더 이상 차일드 노드가 없는 4를 출력한다.

3. 왼쪽 다음 root인 2을 출력한다.

4. 오른쪽으로 가서 더이상 차일드 노드가 없으니까 5를 출력한다.

5. 더 남아있는 왼쪽의 노드가 없기 때문에 루트 노드인 1을 출력한다.

6. 남아있는 3을 출력한다.

 

 

Preorder (Root, Left, Right) : 1 2 4 5 3

1. 자기 자신인 1을 출력한다.

2. 왼쪽으로 향하고 루트 노드인 2를 출력한다.

3. 왼쪽으로 향하고 4를 출력한다.

4. 더 이상 노드가 없으니까 오른쪽으로 가서 5를 출력한다.

5. 남아있는 오른쪽의 3을 출력한다.

 

 

Postorder (Left, Right, Root) : 4 5 2 3 1

1. 왼쪽으로 먼저 향해서 더 이상 차일드가 없으니까 4를 출력한다.

2. 오른쪽으로 가서 5를 출력한다.

3. 루트 쪽으로 올라가서 2을 출력한다.

4. 루트 쪽으로 올라가서 바로 오른쪽으로 향하고 3을 출력한다.

5. 마지막으로 루트인 1을 출력한다.

 

 

 

자바로 구현하기

class Node {
    int data;
    Node left;
    Node right;
}

public class Test {

    public Node root;
    
    public void setRoot(Node node) {
    	this.root = node;
    }
    
    public Node getRoot() {
    	return root;
    }
    
    public Node makeNode(Node left, int data, Node right) {
    	Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        return node;
    }
    
    public void inorder(Node node) {
    	if (node != null) {
            inorder(node.left);
            System.out.println(node.data);
            inorder(node.right)
        }
    }
    
    public void preorder(Node node) {
    	if (node != null) {
            System.out.println(node.data);
            preorder(node.left);
            preorder(node.right);
        }
    }
    
    public void postorder(Node node) {
    	if (node != null) {
            postorder(node.left);
            postorder(node.right);
            System.out.println(node.data);
        }
    }
    
	public static void main(String[] args) {
    	Tree t = new Tree();
        Node n4 = t.makeNode(null, 4, null);
        Node n5 = t.makeNode(null, 5, null);
        Node n2 = t.makeNode(n4, 2, n5);
        Node n3 = t.makeNode(null, 3, null);
        Node n1 = t.makeNode(n2, 4, n3);
        t.setRoot(n1);
        t.inorder(t.getRoot());
        t.preorder(t.getRoot());
        t.postorder(t.getRoot());
    }
}

재귀함수를 사용해서 트리를 순회하며 노드를 출력한다.