이진트리 레이아웃 #2

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

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

레이아웃 알고리즘

두 자식의 x축 상 간격이 2의 배수로 증가한다. y좌표는 트리 상의 깊이로 결정된다.

입출력

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

입력 예 #1

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

입력 예 #2

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

입력 예 #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 3 3
d 4 5
e 5 4
g 6 5
...

출력 예 #2

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

출력 예 #3

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

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

3개의 풀이가 있습니다.

예의 그림에서 c를 기준으로 보면.. c의 높이는 3(맨 밑을 1로 보면) c의 자식들의 x는 c를 기준으로 -2, +2 에 있다. 이는 2^(height-2)다.

  123456
1   c
2 a   e
3    d g

즉, 미리 루트의 높이를 계산하면 루트에서의 양팔의 길이를 알 수 있고, 자식들로 내려가면서 양팔의 길이는 반씩 줄여가면 된다.

이때, x는 왼쪽 오른쪽의 자식들 상황에 따라 달라지므로, 임의의 값으로 진행한 다음 후보정하는 방법을 취하거나 루트에서 맨왼쪽 자식까지의 높이 차를 기준으로 선보정할 수 있다.

다른 utility 함수들은 레이아웃#1 풀이를 참고하고.. 후보정하는 방식으로 구현한다면..

// 노드의 양팔 길이는 2^height
void tree_layout2(tree* t) {
    int height = tree_height(t);           // 높이
    layout2_(t, 0, 1, powi(2, height - 2));// 팔길이계산하여 0, 1기준으로 layout시작
    int minx = tree_leftmost(t)->x;              // 맨왼쪽 자식의 x가
    layout2_translate_x(t, 1-minx);        // 1이 되도록 translate
}

void layout2_(tree* t, int x, int y, int arm) {
    t->x = x;
    t->y = y;

    if (t->left) layout2_(t->left, x-arm, y+1, arm/2);
    if (t->right) layout2_(t->right, x+arm, y+1, arm/2);
}

void layout2_translate_x(tree* t, int dx) {
    t->x += dx;

    if (t->left) layout2_translate_x(t->left, dx);
    if (t->right) layout2_translate_x(t->right, dx);
}

tree* tree_leftmost(tree* t) {
    while (t->left) {
        t = t->left;
    }
    return t;
}

int tree_height(tree* t) {
    if (!t) return 0;
    return 1 + max(tree_height(t->left), tree_height(t->right));
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

좌측순회를 마친 뒤 L(node.x), U(node.x), R(node.r.x) 순서로 x 계산.

add = ->par,node do 
  par ? node.y = par.y + 1 : (return node)
  chd = node.val < par.val ? par.l : par.r
  chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node)
  par
end

calc_x = ->node,par,max_y do
  left_x = par.x + 2**(max_y-node.y) * (node == par.l ? -1 : 1) if par
  node.x = (node.l ? node.l.x + 2**(max_y-node.y-1) : par&.x > 0 ? left_x : 1)
  node.r.x = node.x + 2**(max_y-node.y-1) if node.r                           
end

layout = ->tree_str=gets.chop do
  Node = Struct.new(:val, :x, :y, :l, :r)
  nodes = tree_str.chars.map {|c| Node.new(c, 0, 1) }
  btree, max_y = nodes.reduce(&add), nodes.max_by(&:y).y

  trav = ->node,par=nil do
    trav[node.l, node] if node.l
    calc_x[node, par, max_y]
    puts node.values[0..2].join(" ")
    trav[node.r, node] if node.r
  end
  trav[btree]
end

Test

in_ordered =  "a 1 4\n"  + "c 3 3\n"  + "d 4 5\n"  + "e 5 4\n"  +
              "g 6 5\n"  + "k 7 2\n"  + "m 11 3\n" + "n 15 1\n" +
              "p 19 3\n" + "q 21 4\n" + "u 23 2\n"
expect{ layout["nkcmaedgupq"] }.to output(in_ordered).to_stdout

Output

cmd > layout.call
nkcmaedgupq
a 1 4
c 3 3
d 4 5
e 5 4
g 6 5
k 7 2
m 11 3
n 15 1
p 19 3
q 21 4
u 23 2
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
class BinaryTree():
    class Node():
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data
            self.depth = 1
            self.x = 0

        def child(self, node):
            if self.data == node.data:
                return
            key = 'left' if self.data > node.data else 'right'
            if self.__dict__[key] == None:
                node.depth = self.depth + 1
                self.__dict__[key] = node
            else:
                self.__dict__[key].child(node)

        def print_inorder_pos(self, x, depth):
            if self.left != None:
                self.left.print_inorder_pos(x, depth)
                self.x = self.left.x + (2 ** (depth - self.left.depth))
            else:
                self.x = 1 if x == -1 else x + (2 ** (depth - self.depth))
            print(self.data, self.x, self.depth)
            if self.right != None:
                self.right.print_inorder_pos(self.x, depth)

    def __init__(self, data):
        self.depth = 1
        self.root = None
        if data != None:
            self.set(data)

    def set(self, data):
        for x in data:
            self.add(BinaryTree.Node(x))

    def add(self, node):
        if self.root == None:
            self.root = node
        else:
            self.root.child(node)
        if node.depth > self.depth:
            self.depth = node.depth

    def print_inorder(self):
        self.root.print_inorder_pos(-1, self.depth)

bt = BinaryTree("nkcmaedgupq")
bt.print_inorder()

Python 3.5.2에서 작성하였습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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

이진트리 x 3
연관 문제

언어별 풀이 현황
전 체 x 3
기 타 x 1
ruby x 1
python x 1