0

http://pastebin.com/dN9a9xfs

これが、二分探索木の要素を出力するための私のコードです。目標は、親と各子をスラッシュで接続して、レベル順に表示することです。したがって、たとえば、シーケンス15 3 16 2 1 4 19 17 28 31 12 14 11 0は、実行後に次のように表示されます。

         15
        /  \
       3    16
      / \     \
     2   4    19
    /     \   / \
   1      12 17 28
  /      /  \     \
 0      11  14    31

私は長い間それに取り組んできました、しかし私はちょうど間隔/インデントを正しくすることができないようです。ノードを適切な順序で表示するための適切なアルゴリズムを作成したことは知っていますが、スラッシュはちょうどずれています。これは私のコードの結果です：http：//imgur.com/sz8l1

私のディスプレイは必要なものからそれほど遠くないので、私は答えに非常に近いことを知っています、そしてそれは本当に簡単な解決策だと感じていますが、何らかの理由で私はちょうどそれを正しくしているようです。

4

1 に答える 1

1

今は時間がありませんが、ここに簡単なバージョンがあります。私はあなたのコードを読んでいない(C++ を知らない) ので、私たちのソリューションがどれほど近いかわかりません。

出力形式を少し変更しました。/左のノードの代わりに使用|したので、左の間隔をまったく気にする必要はありませんでした。

15
| \
3  16
|\   \
2 4   19
|  \  | \
1   | 17 28
|   |      \
0   12      31
    | \
    11 14

これがコードです。そこから必要なものを取り出せることを願っています。あなたが使用しているものにマップしたいいくつかの Pythonisms が間違いなくあります。主なアイデアは、数値の各行をノード オブジェクトへの位置のマップとして扱い、各レベルでマップをキーで並べ替え、割り当てられた位置に基づいてコンソールに繰り返し出力することです。次に、前のレベルの親に相対的な位置を持つ新しいマップを生成します。衝突が発生した場合は、偽のノードを生成して、実際のノードを一列に並べます。

from collections import namedtuple

# simple node representation. sorry for the mess, but it does represent the
# tree example you gave.
Node = namedtuple('Node', ('label', 'left', 'right'))
def makenode(n, left=None, right=None):
    return Node(str(n), left, right)
root = makenode(
    15,
    makenode(
        3,
        makenode(2, makenode(1, makenode(0))),
        makenode(4, None, makenode(12, makenode(11), makenode(14)))),
    makenode(16, None, makenode(19, makenode(17),
                                makenode(28, None, makenode(31)))))

# takes a dict of {line position: node} and returns a list of lines to print
def print_levels(print_items, lines=None):
    if lines is None:
        lines = []
    if not print_items:
        return lines

    # working position - where we are in the line
    pos = 0

    # line of text containing node labels
    new_nodes_line = []

    # line of text containing slashes
    new_slashes_line = []

    # args for recursive call
    next_items = {}

    # sort dictionary by key and put them in a list of pairs of (position,
    # node)
    sorted_pos_and_node = [
        (k, print_items[k]) for k in sorted(print_items.keys())]

    for position, node in sorted_pos_and_node:
        # add leading whitespace
        while len(new_nodes_line) < position:
            new_nodes_line.append(' ')
        while len(new_slashes_line) < position:
            new_slashes_line.append(' ')

        # update working position
        pos = position
        # add node label to string, as separate characters so list length
        # matches string length
        new_nodes_line.extend(list(node.label))

        # add left child if any
        if node.left is not None:
            # if we're close to overlapping another node, push that node down
            # by adding a parent with label '|' which will make it look like a
            # line dropping down
            for collision in [pos - i for i in range(3)]:
                if collision in next_items:
                    next_items[collision] = makenode(
                        '|', next_items[collision])

            # add the slash and the node to the appropriate places
            new_slashes_line.append('|')
            next_items[position] = node.left
        else:
            new_slashes_line.append(' ')

        # update working position
        len_num = len(node.label)
        pos += len_num

        # add some more whitespace
        while len(new_slashes_line) < position + len_num:
            new_slashes_line.append(' ')

        # and take care of the right child
        if node.right is not None:
            new_slashes_line.append('\\')
            next_items[position + len_num + 1] = node.right
        else:
            new_slashes_line.append(' ')

    # concatenate each line's components and append them to the list
    lines.append(''.join(new_nodes_line))
    lines.append(''.join(new_slashes_line))

    # do it again!
    return print_levels(next_items, lines)

lines = print_levels({0: root})
print '\n'.join(lines)
于 2012-12-02T23:54:00.993 に答える