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

8개의 풀이가 있습니다.

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

2016/12/06 15:09

Yeo HyungGoo

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

문자열 입력을 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]))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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

Python3: 바로 아래 C# 코드와 똑같은 풀이

def trav(idx, depth):
    global inorder
    if idx >= len(btree) or btree[idx] is '.':
        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)

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

풀이 작성

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

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

이진트리 x 3
연관 문제

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