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エッジリストをダンプするようにクラスを変更する方法の 1 つを次に示します。

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

a を使用し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、つまり、この pre-order 再帰実装のような深さ優先のものが必要な場合があります。

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 に答える