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

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

.

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)

from string import ascii_letters
from itertools import count

class node:
    def __init__(self, name, left = None, right = None):
        self.name = name
        self.left = left
        self.right = right

    def in_order_trav(self, counter = None, queue = {}, depth = 1):
        if counter == None:
            counter = count()
        if self.left:
            self.left.in_order_trav(counter, queue, depth + 1)
        queue[next(counter)] = (self, depth)
        if self.right:
            self.right.in_order_trav(counter, queue, depth + 1)
        return queue

    def even_number_layout_trav(self, width = 0, pos = 0, queue = {}, depth = 1):
        if width == 0:
            width = 2**(self.get_max_depth()-2)
        if self.left:
            self.left.even_number_layout_trav(width/2, pos-width, queue, depth + 1)
        queue[pos] = (self, depth)
        if self.right:
            self.right.even_number_layout_trav(width/2, pos+width, queue, depth + 1)
        return queue

    def get_max_depth(self, depth = 1):
        res = depth
        if self.left:
            res = max(res, self.left.get_max_depth(depth + 1))
        if self.right:
            res = max(res, self.right.get_max_depth(depth + 1))
        return res

    def __str__(self):
        return self.name

class table:
    def __init__(self, queue:{int:(node, int)}):
        self.max_height = max(queue[key][1] for key in queue)
        self.table = []
        for i in range(self.max_height):
            self.table.append(list(' ' * (int(max(queue) - min(queue))+1)))
        transition = 0-min(queue)
        for key in queue:
            self.table[queue[key][1]-1][int(key + transition)] = queue[key][0].name

    def __str__(self):
        res = '   ' + ' '.join('%2d'%i for i in range(1, len(self.table[0])+1)) + '\n'
        for height in range(1, self.max_height+1):
            res += '%2d '%height + ' '.join('%2s'%i for i in self.table[height-1])
            res += '\n'
        return res

def make_tree(_in):
    t_in = list(_in)
    for i in range(len(_in)-1, -1, -1):
        char = t_in[i]
        if char in ascii_letters:
            if _in[i+1] == '(':
                t_in.insert(i+2, ',')
                t_in[i], t_in[i+1] = t_in[i+1], t_in[i]
                t_in.insert(i+2, '\'')
                t_in.insert(i+1, '\'')
                t_in = t_in[:i] + list('node') + t_in[i:]
            else:
                t_in = t_in[:i] + list('node(\'') + [t_in[i], '\')'] + t_in[i+1:]

    str_in = ''.join(t_in)
    str_in = str_in.replace(',,', ', right=')
    str_in = str_in.replace(',)', ')')

    root = eval(str_in)
    return root

if __name__ == '__main__':
    in_1 = 'n(k(c(a,h(g(e,),)),m),u(p(,s(q,)),))'
    print(table(make_tree(in_1).in_order_trav()))
    in_2 = 'n(k(c(a,e(d,g)),m),u(p(,q),))'
    print(table(make_tree(in_2).even_number_layout_trav()))

1편의 코드를 수정했습니다.

파이썬 3.6.2 64

class binarytreelayout:
    def __init__(self,data=None):
        self.tree = []
        if data == None: return
        else:
            data = ''.join(j for i,j in enumerate(data) if j not in data[:i])
            tmp = sorted(data)
            item = ( [i,tmp.index(i)] for i in data )

            for node in item:
                depth,id = 0,0
                while 1:
                    if depth == len(self.tree): self.tree.append([None for i in range(2**depth)])
                    if self.tree[depth][id] == None: self.tree[depth][id] = node; break
                    if self.tree[depth][id][0] > node[0]: id = id*2
                    else: id = id*2 + 1
                    depth += 1
        return

    def layout2(self):
        tmp = 0
        lnt = 2**(len(self.tree) - 2)
        for i in range(1,len(self.tree)):
            for j,k in enumerate(self.tree[i]):
                if k:
                    k[1] = self.tree[i-1][j>>1][1] - ((-1)**j) * lnt
                    tmp = min(k[1],tmp)
            lnt >>= 1

        return (f'{j[0]} {j[1]+1-tmp} {i+1}' for i in range(len(self.tree))
                                         for j in self.tree[i] if j)

data = 'nkcmaedgupq'
x = binarytreelayout(data)

for i in sorted(x.layout2()): print(i)

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