class BinaryTree():
    class Node():
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data

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

        def print_inorder_pos(self, x, y):
            if self.left != None:
                x = self.left.print_inorder_pos(x, y + 1)
            print(self.data, x, y)
            x+=1
            if self.right != None:
                x = self.right.print_inorder_pos(x, y + 1)
            return x

    def __init__(self, data):
        self.root = None
        self.node_list = []
        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)

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

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

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

문자열 입력을 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;
}

Ruby

nodes.reduce(add(parent, node))로 btree 생성. trav(btree)로 순회, x 계산, 순회한 node 출력.

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

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

  trav = ->node do
    trav[node.l] if node.l
    node.x = cnt+=1
    puts node.values[0..2].join(" ")
    trav[node.r] if node.r
  end
  trav[btree]
end

Test

in_ordered = "a 1 4\n" + "c 2 3\n"  + "e 3 6\n"  + "g 4 5\n" + 
             "h 5 4\n" + "k 6 2\n"  + "m 7 3\n"  + "n 8 1\n" + 
             "p 9 3\n" + "q 10 5\n" + "s 11 4\n" + "u 12 2\n"
expect{ layout["nkcmahgeupsq"] }.to output(in_ordered).to_stdout

Output

cmd > layout.call
nkcmahgeupsq 
a 1 4
c 2 3
e 3 6
g 4 5
h 5 4
k 6 2
m 7 3
n 8 1
p 9 3
q 10 5
s 11 4
u 12 2

C(99)

gcc -std=c99 -pedantic-errors -W -Wall

#include <stdio.h>
#include <stdlib.h>

/* 구조체 정의 */
typedef struct _data
{
    char alpha; // 영문자
    int x, y; // x, y 좌표
} Data;

typedef struct _bstNode
{
    Data * data;
    struct _bstNode * left;
    struct _bstNode * right;
} BSTnode; // Binary Search Tree node

/* 함수 포로토타입 */
// BST 형태를 유지하며 삽입
void bst_insert(BSTnode ** root, Data * data);
// inorder 순회
void bst_traverse(BSTnode * root);
// 메모리 해제
void bst_free(BSTnode * root);
// 문자열을 BST로 변환
BSTnode * str_to_bst(const char * str);

/* 메인 */
int main(void)
{
    const char * str = "nkcmahgeupsq";

    BSTnode * root = str_to_bst(str);
    bst_traverse(root);

    bst_free(root);
    return 0;
}

/* 함수 정의 */
void bst_insert(BSTnode ** root, Data * data)
{
    BSTnode * parent = NULL;
    BSTnode * cursor = *root;
    BSTnode * new_node = malloc(sizeof (BSTnode));
    int level = 1;

    while (cursor != NULL)
    {
        parent = cursor;
        if (data->alpha < cursor->data->alpha)
            cursor = cursor->left;
        else
            cursor = cursor->right;
        level++; // 다음 레벨로 넘어감
    }

    data->y = level; // data의 레벨설정
    new_node->data = data;

    if (parent != NULL)
    {
        if (data->alpha < parent->data->alpha)
            parent->left = new_node;
        else
            parent->right = new_node;
    }
    else // 루트일때
        *root = new_node;
}

void bst_traverse(BSTnode * root)
{
    static int xpos = 1;
    if (root == NULL)
        return;

    bst_traverse(root->left);
    root->data->x = xpos++; // data의 x좌표 설정
    printf("%c %d %d \n", root->data->alpha, root->data->x, root->data->y); 
    bst_traverse(root->right);
}

void bst_free(BSTnode * root)
{
    if (root == NULL)
        return;

    bst_free(root->left);
    bst_free(root->right);
    free(root->data);
    free(root);
}

BSTnode * str_to_bst(const char * str)
{
    BSTnode * root = NULL; // 초기화

    while (*str)
    {
        Data * tmp = malloc(sizeof (Data));
        tmp->alpha = *str++;
        bst_insert(&root, tmp);
    }

    return root;
}

#include <iostream>
#include <vector>

using namespace std;

char word[] = {"nkcmahgeupsq"};

