相対位置ですべてのルートからリーフへのパスを出力する

Question

バイナリツリーが与えられた場合、ルートをリーフパスに出力するにはどうすればよいでしょうか？

例：

Input : Root of below tree 
     A 
    / \ 
     B  C 
    /\ /\ 
    D E F G 

Output : All root to leaf paths 
_ _ A 
_ B 
D 

_ A 
B 
_ E 

A 
_ C 
F 

A 
_ C 
_ _ G 

Answer 1

あなたは木を訪問する先行順旅を使用することができます。インデントでパスを記録します。

左の子を訪問するときにインデントを減らすとき、右の子供を訪問するときインデントを大きくする。そして、あなたは

(2, A), (1, B), (0, D) 
(1, A), (0, B), (1, E) 
... 

そして、出力段階では、

(0, A), (-1, B), (-2, D) 
(0, A), (-1, B), (0, E) 
... 

ようなパスを取得し、パスを正規化し、パスノードの最小のインデントを見つけて、パスのノードへのシフトすることができますそれに応じてパスを印刷します。

はここ

def travel(node, indent, path): 
    if not node: 
     print_path(path) 
     return 
    path.append((indent, node)) 
    if node.left: 
     travel(node.left, indent - 1, path) 
    if node.right: 
     travel(node.right, indent + 1, path) 
    del path[-1] 


def print_path(path): 
    min_indent = abs(min([x[0] for x in path])) 
    for indent, node in path: 
     p = [] 
     for x in xrange(min_indent + indent): 
      p.append('_') 
     p.append(node.val) 
     print ' '.join(p) 

Answer 2

、垂直順に印刷パス上のアイデアベースのpythonのサンプルコードです。

1）私たちは、与えられたバイナリツリーの前順走査を行います。ツリーを横断しながら、水平距離またはHDを再帰的に計算することができます。最初に、水平距離を0に渡します。左サブツリーについては、水平距離をルートから1の水平距離まで引きます。右サブツリーについては、水平距離をルートの水平距離+1にします。すべてのHD値について、ベクトルのノードのリスト（ "現在のノードの水平距離とルートのキー値の情報を格納します）。）また、ノードの順序（ルートからリーフまでのパスに表示される順序）を維持します。注文を維持するため。

2）私たちはトラバース中に葉ノードに到達しながら、我々はアンダースコアでそのパスを印刷する「_」

a) First find the minimum Horizontal distance of the current path. 
b) After that we traverse current path 
    First Print number of underscore “_” : abs (current_node_HD – minimum-HD) 
    Print current node value. 

葉のパスへのすべてのルートのためにこのプロセスを実行します。

Answer 3

Qiang Jinの反応がうまくいかない。いくつかのものを切り換えました。

class Node: 
    def __init__(self, val): 
     self.value = val 
     self.right = None 
     self.left = None 


def printTreeRelativePaths(root): 
    indent = 0 
    path = [] 
    preOrder(root, indent, path) 

def preOrder(node, indent, path): 

    path.append((node, indent)) 

    if not node.left and not node.right: 
     processPath(path) 

    if node.left: 
     preOrder(node.left, indent - 1, path) 
    if node.right: 
     preOrder(node.right, indent + 1, path) 
    del path[-1] 

def processPath(path): 
    minIndent = 0 
    for element in path: 
     if element[1] < minIndent: 
      minIndent = element[1] 
    offset = abs(minIndent) 
    for element in path: 
     print ('_' * (offset + element[1])) + element[0].value 



root = Node('A') 
root.left = Node('B') 
root.right = Node('C') 
root.left.left = Node('D') 
root.left.right = Node('E') 
root.right.left = Node('F') 
root.right.right = Node('G') 

printTreeRelativePaths(root)