Python 树递归

Question

我在 python 递归打印出搜索树的结果时遇到了一些困难。我是 C++ 本地人，我完全熟悉使用指针遍历此类结构，但 Python 比我以前做的工作更多。 . .

无论如何，我希望有人能够帮助我。我正在努力实施启发式方法来解决旅行商问题；但是，在我可以遍历我的树之前，我无法开始实际的启发式工作。无论如何，这是树的代码。

class Tree:
    branches = dict()

    def __init__(self, cities, n=0):
        if len(cities) == 1:
            nc = list(cities)  # create a working list
            # grab the nth element of the list, default to head
            # Stash that as the node value
            self.node = nc[n]
            print "Complete!"
        elif len(cities) == 0:
            print "Doubly Complete!"
        else:
            nc = list(cities)  # create a working list
            # grab the nth element of the list, default to head
            # Stash that as the node value
            self.node = nc[n]
            print self.node
            del nc[n]  # Pop off the nth value from the list
            print "deleted city! See?"
            print nc
            c = 0  # create a counter
            for a in nc:  # loop through the remaining cities
                self.branches[a] = Tree(nc, c)  # generate a new tree
                c += 1  # increase the counter


    def __repr__(self, tier=1):
        ret = ("\t" * tier)
        ret += self.node
        ret += "\n"
        for a in self.branches:
            ret += self.branches[a].__repr__(tier+1)
        return ret

__str__ = __repr__

这里是树实例化和打印的地方：

l = ['A','B','C','D']
mine = Tree(l)
print mine

打印树的结果是RuntimeError: maximum recursion depth exceeded。谈到下一步该怎么做时，我束手无策。如果有任何帮助，我将不胜感激！

哦！相信我，如果我可以使用递归之外的其他方法，我会的。不过，这种特殊的启发式方法需要它。

感谢所有帮助！

Answer 1

此代码似乎有效。我所做的只是将 self.branches 移动到 __init__ 内部。我在调试时遵循了最佳实践。问题是他们 class members 而不是 instance members。拥有像 dict 这样的可变数据类型是 class member 只会带来问题。

class Tree:
    def __init__(self, cities, n=0):
        self.branches = dict()
        if len(cities) == 1:
            nc = list(cities)  # create a working list
            # grab the nth element of the list, default to head
            # Stash that as the node value
            self.node = nc[n]
            print "Complete!"
        elif len(cities) == 0:
            print "Doubly Complete!"
        else:
            nc = list(cities)  # create a working list
            # grab the nth element of the list, default to head
            # Stash that as the node value
            self.node = nc[n]
            print self.node
            del nc[n]  # Pop off the nth value from the list
            print "deleted city! See?"
            print nc
            c = 0  # create a counter
            for a in nc:  # loop through the remaining cities
                self.branches[a] = Tree(nc, c)  # generate a new tree
                c += 1  # increase the counter

    def __repr__(self, tier=1):
        ret = ("\t" * tier)
        ret += self.node
        ret += "\n"
        for a in self.branches:
            ret += self.branches[a].__repr__(tier+1)
        return ret

    __str__ = __repr__

t = Tree(["SLC", "Ogden"], 1)
print t

Python 树递归

Python Tree Recursion

python

algorithm

tree

recursion