struct element
{
    int word; // a char extracted from "nkcmahgeupsq"
    int y;    // the value of y coordinate
    element(int a, int b) : word(a), y(b){}
};

int main ()
{
    int i,j,x,y;
    vector < element > bin_array;

    for(i=0,y=0; i< (sizeof(word) / sizeof(word[0]))-1; i++)
    {   
        for(j=i-1,x=0; j>=0; j--)
        {
            if((int)word[i] > (int)bin_array[j].word)  // find the value of x coordinate
            {
                x=j+1;
                break;
            }
        }
        if((bin_array.size() > x) && (bin_array[x-1].y < bin_array[x].y))//find the value of y coordinat
            y = bin_array[x].y + 1;
        else if(bin_array.size() != 0)
            y = bin_array[x-1].y +1; 

        bin_array.insert(bin_array.begin()+x, element((int)word[i],y));  // insert a result
    }   
    for(i=0; i< (sizeof(word) / sizeof(word[0]))-1; i++)  // print results
        cout<<(char)bin_array[i].word<<" "<<i+1<<" "<<bin_array[i].y+1<<endl;
    return 0;
}

Python 3으로 풀었습니다. 입력 #1, 출력 #1을 풀었습니다.

class Tree:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def make_tree(s):
    S = []
    prev = None
    for c in s:
        if c == ')':
            if prev == ',':
                S.append(None)
            r = S.pop(-1)
            l = S.pop(-1)
            S[-1].right = r
            S[-1].left = l
        elif c == ',':
            if prev == '(':
                S.append(None)
        elif c != '(':
            S.append(Tree(c))
        prev = c
    return S[0]

def inorder(node, h=1, L=[]):
    if node is not None:
        inorder(node.left,  h + 1, L)
        L.append((node.data, h))
        inorder(node.right, h + 1, L)
        return L
    return None

L = inorder(make_tree('n(k(c(a,h(g(e,),)),m),u(p(,s(q,)),))'))
for i in range(len(L)):
    print("%s %d %d" % (L[i][0], i+1, L[i][1]))

def trav(idx, depth):
    global inorder
    if idx >= len(btree) or btree[idx] == '.':
        return

    trav(idx * 2, depth + 1)
    inorder += 1
    print(btree[idx], inorder, depth)
    trav(idx * 2 + 1, depth + 1)

btree = " nkucmp.ah...s....g.......q.........e"
inorder = 0
trav(1, 1)

C#

입력은 배열로 바로 저장하고 출력은 inorder입니다.

using static System.Console;

class VersionComparison
{
    // idx 0은 사용 안 함
    // idx 1부터 왼쪽=idx*2, 오른쪽=idx*2+1, 부모=floor(idx/2)
    static char[] btree = " nkucmp.ah...s....g.......q.........e".ToCharArray();
    static int inorder = 0;

    static void trav(int idx, int depth)
    {
        if (idx >= btree.Length || btree[idx] == '.') 
        {
            return;
        }

        trav(idx * 2, depth + 1);
        inorder++;
        WriteLine("{0} {1} {2}", btree[idx], inorder, depth);
        trav(idx * 2 + 1, depth + 1);
    }

    static void Main(string[] args)
    {
        trav(1, 1);
    }
}

from string import ascii_letters

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

    def in_order_trav(self, queue = [], depth = 1):
        if self.left:
            self.left.in_order_trav(queue, depth + 1)
        queue.append((self, depth))
        if self.right:
            self.right.in_order_trav(queue, depth + 1)
        return queue

class table:
    def __init__(self, queue:[(node, int),]):
        self.max_height = max(queue[i][1] for i in range(len(queue)))
        self.table = []
        for i in range(self.max_height):
            self.table.append(list(' ' * len(queue)))
        for x, (item, height) in enumerate(queue):
            self.table[height-1][x] = item.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):
        print(i)
        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 = input()
    _in = 'n(k(c(a,h(g(e,),)),m),u(p(,s(q,)),))'
    root = make_tree(_in)

    queue = root.in_order_trav()
    tb = table(queue)
    print(tb)

