1.이진트리, 완전 이진트리, 이진 탐색트리에 대해 설명하라

  • 트리는 하나의 루트를 가지고(엄밀한 그래프 이론에서는 그렇지 않지만 일반적으로 사용하는 트리는 보통 이렇다) 자식노드를 가지며 cycle이 존재하지 않는자료구조이다.
  • 이진트리는 자식노드를 최대 2개까지 가질 수 있는 트리
  • 완전 이진트리는 말단노드를 제외한 모든 노드가 2개의 자식노드를 가지고 있는 트리, 단 마지막 단계(말단노드의 부모)는 2개의 노드를 가지지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
  • 이진 탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식을 만족하는 형태의 트리이다.
  • 전 이진트리(Full BinaryTee)는 모든 노드의 자식이 없거나 정확히 두개 있는 경우를 말함

2. 중위, 후위, 전위 순회에 대한 수도코드를 작성하라

  • 중위순회
        void inOrderTraversal(Node node){
          if(node != null){
            inOrderTraversal(node.left);
            cout << node.data << "\n";
            inOrderTraversal(node.right);
          }
        }
  • 전위순회
          void preOrderTraversal(Node node){
            if(node != null){
              cout << node.data << "\n";
              preOrderTraversal(node.left);
              preOrderTraversal(node.right);
            }
          }
  • 후위순회
          void postOrderTraversal(Node node){
            if(node != null){
              postOrderTraversal(node.left);
              postOrderTraversal(node.right);
              cout << node.data << "\n";
            }
          }

3. 트리에서 사이클을 검증하는 방법에 대해 설명하라

  • DFS를 이용한 방법

      bool findCycleAlgorithm(int here) {
      if (visitied[here]) {
        if (visitied[here] == -1) {
          return true;
        }
        return false;
      }
    
      visitied[here] = -1;
      for (int there : node[here]) {
        if (findCycleAlgorithm(there)) {
          return true;
        }
      }
      visitied[here] = 1;
    
      return false;
  • Union Find 이용