來自二叉樹的邊緣列表

Question

我想製作一個漂亮的二叉樹圖。

這裏是我的自定義二叉樹類：

class BinaryTree(): 

    def __init__(self, data): 
     self.data = data 
     self.right = None 
     self.left = None 

現在，爲了繪製這個圖我將使用networkx庫，所以我需要我的圖形轉換爲networkx對象，然後用graphviz的繪製它。問題是邊緣列表：爲了構建我的新對象，我需要邊緣。

例如給出一個二叉樹，如下圖所示。

我需要檢索邊緣列表。會是這樣的：

[(0,1),(0,2),(2,3),(2,4)] 

請注意，在我的情況下，我沒有節點上的id。那我該怎麼做呢？ 我相信這可能是一些遞歸函數考慮到深度，但我有一些困難，所以有一點幫助表示讚賞。 ;）

編輯

感謝您的答案。但是，我發現了一個解決方案通過自己的作品以及..：P 這就是：

def edgelist(node, output, id=0): 

    if node is None or isinstance(node, bt.Leaf): 
     return output 

    if node.left: 
     output.append((id, id*2+1)) 

    if node.right: 
     output.append((id, id*2+2)) 

    edgelist(node.left, output, id*2+1) 
    edgelist(node.right, output, id*2+2) 

    return output 

Answer 1

這裏有一種方法，你可以修改BinaryTree類轉儲EdgeList都：

import networkx as nx 
import itertools as IT 
import matplotlib.pyplot as plt 

class BinaryTree(object): 
    def __init__(self, data): 
     self.data = data 
     self.right = None 
     self.left = None 
     self.name = None 
    def edgelist(self, counter = IT.count().next): 
     self.name = counter() if self.name is None else self.name 
     for node in (self.left, self.right):  
      if node: 
       node.name = counter() if node.name is None else node.name 
       yield (self.name, node.name) 
     for node in (self.left, self.right): 
      if node: 
       for n in node.edgelist(counter): 
        yield n 

tree = [BinaryTree(i) for i in range(5)]   
tree[0].left = tree[1] 
tree[0].right = tree[2] 
tree[2].left = tree[3] 
tree[2].right = tree[4] 

edgelist = list(tree[0].edgelist()) 
print(edgelist) 

G = nx.Graph(edgelist) 
nx.draw_spectral(G) 
plt.show() 

產量

[(0, 1), (0, 2), (2, 3), (2, 4)] 

Answer 2

可以使用collections.dequeue避免遞歸：

import collections 
def edges_breadth(tree): 
    history = collections.deque([tree]) 
    while history: 
     parent = history.popleft() 
     for c in (parent.left, parent.right): 
      if c: 
       yield((parent.data, c.data)) 
       history.append(c) 

注意，這是一個廣度優先遍歷。您可能需要另一個traversal order，在這個預購遞歸實現即深度第一個，如：

def edges_depth(tree): 
    results = [] 
    def visit(parent, child): 
     if child: 
      results.append((parent, child)) 
      visit(child.left) 
      visit(child.right) 
    return results