[자료구조] 자바를 이용한 트리 구현(전위순회, 중위순회, 후위순회, 레벨순회)

자바를 이용하여 트리를 생성하고 전위순회, 중위순회, 후위순회, 레벨순회를 하는 방법에 대해 알아보자 ❗

💁🏻‍ 예시에서 사용하려는 트리의 구조

---

1. 트리를 생성하기

import java.util.LinkedList;
import java.util.Queue;

class Node{
	private int data;
	private Node left;
	private Node right;
	
	public Node(int data) {
		this.data = data;
	}

	public Node(int data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
	
	public int getData() {
		return data; 
	}
	
	public Node getLeftNode() {
		return left;
	}
	
	public void setLeftNode(Node node) {
		this.left = node;
	}
	
	public Node getRightNode() {
		return right;
	}

	public void setRightNode(Node node) {
		this.right = node;
	}
	
}

class Tree{
	private Node root;
	
	public Node createNode(int data, Node left, Node right) {
		root = new Node(data);
		root.setLeftNode(left);
		root.setRightNode(right);
		
		return root;
	}

}

public class Main {

	public static void main(String[] args) {
		// 1. 트리를 생성한다.
		Tree tree = new Tree();
		
		// 2. 노드를 tree에 연결시킨다.
		Node n2 = tree.createNode(2, null, null);
		Node n5 = tree.createNode(5, null, null);
		Node n13 = tree.createNode(13, null, null);
		
		Node n4 = tree.createNode(4, n2, n5);
		Node n15 = tree.createNode(15, n13, null);
		
		Node n9 = tree.createNode(9, n4, n15);
	
	}

}

---

2. 전위(preOrder) 중위(inOrder) 후위(postOrder) , 레벨을 순회하는 메서드를 생성

package com.ssafy.tree;

import java.util.LinkedList;
import java.util.Queue;

class Node{
	private int data;
	private Node left;
	private Node right;
	
	public Node(int data) {
		this.data = data;
	}

	public Node(int data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
	
	public int getData() {
		return data; 
	}
	
	public Node getLeftNode() {
		return left;
	}
	
	public void setLeftNode(Node node) {
		this.left = node;
	}
	
	public Node getRightNode() {
		return right;
	}

	public void setRightNode(Node node) {
		this.right = node;
	}
	
}

class Tree{
	private Node root;
	
	public Node createNode(int data, Node left, Node right) {
		root = new Node(data);
		root.setLeftNode(left);
		root.setRightNode(right);
		
		return root;
	}
	
	
	// 1. 전위순회(root → Left → Right)
	public void preOrder(Node node) {
		if(node != null) {
			System.out.print(node.getData()+" ");
			preOrder(node.getLeftNode());
			preOrder(node.getRightNode());
		}
	}
	
	// 2. 중위순회(Left → root → Right)
	public void inOrder(Node node) {
		if(node != null) {
			inOrder(node.getLeftNode());
			System.out.print(node.getData()+" ");
			inOrder(node.getRightNode());
		}
	}
	
	// 3. 후위순회(Left → Right → root)
	public void postOrder(Node node) {
		if(node != null) {
			postOrder(node.getLeftNode());
			postOrder(node.getRightNode());
			System.out.print(node.getData()+" ");
		}
	}
	
	
	// 4. 레벨순회(각 노드 레벨의 순서에 따라 순회하는 방법)
	public void levelOrder(Node node) {
		
		Queue<Node> queue = new LinkedList<>();
		queue.offer(node);
		
		Node tempNode;
		while(!queue.isEmpty()) {
			tempNode = queue.poll();
			
			System.out.print(tempNode.getData()+" ");
			
			if(tempNode.getLeftNode() != null) queue.offer(tempNode.getLeftNode());
			if(tempNode.getRightNode() != null) queue.offer(tempNode.getRightNode());
		}
	}
}

public class Main {

	public static void main(String[] args) {
		// 1. 트리를 생성한다.
		Tree tree = new Tree();
		
		// 2. 노드를 tree에 연결시킨다.
		Node n2 = tree.createNode(2, null, null);
		Node n5 = tree.createNode(5, null, null);
		Node n13 = tree.createNode(13, null, null);
		
		Node n4 = tree.createNode(4, n2, n5);
		Node n15 = tree.createNode(15, n13, null);
		
		Node n9 = tree.createNode(9, n4, n15);

		// 전위순회, 중위순회, 후위순회, 레벨순회로 노드의 데이터를 탐색한다.
		
		System.out.println("1. 전위순회(root → Left → Right)");
		tree.preOrder(n9);
		
		System.out.println("\n2. 중위순회(Left → root → Right)");
		tree.inOrder(n9);
		
		System.out.println("\n3. 후위순회(Left → Right → root)");
		tree.postOrder(n9);
		
		System.out.println("\n4. 레벨순회(각 노드 레벨의 순서에 따라 순회하는 방법)");
		tree.levelOrder(n9);
		

	}

}

📌 결과

---

3. 스택을 이용하여 중위순회를 구현하기

package com.ssafy.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node{
	private int data;
	private Node left;
	private Node right;
	
	public Node(int data) {
		this.data = data;
	}

	public Node(int data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
	
	public int getData() {
		return data; 
	}
	
	public Node getLeftNode() {
		return left;
	}
	
	public void setLeftNode(Node node) {
		this.left = node;
	}
	
	public Node getRightNode() {
		return right;
	}

	public void setRightNode(Node node) {
		this.right = node;
	}
	
}

class Tree{
	private Node root;
	
	public Node createNode(int data, Node left, Node right) {
		root = new Node(data);
		root.setLeftNode(left);
		root.setRightNode(right);
		
		return root;
	}
	// 5. 스택을 사용한 중위순회(Left → root → Right)
	public void stackinOrder(Node node) {
		Stack<Node> stack = new Stack<>();
		
		while(node != null || !stack.isEmpty()) {
			while(node != null) {
				stack.push(node);
				node = node.getLeftNode();
			}
			
			node = stack.pop();
			System.out.print(node.getData()+" ");
			
			node = node.getRightNode();
		}
		
	}
}

public class Main {

	public static void main(String[] args) {
		Tree tree = new Tree();
		
		Node n2 = tree.createNode(2, null, null);
		Node n5 = tree.createNode(5, null, null);
		Node n13 = tree.createNode(13, null, null);
		
		Node n4 = tree.createNode(4, n2, n5);
		Node n15 = tree.createNode(15, n13, null);
		
		Node n9 = tree.createNode(9, n4, n15);
		
		System.out.println("\n\n5. 스택을 사용한 중위순회(Left → root → Right)");
		tree.stackinOrder(n9);
		

	}

}

📌 결과