IT外包 IT外包

咨询热线

400-635-8089

为什么选择IT外包公司

为什么选择IT外包公司

微软云
IT采购
弱电工程
系统集成

推荐视频

   走进蓝盟

蓝盟IT外包，二叉树的各种扫描真的很难吗？ 大赛会带你去的！

发布者：上海IT外包来源：http://www.lanmon.net点击数：845


二叉树的前序扫描
二叉树的前相遍历最简单，其枚举方式最简单的dfs，学习二叉树的前相遍历后，以后就很容易入门dfs了。
二叉树前序遍历的枚举规则为：根节点--- -大于左子树--- -大于右子树，也就是给定某棵树，对当前节点进行输出操作，然后枚举左子树，最后枚举右子树。 这样得到的列举序列之一是二叉树的前序扫描序列(也称为前序)。
沿着二叉树前进的顺序可以看到下图(红色箭头所指的表示需要访问，只有从父节点列举后才能被访问)。
具体实现的方式有递归方式和非递归方式。
递归
递归实现的二叉树的前序遍历很简单，递归考虑初始情况、结束边界、中间正常点逻辑即可。
初始状态：从根节点开始枚举，函数执行作为参数传递的根节点。
结束边界：如果节点的左(或右)子节点为null，则停止递归执行相应的节点。
常规点逻辑：首先处理当前点(存储或输出)，通过递归调用枚举左侧子树(如果不为空)，如果不是递归调用枚举右侧子树)。
非递归
非递归前缀还是非常简单的，遍历前缀的规则是根节点、左节点和右节点。 但是，根的左方一直持续着，手动列举没有递归返回的过程，一直持续着，我们怎么找到返回时的右方几点？
在堆栈中先存储路过的节点，第一次列举并存储节点输出后放入堆栈，第二次抛出时列举其右侧的节点。
其规则大致如下
访问当前节点，使用堆栈存储。 左侧的节点指向左侧的节点，直到左侧的孩子为空。
放下堆栈顶部不访问。 如果有右节点，请访问该右节点，重复步骤1，如果没有右节点，则重复步骤2中的抛出。
在这样的逻辑中，从根开始一直向左访问，到根、左访问结束后再访问右节点(子树)，得到完成前的遍历序列。
IT外包
中文
>
400-635-8089
立即
咨询 电话咨询
服务热线
400-635-8089
 微信咨询
微信咨询
微信咨询
公众号
公众号
公众号
返回顶部