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

概述我创建了一个类Tree和一个Node类.现在我需要实现preOrder,postOrder和inOrder遍历.我是用私人功能做的.但有没有办法只使用一个函数来做同样的事情？ class Node: def __init__(self, data): self.left = None self.right = None self.data = 我创建了一个类Tree和一个Node类.现在我需要实现preOrder,postorder和inorder遍历.我是用私人功能做的.但有没有办法只使用一个函数来做同样的事情？

class Node:    def __init__(self,data):        self.left = None        self.right = None        self.data = dataclass 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()

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

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

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

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

我还在类中添加了简单的__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,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# Testtree = Tree()for elem in '31415926':    tree.insert(elem)print treeprint "Preorder traversal: "print List(tree.preOrder())print "Inorder Traversal: "print List(tree.inorder())print "postorder Traversal: "print List(tree.postorder())

产量

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

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

for data in tree.inorder():    print data

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

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

我们能做到

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

总结

以上是内存溢出为你收集整理的在python类中实现树的递归函数全部内容，希望文章能够帮你解决在python类中实现树的递归函数所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。