Tree 구조 순회방식 구현해보기

Tree 구조의 3가지 순회방식 구현!

저번에 tree 구조에 대해서 막막했던 시절을 회상하며, 직접 tree를 구현하고 순회방식도 구현해보기로 했습니다!

일단 tree구조를 만들기 위해서는 Node클래스와 Tree클래스를 만들어야 겠지요?

바로 코드부터 봅시다!

class Node{    // 데이터를 저장할 노드를 담당한 클래스 Node 를 생성하여
	int data;    // int형의 데이터, 노드의 왼쪽,오른쪽 주소를 생성합니다.
	Node left;
	Node right;
}

class tree{
	public Node root;   // Node의 root를 생성하고, getter,setter를 통해 루트를 설정하는 메소드를 만듭니다.
	
	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.left=left;           // Node의 인스턴스를 생성하여 입력받은 데이터를 객체 타입으로 리턴을 해줍니다.
		node.right=right;
		node.data=data;
		return node;
	}
	
	public void inorder(Node node) {  // 중위순회  (재귀호출로 반복합니다)
		if(node != null) {  // 노드가 비어있지 않을때 까지만 반복합니다.
			inorder(node.left);            // Left-Root-Right 순서대로 진행합니다.
			System.out.println(node.data+ " -> "); // 왼쪽을 다 돌고나서 루트을 출력합니다.
			inorder(node.right);
		}
	}
	
	public void preorder(Node node) {  // 전위순회  : Root-Left-Right
		if(node != null) {
			System.out.print(node.data+ " -> ");
			preorder(node.left);
			preorder(node.right);
		}
	}
	
	public void postorder(Node node) { // 후위순회  : Left-Right-Root
		if(node != null) {
			postorder(node.left);
			postorder(node.right);
			System.out.print(node.data+ " -> ");
		}
	}
}

public class Test {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		tree t = new tree();                // tree를 생성하기 위해 인스턴스를 생성합니다.
		Node n8 = t.makenode(null, 8, null);
		Node n7 = t.makenode(null, 7, n8);
		Node n6 = t.makenode(null, 6, null); // 노드를 생성합니다.
		Node n5 = t.makenode(null, 5, null);
		Node n4 = t.makenode(null, 4, null);
		Node n3 = t.makenode(n6, 3, n7);     // 해당 노드의 데이터를 입력해주고, 왼쪽과 오른쪽에 어떤 노드가 있는지 설정해줍니다.
		Node n2 = t.makenode(n4, 2, n5);
		Node n1 = t.makenode(n2, 1, n3);
		
	// 일부로 보기 쉽게 하기위해 이진트리의 구조처럼 데이터를 삽입하고 정리했습니다 ! :)

		t.setRoot(n1);  // Root값을 설정합니다.
		t.postorder(t.getRoot());  //루트를 기준으로 후위순회를 진행합니다.
	}
}

/*         1

        2       3

      4   5    6   7

                      8
*/

// 결과 ================
// 4 -> 5 -> 2 -> 6 -> 8 -> 7 -> 3 -> 1

이번에 구현을 해보면서 데이터를 객체로 저장하는게 익숙하지 않아서

처음에 이게 뭔 코드여;;; 너무 막막했는데…

막상 개념무상하고 그냥 아 이렇게 하는구나… 하고 따라서 짜보다 보니 어? 객체를 데이터타입 으로 받아 올수도 있구나…

이걸 또 이렇게 사용해서 자료구조를 만들 수 도 있네 와….

오히려 재밌는 코딩을 하는 느낌이 들었고 이 역시 이해하기 까지 ⇒ 반나절이 걸렸다고 한다 ㅋ.