파이썬 3.6.2 64

파이썬 3.6

"""
아이디어>
 1) 최상단 parent 위치 기준으로 nod를 왼쪽 부분, 오른쪽 부분에서 하단으로 이동하며 각 nod들의 위치를 찾습니다.(depth 증가시 y좌표 증가, 좌측 우측 이동시 x좌표 -+1)
 2) 먼저 좌측 부분 nod부터 입력받은 값(tmp)의 요소 위치와 x좌표 방향으로 sort된 값(tmp_2)에서 해당 요소 위치를 비교하여, 좌측이동인지 우측이동인지 판단 합니다.
 3) tmp값의 현재 요소의 tmp_2에서 위치(인덱스)값이 이전 요소의 tmp_2에서의 위치값보다 작으면 좌측이동, 크면 우측이동 입니다.
 4) tmp의 현재 요소의 (위치값+1)이 tmp_2에서 최상단 parent 요소의 위치값과 같으면 최상단 parent 위치 기준으로 우측 부분 nod들에 대한 위치를 검색합니다.
"""
def binarytree(data):
    tmp = list(data)
    tmp_2 = sorted(tmp)
    x,nod,depth,y_value = [i+1 for i in range(len(tmp_2))],[],0,[]
    start = tmp_2.index(tmp[0])
    for i,value in enumerate(tmp):
        if i == start+1:
            depth = 1
        if tmp_2.index(value) < start and tmp_2.index(tmp[i-1]) > tmp_2.index(value):
            depth += 1
        elif tmp_2.index(value) < start and tmp_2.index(tmp[i-1]) < tmp_2.index(value):
            pass
        elif tmp_2.index(value) > start and tmp_2.index(tmp[i-1]) > tmp_2.index(value):
            depth += 1
        elif tmp_2.index(value) > start and tmp_2.index(tmp[i-1]) < tmp_2.index(value):
            if tmp_2.index(tmp_2[-1]) < tmp_2.index(value):
                pass
            else:
                depth += 1
        nod.append(["%2s"%value,str(tmp_2.index(value)+1),str(depth+1)])
        y_value.append(depth+1)
    nod.sort()
    for i in nod:
        print(' '.join(i))
    print("\n")
    tree = [ ["%2s"%' ' for i in range(max(x))] for i in range(max(y_value))]
    for i,value_i in enumerate(tree):
        for h,value_h in enumerate(value_i):
            for g in nod:
                if i+1 == int(g[2]) and h+1 == int(g[1]):
                    tree[i][h] = g[0]
    x = [ str("%2d"%i) for i in x ]
    print("  "+' '.join(x))
    for i,value_i in enumerate(tree):
        print(str(i+1)+' '+' '.join(value_i))

if __name__ == "__main__":
    data = input('')
    binarytree(data)

*결과값

nkcmahgeupsq
 a 1 4
 c 2 3
 e 3 6
 g 4 5
 h 5 4
 k 6 2
 m 7 3
 n 8 1
 p 9 4
 q 10 6
 s 11 5
 u 12 3


   1  2  3  4  5  6  7  8  9 10 11 12
1                       n            
2                 k                  
3     c              m              u
4  a           h           p         
5           g                    s   
6        e                    q      

파이썬 3.6

"""
아이디어>
 1) 최상단 parent 위치 기준으로 nod를 좌측 부분, 우측 부분에서 하단으로 이동하며 각 nod들의 위치를 찾습니다.(depth 증가시 y좌표 증가, 좌측 우측 이동시 x좌표 -+1)
 2) 먼저 좌측 부분 nod부터 입력받은 값(tmp)의 요소 위치와 x좌표 방향으로 sort된 값(tmp_2)에서 해당 요소 위치를 비교하여, 좌측이동인지 우측이동인지 판단 합니다.
 3) tmp값의 현재 요소의 tmp_2에서 위치(인덱스)값이 이전 요소의 tmp_2에서의 위치값보다 작으면 좌측이동, 크면 우측이동 입니다.
 4) tmp의 현재 요소의 (위치값+1)이 tmp_2에서 최상단 parent 요소의 위치값과 같으면 최상단 parent 위치 기준으로 우측 부분 nod들에 대한 위치를 검색합니다.
"""
def binarytree(data):
    tmp = list(data)
    tmp_2 = sorted(tmp)
    x,nod,depth,y_value = [i+1 for i in range(len(tmp_2))],[],0,[]
    start = tmp_2.index(tmp[0])
    for i,value in enumerate(tmp):
        if i == start+1:
            depth = 1
