자료구조 - 이진트리

이진트리

---

트리

• 노드가 N개인 트리는 N - 1개의 링크를 가진다.

• 트리의 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의 두 노드간의 경로도 유일하다.

 

이진트리

• 각 노드는 최대 2개의 자식노드를 가진다.
• 종류
  1. perfect binary tree
     • 이진 트리의 모든 노드가 꽉 차있는 트리이다.
     • 높이가 h인 perfect binary tree는 2^h - 1개의 노드를 가진다.
  2. full binary tree
     • 이진 트리의 모든 노드가 0개 또는 2개의 자식을 갖는 트리이다.
  3. complete binary tree
     • 이진 트리에서 노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리이다.

• 각 노드는 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식의 주소를 저장한다.
• 노드가 N개인 full, complete binary tree의 높이는 logN이다.

 

이진트리의 순회

• 순회: 이진 트리의 모든 노드를 방문하는 일.
• 중순위 순회(Inorder)
  • 왼쪽 자식 트리 방문 -> 루트 방문 -> 오른쪽 자식 트리 방문
  • 구현 with JAVA

  public void Inorder(Node node) {
      if(node != null) {
          Inorder(node.left);
          System.out.println(node.data);
          Inorder(node.right);
      }
  }

• 선순위 순회(Preorder)
  • 루트 방문 -> 왼쪽 자식 트리 방문 -> 오른쪽 자식 트리 방문
  • 구현 with JAVA

  public void Preorder(Node node) {
      if(node != null) {
          System.out.println(node.data);
          Preorder(node.left);
          Preorder(node.right);
      }
  }

• 후순위 순회(Postorder)
  • 왼쪽 자식 트리 방문 -> 오른쪽 자식 트리 방문 -> 루트 방문
  • 구현 with JAVA

  public void Postorder(Node node) {
      if(node != null) {
          Postorder(node.left);
          Postorder(node.right);
          System.out.println(node.data);
      }
  }

• 레벨오더 순회(Level-order)
  • 레벨 순으로 방문. 동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문.
  • queue를 이용하여 구현한다.
  • 구현 with JAVA

  public void Levelorder(Node node) {
      Queue<Node> q = new LinkedList<>();
      q.add(node);
   
      while(!q.isEmpty()) {
          Node temp = q.poll();
          System.out.println(temp.data);
          if(temp.left != null) q.add(temp.left);
          if(temp.right != null) q.add(temp.right);
      }
  }

 

reference