이진 트리

- 자료 구조 관점에서 트리의 종류는 굉장히 많은데,

  기본적으로 중요한 트리 중 하나가 바로 '이진 트리'입니다. 

 

1) 이진 트리란?

- 이진 트리란 노드가 없거나, 혹은 노드가 있는 경우 최대 2개의 노드를 가질 수 있는 트리를 의미합니다. 

  이진 트리는 최대 2개의 자식 노드를 갖기 때문에, 노드의 차수는 2입니다. 

  그리고 왼쪽에 있는 노드를 좌측 자식 노드, 오른쪽에 있는 노드를 우측 자식 노드라고 합니다. 

 

2) 이진 트리의 종류

- 그리고 모든 내부 노드가 2개의 자식 노드를 갖고, 모든 Leaf노드가 동일한 레벨을 갖는 이진 트리를 

   Perfect Binary Tree라고 합니다. 

 - Full Binary Tree는 모든 내부 노드가 2개의 자식을 가진 노드이며,

   모든 Leaf노드가 동일한 레벨을 갖지 않아도 상관 없습니다. 

- Complete Binary Tree는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있습니다. 

 

3) 간단한 이진 트리 만들기

- 우선 노드 객체가 필요한데, 노드 객체의 속성으로는 key와

  좌측 자식 노드의 참조값을 저장하는 left 변수,

  우측 자식 노드의 참조값을 저장하는 right 변수가 있습니다. 

class Node{
   int data;
   Node left;
   Node right;
}

- 그 다음 이진트리 객체의 행위로 key를 넣는다, 트리를 순회한다. 2가지 행위를 만듭니다. 

  먼저 이진트리를 구성할 때, 위에서 아래로, 좌에서 우로 키를 배치하려면, 큐를 사용해야 합니다. 

   (1) 최초로 키가 삽입되면 루트 노드가 null 값이기 때문에, 새로운 노드를 생성하고, 루트 노드로 지정합니다.  

   (2) 키가 삽입되면 큐를 이용하여, 다음에 삽입될 위치를 찾아야 하는데,  

         먼저 루트 노드를 큐에 삽입하면서 시작됩니다. 

   (3) 큐에서 노드를 꺼내서 해당 노드의 좌측 자식이 비어 있으면, 좌측 자식 노드로 배치 후 반복문을 탈출합니다. 

   (4) 또 하나의 키가 삽입되면, 루트 노드를 큐에 삽입 후, 큐에서 노드를 꺼내,

        해당 노드의 좌측 자식이 비어 있지 않으면, 좌측 자식을 큐에 삽입합니다. 

   (5) 그리고 우측 자식이 비어 있으면 우측 노드로 배치합니다.  

   (6) 그리고 노드를 이미 배치했으므로, 반복문을 탈출하여 종료합니다. 

   (7) 또 다른 키가 삽입되면, 루트 노드를 큐에 삽입 후, 큐에서 노드를 꺼내, 해당 노드의 좌측 자식이 비어 있지 않으면

        좌측 자식을 큐에 삽입합니다. 그리고 우측 자식이 비어 있지 않으면 우측 자식도 큐에 삽입합니다. 

   (8) 다시 반복문을 통해 큐가 비어 있을 때까지 큐에서 노드를 꺼낸 후,

         좌측 자식이 비어 있으면 좌측 자식에 배치 후 반복문을 탈출합니다. 

public class NormalTree{

    Node root;
    
    public void add(int key){
        Node newNode = new Node();
        newNode.key = key;
        if(null == root){
          root = newNode;
        }else{
          Queue<Node> queue = new LinkedList<>();
          queue.offer(root);
        
          while(!queue.isEmpty()){
             Node parentNode = queue.poll();
             
             if(null != parentNode.left){
                  queue.offer(parentNode.left);
             }else{
                  parentNode.left = newNode;
                  break;
             }
             
             if(null != paretNode.right){
                 queue.offer(parentNode.right);
             }else{
                parentNode.right = newNode;
                break;
             }
         }   
          
       }
   } 
        
 }

- 트리를 순회하는 행위는 삽입하는 행위와 코드가 크게 다르지 않은데,

  작성된 코드는 레벨 순회로 단계별로 트리를 위에서 아래로, 좌에서 우로 순회하는 방식입니다.

public class NormalTree{

    Node root;
    
    public void levelOrder(){
       if(null == root){
          return;
       }
       Queue<Node> queue = new LinkedList();
       
       while(!queue.isEmpty()){
           Node parentNode = queue.poll();
       
           System.out.println(parentNode.key);
           
           if(null != parentNode.left){
              queue.offer(parentNode.left);
           }
       
           if(null != parentNode.right){
              queue.offer(parentNode.right);
           }
       }
    }
       
   
        
 }

 

참고

코드라떼 자료구조