二叉树的遍历方式以及代码实现python

二叉树的遍历方式以及代码实现python

1、基本概念

首先我们先请出一位二叉树先生（噱（稍）微有点丑） 三种遍历方式 先序遍历 a-b-d-e-c-f中序遍历 d-b-e-a-c-f后序遍历 d-e-b-f-c-a 那么问题来了我们应该怎么记呢？ 重点来了：所谓前中后都是以“当前根节点”为主，“前”就是说第一个先走“当前根节点”再走左子树再走右子树，“中”就是说第一个先走左子树再走“当前根节点”再走右子树，“后”就是说第一个先走左子树再走右子树再走“当前根节点”，

2、代码实现

# 首先定义树的数据结构 class TreeNode: def __init__(self,val): self.val = val self.left = None self.right = None class Solution: # 先序遍历 def preorder(self,root): if not root: return None print(root.val,'- ',end='') self.preorder(root.left) self.preorder(root.right) # 中序遍历 def inorder(self,root): if not root: return None self.inorder(root.left) print(root.val,'- ',end='') self.inorder(root.right) # 后序遍历 def postorder(self,root): if not root: return None self.postorder(root.left) self.postorder(root.right) print(root.val,'- ',end='') a,b,c,d,e,f = [TreeNode(x) for x in 'abcdef'] a.left,a.right = b,c b.left,b.right = d,e c.right = f s = Solution() s.preorder(a) print() s.inorder(a) print() s.postorder(a) 输出： a - b - d - e - c - f - d - b - e - a - c - f - d - e - b - f - c - a -