이진트리 레이아웃 #1

이진트리를 그리기 위해 각 노드의 위치 (x,y)를 계산하는 문제다. 트리의 노드 위치를 결정하기 위한 레이아웃 알고리즘은 아래와 같다.

출처: https://sites.google.com/site/prologsite/prolog-problems/4

레이아웃 알고리즘

  • 각 노드의 x좌표는 inorder 순회 시의 위치에 해당한다.
  • 각 노드의 y좌표는 깊이에 해당한다. (루트 노드의 깊이 = 1)

입출력

트리를 생성하기 위한 입력 포맷이나, 레이아웃이 적용된 각 노드의 위치를 출력하는 형식은 자유롭게 결정한다.

입력 예 #1

"n(k(c(a,h(g(e,),)),m),u(p(,s(q,)),))"와 같이 입력받을 수 있다. parent(left,right)의 모양을 재귀적으로 표현한 것이다. (자식이 둘다 없으면 괄호부분이 생략된다.)

입력 예 #2

"nkcmahgeupsq"와 같이 입력 받아 각 글자를 노드의 라벨로 하여 이진탐색트리를 만들 수 있다.

입력 예 #3

입력을 따로 신경쓰고 싶지 않다면 코드로 직접 트리를 만들어도 된다. 만약 Java라면 다음과 같을 것이다.

class Tree<A> {
  A value;
  Tree<A> left;
  Tree<A> right;
  ...
}

Tree<String> t = new Tree("root", new Tree("left", null, null), new Tree("right", null, null));

출력 예 #1

inorder 출력으로 각 노드의 내용과 위치 (x,y)를 출력한다.

a 1 4
c 2 3
e 3 6
g 4 5
h 5 4
...

출력 예 #2

HTML/SVG/GraphViz 등으로 직접 그려도 좋을 것이다.

출력 예 #3

출력할 필요없이 테스트 코드로 확인해도 좋다.

public void test() {
  Tree<Integer> t = ...;
  Tree<Point>   expected = ...;
  assertEquals(expected, layout(t));
}
이진트리
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1개의 풀이가 있습니다.

문자열 입력을 BST방식으로 읽어 이진트리를 만들고, layout을 적용한 다음 inorder로 출력해보자.

int main(int argc, const char * argv[]) {
    tree* t = string_to_bst("nkcmahgeupsq");
    tree_layout(t);
    tree_inorder(t, print);
    tree_free(t);
    return 0;
}

트리 구조체에는 layout을 위한 x,y 필드를 추가해놓고, layout에서 이를 채운다.

typedef struct tree tree;
struct tree {
    char value;
    int x, y; // layout position
    tree* left;
    tree* right;
};

x좌표는 inorder상의 순서, y좌표는 depth이므로 x,y 위치를 기억하면서 inorder traverse하면 된다.

void layout_(tree* t, int xy[2]) {
    if (!t) return;

    xy[1]++;               // depth 증가시키고
    layout_(t->left, xy);  // 다음 자식 노드 처리
    xy[1]--;               // depth 원래대로..

    t->x = xy[0]++;        // 현재 노드의 x,y 업데이트
    t->y = xy[1];

    xy[1]++;
    layout_(t->right, xy);
    xy[1]--;
}

void tree_layout(tree* t) {
    int xy[2] = {1, 1};
    layout_(t, xy);
}

그 밖의 보조함수들 ..

// inorder 순회하면서 f 호출
void tree_inorder(tree* t, void (*f)(tree* t)) {
    if (t->left) tree_inorder(t->left, f);
    f(t);
    if (t->right) tree_inorder(t->right, f);
}

// 노드 값과 위치 출력
void print(tree* t) {
    printf("%c %d %d\n", t->value, t->x, t->y);
}

// 값으로 새 노드 만들기
tree* new_tree(char value) {
    tree* t = (tree*)malloc(sizeof(tree));
    t->value = value;
    t->x = t->y = 0;
    t->left = t->right = NULL;
    return t;
}

// tree 재귀적으로 free
void tree_free(tree* t) {
    if (t->left) tree_free(t->left);
    if (t->right) tree_free(t->right);
    free(t);
}

// bst로 tree에 값 추가하기
tree* bst_insert(tree* t, char value) {
    if (!t) return new_tree(value);
    if (value < t->value) {
        t->left = bst_insert(t->left, value);
    } else if (value > t->value) {
        t->right = bst_insert(t->right, value);
    } else {
        // duplicate
    }
    return t;
}

// 문자열을 읽어서 tree만들기
tree* string_to_bst(const char* input) {
    tree* t = NULL;
    while (*input) {
        t = bst_insert(t, *input++);
    }
    return t;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

이진트리 x 3
연관 문제

언어별 풀이 현황
전 체 x 5
python x 1
기 타 x 1
ruby x 1
cpp x 2