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 回答