[면접스터디] 트리

피누·2019년 10월 5일
0

면접 스터디

목록 보기
4/4

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

profile
어려운 문제를 함께 풀어가는 것을 좋아합니다.

0개의 댓글