# 최상위 nod 기준 좌측 부분 / 좌측 이동
        if tmp_2.index(value) < start and tmp_2.index(tmp[i-1]) > tmp_2.index(value):
            depth += 1
# 우측 이동
        elif tmp_2.index(value) < start and tmp_2.index(tmp[i-1]) < tmp_2.index(value):
            pass
# 최상위 nod 기준 우측 부분 / 우측 이동
        elif tmp_2.index(value) > start and tmp_2.index(tmp[i-1]) > tmp_2.index(value):
            depth += 1
# 좌측 이동
        elif tmp_2.index(value) > start and tmp_2.index(tmp[i-1]) < tmp_2.index(value):
            if tmp_2.index(tmp[i-2]) < tmp_2.index(value):
                pass
            else:
                depth += 1
        nod.append(["%2s"%value,str(tmp_2.index(value)+1),str(depth+1)])
        y_value.append(depth+1)
    nod.sort()
    for i in nod:
        print(' '.join(i))
    print("\n")
    tree = [ ["%2s"%' ' for i in range(max(x))] for i in range(max(y_value))]
    for i,value_i in enumerate(tree):
        for h,value_h in enumerate(value_i):
            for g in nod:
                if i+1 == int(g[2]) and h+1 == int(g[1]):
                    tree[i][h] = g[0]
    x = [ str("%2d"%i) for i in x ]
    print("  "+' '.join(x))
    for i,value_i in enumerate(tree):
        print(str(i+1)+' '+' '.join(value_i))

if __name__ == "__main__":
    data = input('')
    binarytree(data)

*결과값

nkcmahgeupsq
 a 1 4
 c 2 3
 e 3 6
 g 4 5
 h 5 4
 k 6 2
 m 7 3
 n 8 1
 p 9 3
 q 10 5
 s 11 4
 u 12 2


   1  2  3  4  5  6  7  8  9 10 11 12
1                       n            
2                 k                 u
3     c              m     p         
4  a           h                 s   
5           g                 q      
6        e                             

노드가 한글자가 아닌경우를 위해 예제의 경우 n ( k ( c ( a , h ( g ( e , ) , ) ) , m ) , u ( p ( , s ( q , ) ) , ) ) 이렇게 입력하면 원하는 결과가 나옵니다.

def binarytree(a):
    result = list()
    def depth(a, i):
        if a[i] == '(' or a[i] == ')' or a[i] == ',':
            return 0
        else:
            result = a[:i].count('(') - a[:i].count(')') + 1
        return result
    def node(a):
        result = list()
        for i in range(len(a)):
            if a[i] != '(' and a[i] != ')' and a[i] != ',':
                result.append(i)
        return result
    def parent(a, i):
        if i == 0:
            return
        elif a[i-1] == '(':
            return i-2
        else:
            c = depth(a, i)
            for j in range(i-1,-1, -1):
                if depth(a, j) == c-1:
                    return j
    def place(a):
        b = node(a)
        result = [a[b[0]]]
        for i in b[1:]:
            if a[i-1] == '(':
                result.insert(result.index(a[parent(a, i)]), a[i])
            else:
                result.insert(result.index(a[parent(a, i)])+1, a[i])
        return result
    b = place(a)
    for i in b:
        result.append((i, b.index(i)+1, depth(a, a.index(i))))
    return result

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 layout(self):
        return (f'{j[0]} {j[1]+1} {i+1}' for i in range(len(self.tree))
                                         for j in self.tree[i] if j)

data = 'nkcmahgeupsq'
x = binarytreelayout(data)

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