[면접스터디] 트리

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);
        }
      }

• 전위순회

  	```java
  		void preOrderTraversal(Node node){
      if(node != null){
        cout << node.data << "\n";
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
      }
    }
  	```

• 후위순회

  	```java
  		void postOrderTraversal(Node node){
      if(node != null){
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        cout << node.data << "\n";
      }
    }
  	```

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

• DFS를 이용한 방법

  	```java
  	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 이용