3

ツリーをトラバースして要素をリストとして返す関数があります。treeToList::traverse冗長に見えるので、のすべてのifステートメントを単純化する方法はありますか？

#!/usr/bin/python

def enum(**enums):
  return type('Enum', (), enums)

Order = enum(PREORDER=0, INORDER=1, POSTORDER=2)
def treeToList(root, order=Order.INORDER):
  ret = list()
  def traverse(node, order):
    if order == Order.PREORDER: ret.append(node.data)
    if node.right != None: traverse(node.right, order)
    if order == Order.INORDER: ret.append(node.data)
    if node.down != None: traverse(node.down, order)
    if order == Order.POSTORDER: ret.append(node.data)
  traverse(root, order)
  return ret

class node:
  def __init__(self, data=None):
    self.data = data
    self.down = None
    self.right = None

if __name__ == '__main__':
  root = node('F')
  root.right = node('B')
  root.down = node('G')
  root.right.right = node('A')
  root.right.down = node('D')
  root.down.down = node('I')
  root.right.down.right = node('C')
  root.right.down.down = node('E')
  root.down.down.right = node('H')

  print treeToList(root, Order.PREORDER)
  print treeToList(root, Order.INORDER)
  print treeToList(root, Order.POSTORDER)

出力

['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F']
4

4 に答える 4

5

さて、あなたがクロージャーを取り除くならば..純粋関数はおそらくより明確です：

def treeToList(node, order=Order.INORDER):
    if node is None:
        return []

    right = treeToList(node.right, order)
    down = treeToList(node.down, order)
    current = [node.data]

    if order == Order.PREORDER:
        return current + right + down

    if order == Order.INORDER:
        return right + current + down

    if order == Order.POSTORDER:
        return right + down + current

もちろん、多くの中間リストを作成します。

于 2013-03-20T23:58:52.073 に答える
2

私の頭に浮かぶ唯一のことはこれです：

def treeToList(root, order=Order.INORDER):
    ret = list()
    def inorder_traversal(node):
        if node is not None:
            inorder_traversal(node.right)
            ret.append(node.data)
            inorder_traversal(node.down)

    def preorder_traversal(node):
        if node is not None:
            ret.append(node.data)
            preorder_traversal(node.right)
            preorder_traversal(node.down)

    def postorder_traversal(node):
        if node is not None:
            postorder_traversal(node.right)
            postorder_traversal(node.down)
            ret.append(node.data)

    if order == Order.PREORDER:
        preorder_traversal(node)
    elif order == Order.INORDER:
        inorder_traversal(node)
    else:
        postorder_traversal(node)

    return ret
于 2013-03-20T23:53:44.160 に答える
2

if orderアルゴリズムを再編成せずに3つのステートメントを削除する良い方法はないと思います。発生する位置ret.appendは値に依存するため、3回すべてを何らかの方法でチェックする必要があります。

しかし、いくつかを削除するために物事を再編成する1つの明白な方法がありifます：

def traverse(node, order):
    if node is None: return
    if order == Order.PREORDER: ret.append(node.data)
    traverse(node.right, order)
    if order == Order.INORDER: ret.append(node.data)
    traverse(node.down, order)
    if order == Order.POSTORDER: ret.append(node.data)

もちろん1行長くなりますがif、6秒ではなく4秒です。

もう1つの可能性は、3つの位置すべてを追跡するように変更し、事後に適切な位置に挿入することです。

def traverse(node, order):
    if node is None: return
    prepos = len(ret)
    traverse(node.right, order)
    inpos = len(ret)
    traverse(node.down, order)
    postpos = len(ret)
    pos = (prepos, inpos, postpos)[order]
    ret[pos:pos+1] = node.data

これによりすべてのが削除ifされますが、結果が正確に読みやすく、理解しやすいとは思いません…</ p>

実際、これを読みやすく理解しやすくする方法は、おそらく機能的アルゴリズムに切り替えることです（再帰的可変アルゴリズムを考えるのはめったに楽しいことではありません）…しかし、それは3つのifボディを大きくし、それらを取り除くことはありません。

于 2013-03-20T23:59:05.290 に答える
0

次のようなものを試してください

if order in (Order.PREORDER, Order.INORDER, ...):
    ret.append(node.data)

Nitpicks

あなたは複数の行にあなたの条件を持っている必要があります

if cond:
    pass

それ以外の

if cond: pass

andの代わりにandを使用isしてis not比較する場合も検討してください。None==!=

于 2013-03-20T23:47:56.080 に答える