[Java] 트리 구현하기 (이진트리, 전위순회, 중위순회, 후위순회)

트리 구현

 

위와 같은 형태를 갖추며 

 

각 노드는 (Data, Left, Right)의 구조체를 갖는다.

 

public static class Node {
    char data;
    Node leftNode;
    Node rightNode;

    //Node에 값 넣고 초기화
    public Node(char data) {
        this.data = data;
        this.leftNode = null;
        this.rightNode = null;
    }
}

노드의 구조체의 선언은 위와 같다.

 

이후 각 leftNode와 rightNode가 다른 노드를 가리키게끔 코드를 적용하면

 

public static class Node {
    char data;
    Node leftNode;
    Node rightNode;

    //Node에 값 넣고 초기화
    public Node(char data) {
        this.data = data;
        this.leftNode = null;
        this.rightNode = null;
    }

    //main에서 Node 생성 후 각각 붙여주기
    public void setLeftNode(Node node) {
        this.leftNode = node;
    }
    public void setRightNode(Node node) {
        this.rightNode = node;
    }
}

public static void main(String[] args) {
    Tree tree = new Tree();

    //각 노드 생성
    Node A = new Node('A');
    Node B = new Node('B');
    Node C = new Node('C');
    Node D = new Node('D');
    Node E = new Node('E');
    Node F = new Node('F');
    Node G = new Node('G');

    /*
     * 	  A
     * 	B 	C
     * D E F G
     */
    //부모노드에 자식노드 붙여주기
    A.setLeftNode(B);
    A.setRightNode(C);
    B.setLeftNode(D);
    B.setRightNode(E);
    C.setLeftNode(F);
    C.setRightNode(G);
}

위의 코드와 같이 나타낼 수 있다.

 

 

전위/중위/후위 순회

전위순회는

루트 > 왼쪽 > 오른쪽

 

중위 순회는

왼쪽 > 부모 > 오른쪽

 

후위 순회는

왼쪽 > 오른쪽 > 부모

 

위의 순서대로 탐색을 한다.

 

//전위 순회
public void preOrder(Node node) {
    if(node == null) {
        return;
    }
    System.out.print(node.data);
    preOrder(node.leftNode);
    preOrder(node.rightNode);
}

//중위 순회
public void inOrder(Node node) {
    if(node == null) {
        return;
    }
    inOrder(node.leftNode);
    System.out.print(node.data);
    inOrder(node.rightNode);
}

//후위 순회
public void postOrder(Node node) {
    if(node == null) {
        return;
    }
    postOrder(node.leftNode);
    postOrder(node.rightNode);
    System.out.print(node.data);
}

작동 방식은 재귀를 통해서 작동한다.

 

---

전체 코드

 

public class Tree {

	public static class Node {
		char data;
		Node leftNode;
		Node rightNode;
		
		//Node에 값 넣고 초기화
		public Node(char data) {
			this.data = data;
			this.leftNode = null;
			this.rightNode = null;
		}
		
		//main에서 Node 생성 후 각각 붙여주기
		public void setLeftNode(Node node) {
			this.leftNode = node;
		}
		public void setRightNode(Node node) {
			this.rightNode = node;
		}
	}
	
	//전위 순회
	public void preOrder(Node node) {
		if(node == null) {
			return;
		}
		System.out.print(node.data);
		preOrder(node.leftNode);
		preOrder(node.rightNode);
	}
	
	//중위 순회
	public void inOrder(Node node) {
		if(node == null) {
			return;
		}
		inOrder(node.leftNode);
		System.out.print(node.data);
		inOrder(node.rightNode);
	}
	
	//후위 순회
	public void postOrder(Node node) {
		if(node == null) {
			return;
		}
		postOrder(node.leftNode);
		postOrder(node.rightNode);
		System.out.print(node.data);
	}
	
	public static void main(String[] args) {
		Tree tree = new Tree();
		
		//각 노드 생성
		Node A = new Node('A');
		Node B = new Node('B');
		Node C = new Node('C');
		Node D = new Node('D');
		Node E = new Node('E');
		Node F = new Node('F');
		Node G = new Node('G');
		
		/*
		 * 	  A
		 * 	B 	C
		 * D E F G
		 */
		//부모노드에 자식노드 붙여주기
		A.setLeftNode(B);
		A.setRightNode(C);
		B.setLeftNode(D);
		B.setRightNode(E);
		C.setLeftNode(F);
		C.setRightNode(G);
		
		//전위순회
		tree.preOrder(A);
		System.out.println(); //ABDECFG
		
		tree.inOrder(A);
		System.out.println(); //DBEAFCG
		
		tree.postOrder(A);
		System.out.println(); //DEBFGCA
	}
}