刷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)))
运行结果,这是上述第三个例子: