那些网站是php开发的,开发商破产房子烂尾怎么办,互动平台表示公司帮助国内客户进行新冠药物研发,手机怎样建个人网站二叉树
二叉树#xff08;Binary tree#xff09;是树形结构的一个重要类型。对于二叉树的基础知识这里不做过多介绍#xff0c;下面我们直接介绍二叉树的遍历方式和如何用python代码去实现二叉树的遍历。
二叉树的遍历#xff08;重点#xff09;
“前”、“中”、“后…二叉树
二叉树Binary tree是树形结构的一个重要类型。对于二叉树的基础知识这里不做过多介绍下面我们直接介绍二叉树的遍历方式和如何用python代码去实现二叉树的遍历。
二叉树的遍历重点
“前”、“中”、“后“是相对根节点来说的 深度优先DFS递归实现 先序遍历根节点——左子树——右子树 中序遍历左子树——根节点——右子树 后序遍历左子树——右子树——根节点
广度优先BFS配合队列一起实现 层序遍历广度优先 代码实现
注意在层序遍历的时候我用的队列是引入了collections中的队列其实我们也可以用python中的列表代替模拟队列的操作。
from collections import dequeclass Node(object):def __init__(self,val,leftNone,rightNone):self.val valself.left leftself.right right class Tree(object):def __init__(self):self.root Nonedef add(self,item):只考虑尾插 并且层次遍历后插入node Node(item)# 考虑边界条件# bool([None]) True 这种情况进入while循环会出错 if self.root is None:self.root nodereturnqueue deque() # 也可以用列表代替queue.append(self.root)while queue:cur_node queue.popleft()if cur_node.left is None:cur_node.left nodereturnelse:queue.append(cur_node.left)if cur_node.right is None:cur_node.right nodereturnelse:queue.append(cur_node.right)def levelorder(self):层序遍历广度优先# 考虑边界条件if self.root is None:returnqueue deque()queue.append(self.root)while queue:cur_node queue.popleft()print(cur_node.val,end )if cur_node.left is not None:queue.append(cur_node.left)if cur_node.right is not None:queue.append(cur_node.right)# 递归实现深度优先 关注树根节点的变化def preorder(self,node):递归实现先序遍历# 终止条件if node is None:return# 循环部分print(node.val,end )self.preorder(node.left)self.preorder(node.right)def inorder(self,node):递归实现中序遍历# 终止条件if node is None:return# 循环部分self.inorder(node.left)print(node.val,end )self.inorder(node.right) def postorder(self,node):递归实现后序遍历# 终止条件if node is None:return# 循环部分self.postorder(node.left)self.postorder(node.right) print(node.val,end )if __name__ __main__:tree Tree()tree.add(0)tree.add(1)tree.add(2)tree.add(3)tree.add(4)tree.add(5)tree.add(6)tree.add(7)tree.add(8)tree.add(9)print(广度优先-层序遍历,end )tree.levelorder()print(\n)print(深度优先-先序遍历,end )tree.preorder(tree.root)print(\n)print(深度优先-中序遍历,end )tree.inorder(tree.root)print(\n)print(深度优先-后序遍历,end )tree.postorder(tree.root)print(\n)输出结果 广度优先-层序遍历 0 1 2 3 4 5 6 7 8 9
深度优先-先序遍历 0 1 3 7 8 4 9 2 5 6
深度优先-中序遍历 7 3 8 1 9 4 0 5 2 6
深度优先-后序遍历 7 8 3 9 4 1 5 6 2 0
