IM

작지만 단단하게

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.
https://github.com/ejImDev/data_structure_study.git

이진트리의 연산

  • 이진트리에서 수행되는 기본 연산들은 트리를 순회하며 이루어진다
  • 이진트리의 4가지 순회 방식 (모두 트리의 루트노드부터 시작하며, 각 노드를 반드시 1번씩 방문해야 종료됨)

  1. 전위순회
    • 전위순회는 노드 x에 도착했을 때 x를 먼저 방문
    • 그 다음에 x의 왼쪽 자식노드로 순회를 계속
    • x의 왼쪽 서브트리의 모든 노드들을 방문한 후에는 x의 오른쪽 서브트리의 모든 후손 노드들을 방문
    • 각 서브트리의 방문은 동일한 방식으로 순회
    • 전위순회 순서를 NLR 또는 VLR로 표현 (N은 노드, V는 방문, L은 왼쪽, R은 오른쪽)

  2. 중위순회
    • 중위순회는 노드 x에 도착하면 x의 방문을 보류하고 x의 왼쪽 서브트리로 순회를 진행
    • 왼쪽 서브트리의 모든 노드를 방문한 후에 x를 방문
    • x를 방문한 후에는 x의 오른쪽 서브트리를 같은 방식으로 방문
    • 중위순회 순서를 LNR 또는 LVR로 표현

  3. 후위순회
    • 후위순회는 노드 x에 도착하면 x의 방문을 보류하고 x의 왼족 서브트리로 순회를 진행
    • x의 왼쪽 서브트리를 방문한 후에는 x의 오른쪽 서브트리를 같은 방식으로 방문
    • 마지막에 x를 방문한다
    • 후위순회 순서를 LRN 또는 LRV로 표현

  4. 레벨순회

  5. 연산 메소드
    • 전위순회
      public void preorder(Node n) {
 if(n!=null) {
   System.out.print(n.getKey()+" ");
   preorder(n.getLeft());
   preorder(n.getRight());
 }
}
  • 중위순회
    public void inorder(Node n) {
  if(n!=null) {
      inorder(n.getLeft());
      System.out.print(n.getKey()+" ");
      inorder(n.getRight());
  }
}
  • 후위순회
    public void postorder(Node n) {
  if(n!=null) {
      inorder(n.getLeft());
      inorder(n.getRight());
      System.out.print(n.getKey()+" ");
  }
}
  • 레벨순회
    public void levelorder(Node root) {
Queue<Node> q = new LinkedList<>();
Node t;
q.add(root);
while (!q.isEmpty()) {
  t = q.remove();
  System.out.print(t.getKey() + " ");
  if (t.getLeft() != null) {
    q.add(t.getLeft());
  }
  if (t.getRight() != null) {
    q.add(t.getRight());
  }
}
}
  1. 기타 메소드
    • size (트리의 노드 수 계산 / 후위순회 기반) 
      public int size(Node n) {
 if(n==null) {
   return 0;
 } else {
   return (1 + size(n.getLeft()) + size(n.getRight()));
 }
}
  • height (트리의 높이 계산 / 후위순회 기반) 
    public int height(Node n) {
  if(n==null) {
      return 0;
  } else {
      return (1 + Math.max(height(n.getLeft()), height(n.getRight())));
  }
}
  • isEqual (2개의 이진트리에 대한 동일성 검사 / 전위순회 기반) 
    public static boolean isEqual(Node n, Node m) {
  if(n==null || m==null) {
      return n==m;
  }
  if (n.getKey().compareTo(m.getKey()) != 0) {
      return false;
  }
  return (isEqual(n.getLeft(), m.getLeft()) &&
          isEqual(n.getRight(), m.getRight()));
}

소요시간

각 연산은 트리의 각 노드를 한번씩 방문하므로 O(N)시간 소요

정리

  • 트리는 계층적 자료구조로서 배열이나 연결리스트의 단점을 보완하는 자료구조
  • 왼쪽자식-오른쪽형제 표현은 노드의 차수가 일정하지 않은 일반적인 트리를 구현하는 매우 효율적 자료구조
  • 포화이진트리는 각 내부노드가 2개의 자식 노드를 가지는 트리
  • 완전이진트리는 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리
  • 포화이진트리는 완전이진트리이다

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/egOXCUyjIMI

Updated: