上节中我们学到了链表,这一节中学习一个新的数据结构二叉树,对于链表它拥有的属性时值val,和下一个链表节点指针next,而二叉树其实就比他多一个属性,它的形状看起来是下面这样的:
class TreeNode: def __init__(self, val=0, left=None,right=None): self.val = val self.left = left self.right = right head=TreeNode(1,TreeNode(2),TreeNode(3))print(head.val)#1print(head.left.val)#2print(head.right.val)#3这样的方式组成的二叉树如下图所示:
和之前一样,我们先介绍二叉树的遍历方式
二叉树的遍历
二叉树的有三种递归遍历方式和一种层序遍历方式,都是需要掌握的,我们使用如下图所示的二叉树来进行讲解:
前序遍历
前序遍历的方式是<根,左,右>的遍历方式,因为先遍历根节点所以叫前序遍历,根据上述二叉树,从根节点1出发,那么整体二叉树会输出成什么样呢?这里我们先给出代码,根据代码来推一推吧:
class TreeNode: def __init__(self, val=0, left=None,right=None): self.val = val self.left = left self.right = right @staticmethod def pre_order(head): if head is None:return print(head.val) TreeNode.pre_order(head.left) TreeNode.pre_order(head.right)head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))TreeNode.pre_order(head)答案是1 2 4 5 3 6,有答对嘛,没有答对没有关系,因为这里牵扯到一个新的知识点递归,我们根据当前二叉树来分析一下代码如何运行:
如下图所示,那个长方形的东西叫做栈,函数是右边那个pre_order,函数只有进栈后才能正确的运行
来看一下进栈的过程，进入栈后pre_order(1)开始运行，第一句不为空吧，继续往下运行，第二句打印1，第三句设计到了递归函数，需要创建一个新的函数pre_order(2)，而且需要在pre_order(2)进栈运行完成之后再继续第四句话的运行
继续pre_order(2)进栈后，重复刚刚的过程在第三句的时候创建了pre_order(4)
接着pre_order(4)进栈，重复以上过程创建了pre_order(None),因为对于4这个节点并没有左子节点嘛，对是不对
延续刚刚的过程，pre_order(None)进栈，开始执行代码，在第一句的时候整个代码就已经执行完了，执行完之后的函数会进行出栈操作
出栈后我们栈顶的函数为pre_order(4),还记得上次这个函数运行到哪行代码了吗？是第三句哦，所以现在会继续运行第四句代码，4这个节点是不是依然没有右节点，那么生成的函数还是pre_order(None),和上述过程完全一样，这里就不再赘述了，我们继续往下看
在又一个pre_order(None)出栈之后，pre_order(4)也全部执行结束了，所以pre_order(4)也该出栈
接着看，在pre_order(4)出栈后，栈顶的函数是pre_order(2)，这个函数上次也是执行到第三句话，该接着执行第四局了，这里又创建了一个函数pre_order(5)，因为2的右节点是5嘛
接着pre_order(5)入栈打印5，最后再开始打印节点1的右节点，分析的过程和我们上面是一样的哦，羊羊可以自己分析一下
最后的打印结果就是1，2，4，5，3，6了
中序遍历
理解了递归和前序遍历，中序遍历就显得十分简单了，它的代码如下，只是输出语句换了一个位置罢了:
class TreeNode: def __init__(self, val=0, left=None,right=None): self.val = val self.left = left self.right = right @staticmethod def in_order(head): if head is None:return TreeNode.in_order(head.left) print(head.val) TreeNode.in_order(head.right)head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))TreeNode.in_order(head)他的输出结果是：4 2 5 1 6 3，因为他的打印方式是《左，根，右》会最先输出左子树的节点
后序遍历
是不是已经可以自己写出后序遍历了，真的很简单呢
class TreeNode: def __init__(self, val=0, left=None,right=None): self.val = val self.left = left self.right = right @staticmethod def post_order(head): if head is None:return TreeNode.post_order(head.left) TreeNode.post_order(head.right) print(head.val)head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))TreeNode.post_order(head)他的输出结果是：4 5 2 6 3 1
随堂检测
不借助代码能否写出如下这颗树的前序，中序和后续遍历呢，后续自己可以使用代码来测试一下哦：
层序遍历
是不是感觉前中后序遍历都没有什么规律可言，好像是给电脑看的，我作为一个人我就想遍历出来就是1，2，3，4，5，6，7，8这样的，这就要说到层序遍历了
其思路是这样的，我们先将头节点放入容器，然后在遍历到头节点的左节点和右节点的时候也将其加入容器，在一个节点的左节点和右节点都被遍历完以后将这个节点丢出容器，现在容器里是不是只剩下头节点的左右节点了，我们继续上述操作，按照先来先到的原则，对这两个节点执行上述操作，直到容器内什么都不剩下
思考一下要找到最先进入的节点我们该使用什么数据结构呢？栈的特点（先序遍历的时候讲过了，栈只有一个口子进出）是先进后出与我们的用法相悖，所以该使用的是队列（队列是一个先进先出的数据结构，像一根管子一样，add函数从管子的头进入，poll函数从管子的后面取出，python中的栈和队列都是用deque双端队列来实现的，这里要记得import哦)
import collections #别忘记导入容器工具class TreeNode: def __init__(self, val=0, left=None,right=None): self.val = val self.left = left self.right = right @staticmethod def post_order(head): if head is None:return TreeNode.post_order(head.left) TreeNode.post_order(head.right) print(head.val) @staticmethod def levelOrder(root): if root == None: return [] # 特判 que = collections.deque([root]) # 双端队列，初始化并且将root丢进队列 ans = [] while len(que) != 0: size = len(que) level = [] for _ in range(size): # 遍历当前层节点 cur = que.popleft() # 从左边弹出队列 level.append(cur.val) # 将当前节点值加入当前层的列表 if cur.left != None: que.append(cur.left) if cur.right != None: que.append(cur.right) ans.append(level) # 将当前层结果加入答案列表 return ans @staticmethod def printList(list): for subList in list: print(subList) head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))ans=TreeNode.levelOrder(head)TreeNode.printList(ans)结果打印出来如下图所示：
