[자료구조] 트리순회 (전위, 중위, 후위)

 

트리를 순회하는 방법은 전위, 중위, 후위로 나뉜다.

전위순회(preorder traversal)

전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식이다.

중위순회(inorder traversal)

중위순회는 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식이다.

 

 

후위순회(postorder traversal)

후위순회는 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식이다.

 

 

 

 

재귀를 이용한 트리 순회

 

1. 전위순회 preorder

    // 전위 순회 (결과를 StringBuilder에 저장)
    private void preOrder(Binary node, StringBuilder result) {
        if (node == null) return;

        result.append(node.value).append(" "); // 현재 노드 값 추가
        preOrder(node.left, result); // 왼쪽 하위 트리 순회
        preOrder(node.right, result); // 오른쪽 하위 트리 순회
    }

 

2. 중위순회 inorder

   // 중위 순회 (결과를 StringBuilder에 저장)
    private void inOrder(Binary node, StringBuilder result) {
        if (node == null) return;

        inOrder(node.left, result); // 왼쪽 하위 트리 순회
        result.append(node.value).append(" "); // 현재 노드 값 추가
        inOrder(node.right, result); // 오른쪽 하위 트리 순회
    }

 

3. 후위순회 postorder

    // 후위 순회 (결과를 StringBuilder에 저장)
    private void postOrder(Binary node, StringBuilder result) {
        if (node == null) return;

        postOrder(node.left, result); // 왼쪽 하위 트리 순회
        postOrder(node.right, result); // 오른쪽 하위 트리 순회

        result.append(node.value).append(" "); // 현재 노드 값 추가
    }

 

 

재귀로 구현하면 간단하다.

근데 재귀를 사용할 때 너무 깊은 트리를 탐색하게 되면 함수의 콜스택이 많이 쌓여서 메모리가 초과할 수도 있다.

그럴때는 스택을 이용해서 순회를 구현하는 걸 고려해야한다.

 

 

스택을 이용한 트리 순회

 

1. 전위순회 preorder

   // stack으로 전위순회
    private void preOrderByStack(Binary node, StringBuilder result) {
        Deque<Binary> deque = new LinkedList<>();
        deque.push(node);
        while (!deque.isEmpty()) {
        	// stack에서 노드 하나 꺼내기
            Binary n = deque.pop();
            // 해당값 출력
            result.append(n.value).append(" ");

			// 왼쪽 오른쪽 자식이 있으면 stack에 넣기
            if(n.right != null) {
                deque.push(n.right);
            }
            if(n.left != null) {
                deque.push(n.left);
            }
        }
    }

 

2. 중위순회 inorder

   // stack으로 중위순회
    private void inOrderByStack(Binary node, StringBuilder result) {
        Deque<Binary> deque = new LinkedList<>();
        Binary now = node;

        while (now != null || !deque.isEmpty()) {
            // 왼쪽 자식이 있을 때까지 스택에 push
            while (now != null) {
                deque.push(now);
                now = now.left;
            }

            // 스택에서 노드를 pop하고 값 처리
            now = deque.pop();
            result.append(now.value).append(" ");

            // 오른쪽 자식으로 이동
            now = now.right;
        }
    }

 

3. 후위순회 postorder

    // stack으로 후위순회
    private void postOrderByStack(Binary node, StringBuilder result) {
        if (node == null) return;

        Deque<Binary> stack = new LinkedList<>();
        Deque<Binary> output = new LinkedList<>();

        stack.push(node);

        while (!stack.isEmpty()) {
            Binary current = stack.pop();
            output.push(current);

            // 왼쪽, 오른쪽 자식 순서대로 푸시
            if (current.left != null) stack.push(current.left);
            if (current.right != null) stack.push(current.right);
        }

        // 후위 순서대로 결과를 output에서 꺼내어 result에 추가
        while (!output.isEmpty()) {
            result.append(output.pop().value).append(" ");
        }
    }

 

 

 

 

 

 

 

 

 

이진탐색트리 시각화 + 전위, 중위, 후위 탐색  전체 코드

 

 

 

 

 

 

package com.example.demo;

import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Button;
import javafx.scene.control.TextField;
import javafx.scene.control.TextArea;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

import java.util.Deque;
import java.util.LinkedList;

public class HelloApplication extends Application {

