建设网站的目的服装类,图库网址大全,网站建设施工图片,租房合同 模板开始系统学习算法啦#xff01;为后面力扣和 蓝桥杯的刷题做准备#xff01;这个专栏将记录自己学习算法是的笔记#xff0c;包括 概念#xff0c; 算法运行过程#xff0c;以及 代码实现#xff0c;希望能给大家带来帮助#xff0c;感兴趣的小伙伴欢迎评论区留言或者私… 开始系统学习算法啦为后面力扣和 蓝桥杯的刷题做准备这个专栏将记录自己学习算法是的笔记包括 概念 算法运行过程以及 代码实现希望能给大家带来帮助感兴趣的小伙伴欢迎评论区留言或者私信博主哦今天更新的是 《07 二叉树》 目录
一、树概念
二、性质
三、特殊二叉树
四、二叉树的节点及树的创建
五、二叉树的遍历
5.1深度优先遍历
先序遍历
中序遍历
后续遍历
5.2 广度优先遍历层次遍历) 一、树概念
二叉树是每个节点最多有两个子树的树结构。通常子树被称作”左子树“left subtree)和”右子树“right subtree)。
二、性质
在二叉树的第i层上至多有2^(i-1)个节点(i0)深度为k的二叉树至多有2^k-1个节点对于任意一颗二叉树如果其叶节点数为N0而度数为2 的节点总书为N2那么N0 N21具有n个系欸点的完全二叉树的深度必为log2(n1)对完全二叉树 若从上到下、从左到右编号则编号为i的结点其左孩子编号必为2i其右孩子编号必为2i1其双氢的编号必为i/2 i1时为根除外
三、特殊二叉树
完全二叉树设二叉树的高度为h除第h层外其他各层1~h-1的节点数都达到最大个数第h层有叶子节点并且叶子节点都是从左到右依次排布这就是完全二叉树。 满二叉树除了叶节点外每个节点都有左右子叶且叶子节点都处在最外层的二叉树 四、二叉树的节点及树的创建
节点创建
class Node(object):def __init__(self,elem-1,lchildNone,rchildNone):self.elem elemself.lchild lchildself.rchild rchild
树的初始化
class Tree(object):def __init__(self,root None):self.root root
添加节点def add(self,elem):# 首先创建节点node Node(elem)# 如果树是空的则对root根赋值if self.root None:self.root nodeelse:queue []queue.append(self.root)# 对已有的节点进行层次遍历while queue:cur queue.pop(0)if cur.lchild None:cur.lchild nodereturnelif cur.rchild None:cur.rchild nodereturnelse:#如果左右子树都不为空加入队列继续判断queue.append(cur.lchild)queue.append(cur.rchild)
五、二叉树的遍历 树的遍历是书的一种重要的运算所谓遍历是指对树中所有节点的信息的访问即一次对树中每个节点访问一次且仅访问一次我们把这种对所有节点的访问称为遍历(traveral)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历深度优先一般用递归广度优先一般用队列一般情况下能用递归实现的算法大部分也能用堆栈来实现。
5.1深度优先遍历
对于一颗二叉树深度优先搜素Depth First Search)是沿着树的深度遍历树的节点尽可能深的搜索树的分支。
那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点他们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历preorder中序遍历inorder和后序遍历prstorder)。我们给出详细定义然后举例看看它们的应用。 先序遍历
在先序遍历中我们先访问根节点然后递归使用先序遍历访问左子树然后再递归使用先序遍历访问右子树。
访问的顺序为根节点-左子树-右子树
代码实现
class Tree(object):def preorder(self,root):if root None:returnprint(root.item)self.preorder(root.lchild)self.preorder(root.rchild) 中序遍历
在中序遍历中我们递归使用中序遍历访问左子树然后访问根节点最后再递归使用中序遍历访问右子树
访问顺序为左子树-根节点-右子树
代码实现
class Tree(object):def inorder(self,root):if root None:returnself.inorder(root.lchild)print(root.item)self.inorder(root.rchild) 后续遍历
在后续遍历中我们先递归使用后序遍历访问左子树和右子树最后访问根节点。
访问顺序为左子树-右子树-根节点
代码实现
class Tree(object):def postorder(self,root):if root None:returnself.postorder(root.lchild)self.postorder(root.rchild)print(root.item) 5.2 广度优先遍历层次遍历)
从树的root开始从上到下从左到右遍历整个树的节点
代码实现
class Tree(object):def breath_travel(self):if self.root None:returnqueue []queue.append(self.root)while queue:node queue.pop(0)print(node.elem)if node.lchild ! None:queue.append(node.lchild)if node.rchild ! None:queue.append(node.rchild)
