이진트리 레이아웃 #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));
}
이진트리
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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에서 작성하였습니다.

2016/12/09 11:47

Yeo HyungGoo

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

Python3:

트리는 배열에 바로 저장하고, 다음과 같이 사용합니다.

.

btree[0]: 사용 안 함

btree[1]: 루트 노드

btree[x]의 왼쪽자식 = btree[x*2]

btree[x]의 오른쪽자식 = btree[x*2+1]

btree[x]의 부모 = btree[x//2]

.

그리고 편의상 깊이 대신 높이를 사용합니다.

깊이와는 반대로 가장 깊은 노드부터 0, 1, 2, 3, ... 으로 증가하며, 문제의 예시에서는 루트 노드의 높이가 4가 됩니다.

현재 노드의 깊이를 d, 트리의 최대 깊이를 D, 현재 노드의 높이를 h, 트리의 최대 깊이를 H 라고 하면 다음과 같이 변환됩니다.

h = D - d

d = H - h + 1

높이가 h인 부모 노드와 그 자식 노드 사이의 거리는 2의 (h-1)제곱이 됩니다.

from math import log, floor

def trav(idx, x, h):
    if idx >= len(btree) or btree[idx] is '.':
        return

    trav(idx*2, x - 2**(h-1), h-1)
    print(btree[idx], x, H-h+1)
    trav(idx*2+1, x + 2**(h-1), h-1)

btree = " nkucmp.ae...q....dg"
H = floor(log(len(btree) - 1, 2))  # 최대 높이(root의 높이). 
trav(1, 2**H - 1, H)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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

이진트리 x 3
연관 문제

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