    private Binary root;  // 트리의 루트 노드
    private Canvas canvas;
    private TextArea outputArea; // 출력 영역

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(Stage primaryStage) {
        // 캔버스 생성
        canvas = new Canvas(800, 600);

        // 입력 필드 및 버튼 생성
        TextField inputField = new TextField();
        inputField.setPromptText("숫자 입력");
        Button insertButton = new Button("삽입");
        Button deleteButton = new Button("삭제");
        Button preOrderButton = new Button("전위 순회"); // 전위 순회 버튼
        Button inOrderButton = new Button("중위 순회"); // 중위 순회 버튼
        Button postOrderButton = new Button("후위 순회"); // 후위 순회 버튼

        // 출력 영역 생성
        outputArea = new TextArea();
        outputArea.setEditable(false); // 출력만 가능하게 설정
        outputArea.setPromptText("결과가 여기에 표시됩니다.");

        // 버튼 이벤트
        insertButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = insert(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        deleteButton.setOnAction(e -> {
            try {
                int value = Integer.parseInt(inputField.getText());
                root = delete(root, value);
                drawTree();  // 트리 그리기
                inputField.clear();
            } catch (NumberFormatException ex) {
                inputField.setText("숫자만 입력");
            }
        });

        preOrderButton.setOnAction(e -> {
            outputArea.clear(); // 이전 출력 초기화
            StringBuilder result = new StringBuilder();
            preOrderByStack(root, result); // 전위 순회 결과를 result에 저장
            outputArea.setText(result.toString());
        });
        inOrderButton.setOnAction(e -> {
            outputArea.clear(); // 이전 출력 초기화
            StringBuilder result = new StringBuilder();
            inOrderByStack(root, result); // 중위 순회 결과를 result에 저장
            outputArea.setText(result.toString());
        });
        postOrderButton.setOnAction(e -> {
            outputArea.clear(); // 이전 출력 초기화
            StringBuilder result = new StringBuilder();
            postOrderByStack(root, result); // 후위 순회 결과를 result에 저장
            outputArea.setText(result.toString());
        });

        // 레이아웃 구성
        HBox controls = new HBox(10, inputField, insertButton, deleteButton, preOrderButton, inOrderButton, postOrderButton);
        controls.setAlignment(Pos.CENTER);

        BorderPane rootPane = new BorderPane();
        rootPane.setTop(controls);
        rootPane.setCenter(canvas);
        rootPane.setBottom(outputArea);

        Scene scene = new Scene(rootPane, 800, 700);
        primaryStage.setTitle("이진 탐색 트리 시각화");
        primaryStage.setScene(scene);
        primaryStage.show();
    }

    // 트리 그리기
    private void drawTree() {
        GraphicsContext gc = canvas.getGraphicsContext2D();
        gc.clearRect(0, 0, canvas.getWidth(), canvas.getHeight());
        drawNode(gc, root, canvas.getWidth() / 2, 50, canvas.getWidth() / 4);
    }

    // 노드 및 연결선 그리기
    private void drawNode(GraphicsContext gc, Binary node, double x, double y, double offset) {
        if (node == null) return;

        gc.setFill(Color.LIGHTBLUE);
        gc.fillOval(x - 15, y - 15, 30, 30);
        gc.setFill(Color.BLACK);
        gc.strokeOval(x - 15, y - 15, 30, 30);
        gc.fillText(String.valueOf(node.value), x - 5, y + 5);

        if (node.left != null) {
            gc.strokeLine(x, y, x - offset, y + 50);
            drawNode(gc, node.left, x - offset, y + 50, offset / 2);
        }

        if (node.right != null) {
            gc.strokeLine(x, y, x + offset, y + 50);
            drawNode(gc, node.right, x + offset, y + 50, offset / 2);
        }
    }

    // 삽입 메서드
    private Binary insert(Binary node, int value) {
        if (node == null) return new Binary(value);
        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }
        return node;
    }

    // 삭제 메서드
    private Binary delete(Binary node, int value) {
        if (node == null) return null;

        if (value < node.value) {
            node.left = delete(node.left, value);
        } else if (value > node.value) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            Binary minNode = findMin(node.right);
            node.value = minNode.value;
            node.right = delete(node.right, minNode.value);
        }
        return node;
    }

    // 최소값 찾기
    private Binary findMin(Binary node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 전위 순회 (결과를 StringBuilder에 저장)
    private void preOrder(Binary node, StringBuilder result) {
        if (node == null) return;

        result.append(node.value).append(" "); // 현재 노드 값 추가
        preOrder(node.left, result); // 왼쪽 하위 트리 순회
        preOrder(node.right, result); // 오른쪽 하위 트리 순회
    }

    // 중위 순회 (결과를 StringBuilder에 저장)
    private void inOrder(Binary node, StringBuilder result) {
        if (node == null) return;

        inOrder(node.left, result); // 왼쪽 하위 트리 순회
        result.append(node.value).append(" "); // 현재 노드 값 추가
        inOrder(node.right, result); // 오른쪽 하위 트리 순회
    }

    // 후위 순회 (결과를 StringBuilder에 저장)
    private void postOrder(Binary node, StringBuilder result) {
        if (node == null) return;

        postOrder(node.left, result); // 왼쪽 하위 트리 순회
        postOrder(node.right, result); // 오른쪽 하위 트리 순회

        result.append(node.value).append(" "); // 현재 노드 값 추가
    }


    // stack으로 전위순회
    private void preOrderByStack(Binary node, StringBuilder result) {
        Deque<Binary> deque = new LinkedList<>();
        deque.push(node);
        while (!deque.isEmpty()) {
            Binary n = deque.pop();
            result.append(n.value).append(" ");

            if(n.right != null) {
                deque.push(n.right);
            }
            if(n.left != null) {
                deque.push(n.left);
            }
        }
    }

    // stack으로 중위순회
    private void inOrderByStack(Binary node, StringBuilder result) {
        Deque<Binary> deque = new LinkedList<>();
        Binary now = node;

        while (now != null || !deque.isEmpty()) {
            // 왼쪽 자식이 있을 때까지 스택에 push
            while (now != null) {
                deque.push(now);
                now = now.left;
            }

            // 스택에서 노드를 pop하고 값 처리
            now = deque.pop();
            result.append(now.value).append(" ");

            // 오른쪽 자식으로 이동
            now = now.right;
        }
    }


    // stack으로 후위순회
    private void postOrderByStack(Binary node, StringBuilder result) {
        if (node == null) return;

        Deque<Binary> stack = new LinkedList<>();
        Deque<Binary> output = new LinkedList<>();

        stack.push(node);

        while (!stack.isEmpty()) {
            Binary current = stack.pop();
            output.push(current);

            // 왼쪽, 오른쪽 자식 순서대로 푸시
            if (current.left != null) stack.push(current.left);
            if (current.right != null) stack.push(current.right);
        }

        // 후위 순서대로 결과를 output에서 꺼내어 result에 추가
        while (!output.isEmpty()) {
            result.append(output.pop().value).append(" ");
        }
    }


    // Binary 노드 클래스
    class Binary {
        int value;
        Binary left, right;

        Binary(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
}