打印出用斜槓

Question

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

我知道我非常接近答案，因爲我的顯示器距離我所需要的距離並不遙遠，而且我感覺這是一個非常簡單的解決方案，但由於某種原因，我似乎是正確的。

Answer 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)