在python类中实现树的递归函数

Question

我创建了一个类Tree和一个类Node.现在我需要实现preOrder,postOrder并inOrder遍历.我是用私人功能做的.但有没有办法只使用一个函数来做同样的事情？

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

class Tree:
    def __init__(self):
        self.root = None

    # Private helper functions
    def __insert(self, data, root):
        if data < root.data:
            if root.left is None:
                root.left = Node(data)
            else:
                self.__insert(data, root.left)
        elif data >= root.data:
            if root.right is None:
                root.right = Node(data)
            else:
                self.__insert(data, root.right)

    # Traversals
    def __preOrder(self, root):
        print root.data
        if root.left:
            self.__preOrder(root.left)
        if root.right:
            self.__preOrder(root.right)

    # Wrapper Functions 
    def insert(self, data):
        if self.root == None:
            self.root = Node(data)
        else:
            self.__insert(data, self.root)

    def preOrder(self):
        self.__preOrder(self.root)


tree = Tree()
print "Enter elements to be inserted in the tree(End with a -1): "
while True:
    elem = int(raw_input())
    if elem == -1:
        break
    tree.insert(elem)

print "Preorder traversal: "
tree.preOrder()

这里我必须使用辅助函数,因为我不希望用户显式提供根元素.

Answer 1

是的,您可以在单个函数中实现所有3种类型的遍历.我已经将遍历函数转换为生成器,以使它们更加通用.因此,它们不是打印数据,而是生成数据的迭代器.这使您可以在数据生成时处理数据,也可以将数据捕获到列表(或其他集合)中.

在Python 2中,您的类应该继承object,否则您将获得旧式类,与新式类相比,它们相当有限(Python 3只有新式类).

顺便说一句,没有必要为私有函数(调用Python的名称修改机制)使用双下划线,单个前导下划线就足够了.

我还__repr__为类添加了简单的方法,这在开发和调试过程中非常方便.

class Node(object):
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def __repr__(self):
        return repr((self.data, self.left, self.right))


class Tree(object):
    def __init__(self):
        self.root = None

    def __repr__(self):
        return repr(self.root)

    # Private helper functions
    def _insert(self, data, root):
        if data < root.data:
            if root.left is None:
                root.left = Node(data)
            else:
                self._insert(data, root.left)
        else: # data >= root.data:
            if root.right is None:
                root.right = Node(data)
            else:
                self._insert(data, root.right)

    def _traverse(self, root, mode):
        if mode == 'pre':
            yield root.data
        if root.left:
            for u in self._traverse(root.left, mode):
                yield u
        if mode == 'in':
            yield root.data
        if root.right:
            for u in self._traverse(root.right, mode):
                yield u
        if mode == 'post':
            yield root.data

    # Wrapper Functions 
    def insert(self, data):
        if self.root == None:
            self.root = Node(data)
        else:
            self._insert(data, self.root)

    def preOrder(self):
        for u in self._traverse(self.root, 'pre'):
            yield u

    def inOrder(self):
        for u in self._traverse(self.root, 'in'):
            yield u

    def postOrder(self):
        for u in self._traverse(self.root, 'post'):
            yield u

# Test

tree = Tree()

for elem in '31415926':
    tree.insert(elem)

print tree

print "Preorder traversal: "
print list(tree.preOrder())

print "InOrder Traversal: "
print list(tree.inOrder())

print "PostOrder Traversal: "
print list(tree.postOrder())

产量

('3', ('1', None, ('1', None, ('2', None, None))), ('4', None, ('5', None, ('9', ('6', None, None), None))))
Preorder traversal: 
['3', '1', '1', '2', '4', '5', '9', '6']
InOrder Traversal: 
['1', '1', '2', '3', '4', '5', '6', '9']
PostOrder Traversal: 
['2', '1', '1', '6', '9', '5', '4', '3']

以下是处理数据时的示例:

for data in tree.inOrder():
    print data

FWIW,这段代码在Python 3中会更加清晰,因为我们可以使用yield from语法而不是那些for循环.而不是

for u in self._traverse(root.left, mode):
    yield u

我们能做到

yield from self._traverse(root.left, mode)