没有合适的资源?快使用搜索试试~ 我知道了~
首页二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度)
二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度)
需积分: 31 105 下载量 142 浏览量
更新于2023-03-16
评论 4
收藏 158KB PDF 举报
二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度)
资源详情
资源评论
资源推荐
二叉树的遍历
前序遍历递归算法:
代码如下:
public void preOrderTraver(Node root){
if(root != null){
visit(root);
preOrderTraver(root.getLeft());
preOrderTraver(root.getRight());
}
}
二叉树的前序遍历的规则是依次访问根-》左子树-》右子树。并且左子树、右子树均是一棵
二叉树。
对于一棵最小的子树来说,它的结构有如下四种情况:
1) 根 2) 根 3) 根 4)根
/\ / \
叶子 叶子 叶子 叶子
注意:不存在无根的子树
根据二叉树的前序遍历的规则, 我们能够发现 前序遍历的过程是可以抽象成依次访问根
-》左子树-》右子树 的, 并且对于每一棵子树我们采用相同的遍历规则,只是当前的根
有所不同而已。
现在,我们考虑一下遍历终止的条件:
当我们将二叉树中所有结点都遍历过了之后,这时我们遍历结束。当然,这也可以等价于我
们访问过了二叉树的根节点和所有子树的根节点。这个条件在我们编程时,更容易实现。
当根为 null 时,说明该棵子树已经遍历完成
1、当二叉树为空树时,显然无需遍历。
2、当二叉树不为空树时,等价于该二叉树有根节点。对于前序遍历来说,我们先要访问根
节点,然后访问左子树,然后右子树。
因为二叉树的子树也是二叉树,当我们遍历左右子树时,只需要把子树当成二叉树一样遍历
就好(重复上面的 1、2 过程),不同的是,此时的根为子树的根。
我们能够发现 当没有根可以遍历时,我们就遍历完了整棵二叉树。
中序遍历和后序遍历是相同的道理。
中序遍历递归算法:
代码如下:
public void inOrderTraver(Node root){
if(root != null){
preOrderTraver(root.getLeft());
visit(root);
preOrderTraver(root.getRight());
}
}
后序遍历递归算法:
代码如下:
public void postOrderTraver(Node root){
if(root != null){
preOrderTraver(root.getLeft());
preOrderTraver(root.getRight());
visit(root);
}
}
非递归遍历二叉树
前序遍历非递归法(用栈):
/**
* 非递归法求先序遍历序列
* 法 1
* 思路:
* 1、如果二叉树为空树,则结束遍历;
* 2、如果二叉树不为空树,将根节点入栈
* 当栈不为空时
* 3、弹出栈顶节点并访问
* 4、如果栈顶节点有右子树,将右子树根入栈
* 5、如果栈顶元素有左子树,将左子树根入栈
* 6、重复 3、4、5 过程,直到栈为空
* @param root
*/
public void iterativePreOrderTraver(Node root){
Stack<Node> nodes = new Stack<Node>();
if(root != null){//当二叉树不为空(即二叉树有根节点)时
//将根节点入栈
nodes.push(root);
while(!nodes.empty()){//当栈不为空时,
//弹出栈顶元素
root = nodes.pop();
//访问根节点
visit(root);
//如果二叉树有右子树,将右子树根节点压入栈中
if(root.getRight() != null){
nodes.push(root.getRight());
}
//如果二叉树有左子树,将左子树跟阶段压入栈中
if(root.getLeft() != null){
nodes.push(root.getLeft());
}
}
}
}
/**
* 非递归法求先序遍历序列
* 法 2
* 思路:
* 当栈不为空或节点不为空时
* 1、将当前节点的根入栈并访问
* 2、将当前节点的左子树根设为当前节点
* 3、重复 1、2,直到当前节点无左孩子
* 如果栈不空
* 4、将栈顶节点弹出
* 5、如果栈顶节点有右子树,将栈顶节点的右子树根设为当前节点
* 6、重复 1、2、3、4、5 过程,直到栈为空。
* @param root
*/
public void iterativePreOrderTraver2(Node root){
Stack<Node> nodes = new Stack<Node>();
Node node = root;
while(node != null || !nodes.empty()){
//将左节点压入栈中
while(node != null){
visit(node);
nodes.push(node);
node = node.getLeft();
}
//将栈中深度最大节点的右子树根压入栈中,将该右子树按照上面方法将该右子
树根的左节点遍历后压入栈中
if(!nodes.empty()){
node = nodes.pop();
node = node.getRight();
}
}
}
中序遍历非递归法(用栈):
/**
* 非递归法求中序遍历序列
* 法 1
* 思路:
* 1、将当前节点(可看成某棵子树或二叉树的根)的右子树根压入栈中,再将当前节点
压入栈中
* 2、将当前节点的左子树根设为当前节点
* 3、重复 1、2,直到当前节点没有左孩子为止
* 4、将栈顶节点出栈,当栈不为空(没有遍历完二叉树)且 弹出节点没有右子树时,弹
出节点并遍历,重复 4;
* 5、如果栈不为空,将当前节点的右子树根设为当前节点
* 6、重复 1、2、3、4、5 过程 直到 当前节点为空(按照这种压栈弹栈方法,遍历完
整个二叉树的条件为最后一棵被遍历的子树没有右孩子)
* @param root
*/
public static void iterativeInOrderTraver(Node root){
Stack<Node> nodes = new Stack<Node>();
Node node = root;
//由于压栈过程是先压右子树 , 再压根节点,所以当栈为空时,遍历过二叉树所有
节点
while(node != null){
//压栈过程
while(node != null){
if(node.getRight() != null)
nodes.push(node.getRight());
nodes.push(node);
node = node.getLeft();
}
//弹栈过程
node = nodes.pop();
visit(node);
//分两种情况
//1、栈不空 且 当前节点无右子树
while(!nodes.empty() && node.getRight() == null){//返回上一层
node = nodes.pop();
//访问当前节点
visit(node);
}
//2、栈不空 且 当前节点无右子树
if(!nodes.empty()){
//弹出右节点,把右节点当根,重复下面过程
/*
while(node != null){
if(node.getRight() != null)
nodes.push(node.getRight());
nodes.push(node);
node = node.getLeft();
}
node = nodes.pop();
visit(node);
while(!nodes.empty() && node.getRight() == null){//返回上一层
node = nodes.pop();
visit(node);
}
*/
node = nodes.pop();
}else{//结束遍历
node = null;
}
}
}
/**
* 非递归法求中序遍历序列
* 法 2
* 思路:
* 1、将当前节点的左侧节点依次放入栈中,直到最左侧节点(无左孩子)
* 2、将最左侧节点(实际上为未访问过的最左侧节点,因为访问过的节点都会出栈)出
栈,并访问
* 3、将最左侧节点的右子树根节点 定为当前节点
* 4、重复 1、2、3 过程 直到栈为空(即遍历完整棵二叉树)
* @param root
*/
public static void iterativeInOrderTraver2(Node root){
Stack<Node> nodes = new Stack<Node>();
Node node = root;
//二叉树无根节点(此时栈为空且当前节点为空)
//遍历结束时(
//二叉树无根节点(此时栈为空且当前节点为空)
while(node != null || !nodes.empty()){
//遍历结束的条件是:
//1)二叉树不为空树时,运行后,栈为空,当前节点为空 (此时,正是遍历
完整棵二叉树的时候)
//2)二叉树为空树
//将以当前节点为根节点的子树左侧节点压入栈中
while(node != null){
nodes.push(node);
node = node.getLeft();
}
//弹出左侧最深节点,将当前节点设为当前节点的右孩子,将右孩子视为下一次
循环的根节点
剩余25页未读,继续阅读
李华峰
- 粉丝: 6
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 2022年中国足球球迷营销价值报告.pdf
- 房地产培训 -营销总每天在干嘛.pptx
- 黄色简约实用介绍_汇报PPT模板.pptx
- 嵌入式系统原理及应用:第三章 ARM编程简介_3.pdf
- 多媒体应用系统.pptx
- 黄灰配色简约设计精美大气商务汇报PPT模板.pptx
- 用matlab绘制差分方程Z变换-反变换-zplane-residuez-tf2zp-zp2tf-tf2sos-sos2tf-幅相频谱等等.docx
- 网络营销策略-网络营销团队的建立.docx
- 电子商务示范企业申请报告.doc
- 淡雅灰低面风背景完整框架创业商业计划书PPT模板.pptx
- 计算模型与算法技术:10-Iterative Improvement.ppt
- 计算模型与算法技术:9-Greedy Technique.ppt
- 计算模型与算法技术:6-Transform-and-Conquer.ppt
- 云服务安全风险分析研究.pdf
- 软件工程笔记(完整版).doc
- 电子商务网项目实例规划书.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0