[240617] 트리

🔶트리

---

≣ 목차

/ 오늘의 TIL /

---

트리

이진트리

• 배열: 메모리 낭비 주의
• 포인터: 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않지만 실제 노드를 따라가도록 구현해야 하므로 구현 난이도는 배열보다 높다.
• 인접 리스트:메모리 공간이 크게 낭비되지 않고 이동할 수 있는 다음 정점을 빠르게 탐색할 수 있어 시간 복잡도 면에서 이점이 많다. 자주 이용된다.

메모리가 넉넉하다면 배열로 저장해도 괜찮다.

• 루트 노드: 배열 인덱스 1번에 저장
  • 왼쪽 자식 노드: 부모 노드 배열 인덱스 * 2
  • 오른쪽 자식 노드: 부모 노드 배열 인덱스 * 2 + 1
• 루트 노드: 배열 인덱스 0번에 저장
  • 왼쪽 자식 노드: 부모 노드 배열 인덱스 * 2 + 1
  • 오른쪽 자식 노드: 부모 노드 배열 인덱스 * 2 + 2

순회

• 전위 순회
• 중위 순회
• 후위 순회 (트리 삭제에 자주 활용됨)

public class Solution {

    public static String[] solution(int[] nodes) {
        String[] result = new String[3];
        result[0] = preorder(nodes, 0).trim(); //마지막 공백 제거
        result[1] = inorder(nodes, 0).trim(); //마지막 공백 제거
        result[2] = postorder(nodes, 0).trim(); //마지막 공백 제거
        return result;
    }

    //전위 순회
    private static String preorder(int[] nodes, int idx) {
        //idx가 범위를 벗어나면 빈 문자열 반환
        if (idx >= nodes.length) return "";

        //루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 재귀 호출하여 결과를 이어 붙임
        return nodes[idx] + " " +
                preorder(nodes, 2*idx+1) +
                preorder(nodes, 2*idx+2);
    }

    //중위 순회
    private static String inorder(int[] nodes, int idx) {
        //idx가 범위를 벗어나면 빈 문자열 반환
        if (idx >= nodes.length) return "";

        //왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리 순으로 재귀 호출하여 결과를 이어 붙임
        return inorder(nodes, 2*idx+1) +
                nodes[idx] + " " +
                inorder(nodes, 2*idx+2);
    }

    //후위 순회
    private static String postorder(int[] nodes, int idx) {
        //idx가 범위를 벗어나면 빈 문자열 반환
        if (idx >= nodes.length) return "";

        //왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드 순으로 재귀 호출하여 결과를 이어 붙임
        return postorder(nodes, 2*idx+1) +
                postorder(nodes, 2*idx+2) +
                nodes[idx] + " ";
    }

    public static void main(String[] args) {
        int[] nodes = {1,2,3,4,5,6,7};
        //["1 2 4 5 3 6 7"], ["4 2 5 1 6 3 7"], ["4 5 2 6 7 3 1"]
        String[] solution = solution(nodes);
        for (String s : solution) {
            System.out.println(s);
        }
    }
}

 

---

코딩테스트

조건에 따라 값을 증가시키고 싶을 때 (+1) 반복문

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer;
        
        for (answer = 0; a != b; answer++) {
            a = (a+1) / 2;
            b = (b+1) / 2;
        }
        return answer;
    }
}