0

我想为我的二叉树画一个漂亮的图。

这是我的自定义 BinaryTree 类：

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
4

3 回答 3

1

这是您可以修改BinaryTree类以转储边缘列表的一种方法：

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

在此处输入图像描述

于 2012-11-25T15:32:11.103 回答
0

您可以使用 acollections.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)

请注意，这是广度优先遍历。您可能需要另一个遍历顺序，即深度优先的顺序，就像在这个前序递归实现中一样：

def edges_depth(tree):
    results = []
    def visit(parent, child):
        if child:
            results.append((parent, child))
            visit(child.left)
            visit(child.right)
    return results
于 2012-11-22T19:05:41.783 回答
0 
  def edgelist(T):
    results = []
    def visit(parent,child):
        if child:
            if parent != None:results.append((parent.key, child.key))
            visit(child,child.left)
            visit(child,child.right)
        return results
  return visit(None,T.root)
于 2021-10-07T15:00:22.857 回答