树的遍历

发布时间：2020-12-20 09:50:40 所属栏目：Python 来源：网络整理

导读：首先是树的建立： class TreeNode: def __init__ (self,x,left=None,right= None): self.val = x self.left = left self.right = right t7=TreeNode(7);t8=TreeNode(8) t3=TreeNode(3);t4=TreeNode(4,t7,right=None);t5=TreeNode(5,right=t8);t6=TreeNode(6)

首先是树的建立：

class TreeNode:
    def __init__(self,x,left=None,right=None):
        self.val=x
        self.left=left
        self.right=right

t7=TreeNode(7);t8=TreeNode(8)
t3=TreeNode(3);t4=TreeNode(4,t7,right=None);t5=TreeNode(5,right=t8);t6=TreeNode(6)
t1=TreeNode(1,t3,t4);t2=TreeNode(2,t5,t6)
root=TreeNode(0,t1,t2)

建立好的树如图所示：

一、递归版的遍历（很好记）

 traveral:
    __init__(self):
        self.pre_res=[]
        self.in_res=[]
        self.post_res=[]
    #先序遍历（根左右）
    def preorder(self,root):
        if root is None:
            return None
        self.pre_res.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)
    中序遍历（左根右）
     inorder(self,1)"> None
        self.inorder(root.left)
        self.in_res.append(root.val)
        self.inorder(root.right)
    后序遍历（左右根）
     postorder(self,1)"> None
        self.postorder(root.left)
        self.postorder(root.right)
        self.post_res.append(root.val)

tra=traveral()
tra.preorder(root)
tra.inorder(root)
tra.postorder(root)
print(tra.pre_res)
(tra.in_res)
print(tra.post_res)

输出：

[0,1,3,4,7,2,5,8,6]
[3,6,0]

二、非递归版本

 non_recursive:
    []
        pre_res=[]
        while root or stack:
            while root:
                pre_res.append(root.val)
                stack.append(root)
                root=root.left
            if stack:
                t=stack.pop()
                root=t.right
         pre_res

    []
        in_res=while stack  root:
             root:
                stack.append(root)
                root=stack.pop()
                in_res.append(t.val)
                root= in_res

    []
        stack2=[]
        post_res=[]
        stack1.append(root)
         stack1:
            t=stack1.pop()
             t.left:
                stack1.append(t.left)
             t.right:
                stack1.append(t.right)
            stack2.append(t)
         stack2:
            post_res.append(stack2.pop().val)
         post_res

     levelorder(self,root):
        queue=[root]
        level_res= queue:
            t=[]
            for i in range(len(queue)):
                cur=queue.pop(0)
                t.append(cur.val)
                 cur.left:
                    queue.append(cur.left)
                 cur.right:
                    queue.append(cur.right)
            level_res.append(t)
         level_res
nonre=non_recursive()
(nonre.preorder(root))
(nonre.inorder(root))
(nonre.postorder(root))
print(nonre.levelorder(root))

输出：

[0,0]
[[0],[1,2],[3,6],[7,8]]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!