[자료구조] Tree

Tree 

• 나무를 거꾸로 뒤집어 놓은 형태를 의미하는 자료 구조
• 단방향 그래프이고 하나의 뿌리(root)로부터 가지가 사방으로 뻗은 형태
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 하나의 데이터 아래 여러개 데이터가 존재하는 비선형 구조
  • stack과 queue는 데이터를 순차적으로 나열시킨 선형구조 이다.

Tree 구조

• 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결
• 각 데이터를 노드(Node)라고 한다. 두 노드가 상하 관계의 계층으로 연결되면 부모/자식 관계가됨
• 연결된 상층의 노드를 부모 노드(Parent Node), 하층의 노드를 자식 노드(Child Node)라 한다. 
• 자식이 없는 노드를 리프 노드(Reaf Node)라고 한다.

 

Tree 용어

• 깊이(depth) - 루트로 부터 하위 계층의 특정 노드 까지의 깊이, 0부터 시작하여 root의 depth는 0이다.
• 레벨(level) - 같은 깊이에 있는 노드들을 레벨로 묶는다. 같은 레벨에 있는 노드를 형제 노드(Sibling Node)라 한다.
  레벨(level)은1 부터 시작하여, root의 레벨은 1이다. 
• 높이(height) - 리프노드를 기준으로 루트까지의 높이, 리프의 높이를 0으로 놓고 부모 노드는 +1씩 증가한다. 
• 서브트리(Sub Tree) - 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리

 

Tree의 실사용 예제

• 컴퓨터의 디렉토리 구조가 대표적인 예 이다. 최상위 디렉토리로 부터 여러개의 디렉토리 안에 또 디렉토리 들이 존재한다. 리눅스의 최상위 디렉토리는 '/'(root) 이다.
• 현실세계에서 가계도(시조(root)부터 자손들로 이어진다.), 토너먼트 대진표(결승(root)부터 4강,8강,16강...)   

 

JAVA로 Tree 구현

// ArrayList로 구현

import java.util.*;

public class TreeEx { 
  private String value;
  private ArrayList<TreeEx> children;

  public TreeEx() {	//전달인자가 없을 경우의 생성자
    this.value = null;
    this.children = null;
  }
  
  public (String data) {	//전달인자가 존재할 경우의 생성자
    this.value = data;
    this.children = null;
  }

  public void setValue(String data) {  
    this.value = data;
  }

  public String getValue() {      //현재 노드의 데이터를 반환
    return value;
  }
  
  public void addChildNode(TreeEx node) {
    if(children == null) children = new ArrayList<>();
    children.add(node);
  }
  
  public void removeChildNode(TreeEx node) {
    String data = node.getValue();

    if(children != null) {
      for(int i = 0; i < children.size(); i++) {
        if(children.get(i).getValue().equals(data)) {
          children.remove(i);
          return;
        }
        if(children.get(i).children != null) children.get(i).removeChildNode(node);
      }
    }
  }

  public ArrayList<TreeEx> getChildrenNode() {
    return children;
  }

  public boolean contains(String data) {      //재귀를 사용하여 값을 검색합니다.
    if(value.equals(data)) return true;

    boolean check;

    if(children != null) {
      for(int i = 0; i < children.size(); i++) {
        check = children.get(i).contains(data, false);
        if(check) return true;
      }
    }
    return false;
  }

  public boolean contains(String data, boolean check) {      //재귀를 사용하여 값을 검색합니다.
    if(value.equals(data)) return true;

    if(children != null) {
      for(int i = 0; i < children.size(); i++) {
        check = children.get(i).contains(data, check);
      }
    }
    return check;
  }
}

• addChildNode(value): 입력받은 value를 Tree에 계층적으로 추가
• removeChildNode(node): 입력받은 node를 Tree에서 삭제
• getChildrenNode(): 현재 트리에서 존재하는 children을 리턴
• contains(value): 트리에 포함된 데이터를 찾는다.