트리(Tree)

트리(Tree)는 자료를 부모와 자식관계로 표현할 수 있는 자료구조이다. 

그 모양이 마치 나무가 자라 가지를 친 모양과 비슷하다 하여 트리라 부른다.

 

 

그래프(Graph)의 일종이기도 하고 용도나 저장하는 구조에 따라 다양한 변종들이 있다. 

다양한 변종들을 알아보기 전에 트리의 개념을 파악하고 구현해 볼 것이다. 

 

우리 주변에 트리 자료구조를 가진 것은 무엇이 있을까 ?

대표적으로 회사의 조직도를 생각해 볼수 있다.

 

그리고 탐색기나 파인터(MAC)처럼 폴더와 파일 구조도 일종의 트리이다.

 

 

컴퓨터에서 이런 트리 자료구조에 사용되는 용어(terms)는 아래와 같다.

 

 

 

• 루트(root)노드 : 최상위노드 (ex : A)
• 단말(leaf) or 터미널(terminal) 노드 : 자식노드가 없는 최하단 노드 이다. (ex : H, I, J, F, G)
• 내부(internal)노드 : root, leaf 노드가 아닌 나머지 노드들  (ex : B, D, E, C)
• 부모 (parent)- 자식(child) 노드 :  D는 H, I의 노드를 가지고 있다. 이경우 D는 H,I의 부모노드가 되고 H,I는 D의 자식노드가 된다.
• 선조(ancestor) : 선조는 바로 위의 부 모노드 뿐만 아니라 상위 레벨의 모든 부모노드,  (ex. D의 ancestor 는 B, A)
• 후손(descendant) 노드 : 후손은 바로 자식 만 아니라 모든 자식의 자식노드들을 말함 (ex, B의 descendant 는 D, E, H, I, J)
• 형제(sibling) 노드 : 부모노드가 같고 같은 레벨을 가진 노드. (ex. H, I 는 형제노드임. F,G도 형제노드)
• 레벨(level) : 루느노드가 1레벨, 그 하위 자식노드 레벨2, 그 다음 자식 레벨3 , .. LEVEL(N)
• 높이(height) : 트리의 높이는 루트로부터 가장 멀리 떨어진 노드(leaf node)와의 거리로 정의된다. =
• 차수(degree)  : 자식노드의 개수/간선(edge)수 임. ex) D의 차수는 H,I 자식노드 2개를 가지고 있기 때문에 차수는 2 이다. 
• size (크기) : 자신을 포함한 모든 자손 노드의 개수.
• depth(깊이) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 서브트리(subtree) : 그림 참고
• 포리스트(forest) :  루트노드와 연결된 간선이 없다고 할때 subtree의 집합 개념.

 

구현을 통해 개념을 더 익혀보자.

 

public class Tree<T> {
 
    public static class Node<T> {
        T data = null ; // 노드의 아이템 값.
        Node<T> parent = null ; // 부모 노드를 가리킨다.
        List<Node<T>> children = null ; // 자식 노드를 가리킨다.
 
        Node(T data) {
            this.data = data;
        }
 
        public Node(T data, Node<T> parent) {
            this.data = data;
            this.parent = parent;
        }
 
    }
 
}

 

Node 는 부모(parent)와 자식노드들(children) , 그리고 데이터를 유지하기위해 data 를 가지고 있다. 

newRootNode()는 트리의 루트노드를 생성하는 함수이다. 이제 노드를 만들었으니 자식노드를 추가하는 함수를 만들자. 

 

  public Node add(Node parent, T data) {
        Node<T> child = new Node<T>(data);
        child.parent = parent ;
        if(parent.children == null) {
            parent.children = new ArrayList<>(); // or linkedlist 로 해도 된다.
        }
        parent.children.add(child);
 
        return child;
  }

add()는 부모 노드에 자식노드를 추가하는 메소드이다. 

Node<T> child = new Node<T>(data); 로 자식노드를 생성하고 child.parent 로 부모노드를 설정한다.

그리고 부모노드의 children 이 null 이면 생성하여 생성한 자식노드를 추가해준다. 

 

여기까지 구현한것을 기준으로 맨 위의 그림과 동일한 트리를 구성해보자. 

일부러 트리 구조처럼 보이려고 들여쓰기(indent) 하였다.

    public static void main(String[] args) throws IOException {
 
        Tree tree = new Tree<String>();
 
        Tree.Node<String> root = new Tree.Node<>("A");
        Tree.Node<String> b = tree.add(root, "B");
        Tree.Node<String> d = tree.add(b, "D");
        tree.add(d, "H");
        tree.add(d, "I");
        Tree.Node<String> e = tree.add(b, "E");
        tree.add(e, "J");
        Tree.Node<String> c = tree.add(root, "C");
        tree.add(c, "F");
        tree.add(c, "G");
    }

레벨 순서 순회(Level Order Traversal)

▲ 출처 : https://en.wikipedia.org/wiki/Tree_traversal

 

레벨순회는 Queue 를 이용하여 쉽게 구현할 수 있는데 가장 상위 레벨부터 Queue 에 위 그림의 순서대로 넣고 빼면서 출력하면 된다.

▲ 출처 :  https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9

   public  void  levelOrderTraversal(Node root, Consumer<Node> consumer) {
 
        int level = 0 ;
        final Queue<Node<T>> queue = new ArrayDeque<>();
        queue.add(root);
 
        while(!queue.isEmpty()) {
            Node<T> node = queue.poll();
            consumer.accept(node);
 
            if(node.children != null && !node.children.isEmpty()) {
                Iterator iterator = node.children.iterator();
                while(iterator.hasNext()) {
                    queue.add((Node)iterator.next());
                }
 
            }
        }
    }
 

 
import java.util.function.Consumer;
 
public class Main {
 
    public static void main(String[] args) {
        Tree tree = new Tree<String>();
 
        Tree.Node<String> root = new Tree.Node<>("A");
        Tree.Node<String> b = tree.add(root, "B");
        Tree.Node<String> d = tree.add(b, "D");
        tree.add(d, "H");
        tree.add(d, "I");
        Tree.Node<String> e = tree.add(b, "E");
        tree.add(e, "J");
        Tree.Node<String> c = tree.add(root, "C");
        tree.add(c, "F");
        tree.add(c, "G");
 
        tree.levelOrderTraversal(root, new Consumer<Tree.Node>() {
            @Override
            public void accept(Tree.Node node) {
                System.out.println(String.format("data = %s", node.data));
            }
        });
    }
    
}
 

프로그램을 실행하면  A (level-0)-> B, C (level-1) -> D, E, F, G (level-2) -> H, I, J  (level-3) 순으로 출력되는 것을 확인할 수 있다.