[자료구조] 트리(tree)

트리(Tree)

정점과 간선을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다

 

트리 구성요소

트리

노드(Node)	그래프의 정점
루트 노드(Root Node)	트리 구조에서 최상위에 존재하는 노드
내부 노드(Internal Node)	단말 노드가 아닌 노드
단말 노드(Leaf Node)	자식이 없는 노드
경로(edge)	노드와 노드를 연결하는 연결선
형제(sibling)	같은 부모를 가지는 노드
노드의 크기(size)	자신을 포함한 모든 노드의 개수
노드의 깊이(depth)	루트 노드로부터의 거리
노드의 레벨(level)	트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree)	하위 트리 개수
트리의 높이(height)	루트 노드에서 가장 깊숙한 깊이
보조트리(sub-tree	트리 내의 부분집합

특징

• 트리는 사이클이 없는 그래프 즉, 비순환 구조이다. -> 한 정점에서 출발해 다시 자기 자신으로 돌아오는 경로가 존재하지 않는다.
• 모든 노드는 단 하나의 부모 노드를 가진다.(루트 노드 제외)
• 노드가 N개인 트리는 항상 N-1 개의 간선을 가진다. -> 간선 = (정점 개수 - 1)

1.  

자바 코드

public class Tree {
    
    public Tree(){}

    // Node 만드는 메소드
    public Node createNode(Object data){
        Node n = new Node(data);
        return n;
    }
		
		// Node 클래스
    public class Node{

        Object data;
        Node left;
        Node right;

        public Node(Object data){
            this.data = data;
            left = null;
            right = null;
        }
				
		// 왼쪽 자식으로 삽입
        public void addLeft(Node node){
            left = node;
        }

		// 오른쪽 자식으로 삽입
        public void addRight(Node node){
            right = node;
        }
    }
		
	//위의 그림처럼 만들기
	public static void main(String[] args){

		Tree tree = new Tree();

		Node node1 = tree.createNode(1);
		Node node2 = tree.createNode(2);
		Node node3 = tree.createNode(3);
		Node node4 = tree.createNode(4);
		Node node5 = tree.createNode(5);
		Node node6 = tree.createNode(6);

		node1.addLeft(node2);
		node1.addRight(node3);
		node2.addLeft(node4);
		node2.addRight(node5);
		node3.addLeft(node6);

    }
}

트리 순회

전위 순회(Preorder)

루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리의 순서로 순회하는 방법이다.

public void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
 }
 
 
 // 1 2 4 5 3 6

중위 순회(in-order)

왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리

public void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
}

// 4 2 5 1 6 3

후위 순회(pre-order)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 노드

public void postOrder(Node node) {
     
	     if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
 }
 
 // 4 5 2 6 3 1