刷Leetcode时遇到一种经典数据结构--树，树是典型递归思想来的，学习树有助于学习递归思想以及栈、队列（后续细说），本文对树的结构、遍历算法以及Python实现做总结，以供复习拓展
树是连通的无环图，最常利用的有二叉树，即一个节点最多只有两个子节点，称为左子树和右子树。但是树都是相通的，无论是二叉树或者多个节点的树都能一般能用递归方法进行求解。二叉树节点之间的顺序一般不可调换，在数据结构定义时，左是左，右是右，不会说节点1，节点2。二叉排序树又叫二叉查找树或者二叉搜索树：1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；3）左、右子树也分别为二叉排序树；4）没有键值相等的节点
以上是枯燥的概念。
接下来就是重点了，各种遍历（后面有Python代码实现，可用其测试各种类型树的各种遍历）：
前序遍历，根-->左子树-->右子树
中序遍历，左子树-->根-->右子树
后序遍历，左子树-->右子树-->根
前序/后序+中序能够确定一个完整的树结构，因为前序/后序的根在第一位/最后一位，这样在中序中找到对应的根节点，以此递归，具体的题见leetCode105、106
广度优先遍历（Breadth FirstSearch，BFS,实际上就是逐层查找，又叫层次遍历，宽度优先搜索或横向优先搜索）
深度优先遍历（Depth First Search，DFS，主要有三种子方法，前中后序遍历）
举几个例子一目了然，因为深度优先遍历就是前中后序就不再说明了：
对于前中后序遍历或者说深度优先遍历来讲，递归实现非常简单，详细可见代码，但是如果非递归实现，则考虑用栈，先进后出。没有用代码实现，lazy。
对于层次遍历，用队列实现就比较简单，用一个List记录每一行的节点，在循环调用，详细见代码（PS：栈和队列在python中都用list实现即可，栈的取用方式为逆序，pop(-1)，队列使用正序取用）
但是DFS、BFS不止用于树结构，这是一种思想，一个横向发散，一个纵向发散，是解决很多算法问题的思路
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:# 前序遍历，lis是传入的list型参数，为了递归得到一个遍历List结果def preorder(self, tree, lis):lis.append(tree.val)if tree.left:self.preorder(tree.left,lis)if tree.right:self.preorder(tree.right,lis)return lis# 中序遍历，lis是传入的list型参数，为了递归得到一个遍历List结果def infix_order(self,tree, lis):if tree.left:self.infix_order(tree.left, lis)lis.append(tree.val)if tree.right:self.infix_order(tree.right, lis)return lis# 后序遍历，lis是传入的list型参数，为了递归得到一个遍历List结果def epilogue(self, tree, lis):if tree.left:self.epilogue(tree.left, lis)if tree.right:self.epilogue(tree.right, lis)lis.append(tree.val)return lis# 广度优先遍历，层次遍历，lis是传入的list型参数，为了递归得到一个遍历List结果def BFS(self, tree):ans = []q1 = [tree]while q1:q2 = [] # q2 是q1 层的孩子，下一次循环的时候用它for item in q1:if item:ans.append(item.val)q2.append(item.left)q2.append(item.right)q1 = q2return ans# 定义一个树,这棵树是上述第三个例子n1=TreeNode(1)n2=TreeNode(2)n3=TreeNode(3)n4=TreeNode(4)n5=TreeNode(5)n6=TreeNode(6)n7=TreeNode(7)n8=TreeNode(8)n1.right=n3n1.left=n2n2.right=n5n2.left=n4n3.left=n6n3.right=n7n5.right=n8# 运行各种遍历s = Solution()print("前序遍历结果为：",str(s.preorder(n1,[])))print("中序遍历结果为：",str(s.infix_order(n1,[])))print("后序遍历结果为：",str(s.epilogue(n1,[])))print("BFS结果为：",str(s.BFS(n1)))
运行结果，这是上述第三个例子：
如果觉得《树的前序 中序 后序遍历及深度优先算法DFS 广度优先算法BFS及python实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
