来自二叉树的边缘列表

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