原题出自百度的笔试:
简述树的深度优先及广度优先遍历算法,并说明非递归实现。
当时我看到这个题目的时候,已经完全记不得非递归算法该怎么实现了,后来查阅了一下,要用到两个辅助的数据结构:
深度优先遍历--->栈;
广度优先遍历--->队列;
这里以二叉树为例来实现。
import java.util.ArrayDeque;
public class BinaryTree {
static class TreeNode{
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value){
this.value=value;
}
}
TreeNode root;
public BinaryTree(int[] array){
root=makeBinaryTreeByArray(array,1);
}
/**
* 采用递归的方式创建一颗二叉树
* 传入的是二叉树的数组表示法
* 构造后是二叉树的二叉链表表示法
*/
public static TreeNode makeBinaryTreeByArray(int[] array,int index){
if(index<array.length){
int value=array[index];
if(value!=0){
TreeNode t=new TreeNode(value);
array[index]=0;
t.left=makeBinaryTreeByArray(array,index*2);
t.right=makeBinaryTreeByArray(array,index*2+1);
return t;
}
}
return null;
}
/**
* 深度优先遍历,相当于先根遍历
* 采用非递归实现
* 需要辅助数据结构:栈
*/
public void depthOrderTraversal(){
if(root==null){
System.out.println("empty tree");
return;
}
ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
stack.push(root);
while(stack.isEmpty()==false){
TreeNode node=stack.pop();
System.out.print(node.value+" ");
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
System.out.print("\n");
}
/**
* 广度优先遍历
* 采用非递归实现
* 需要辅助数据结构:队列
*/
public void levelOrderTraversal(){
if(root==null){
System.out.println("empty tree");
return;
}
ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
queue.add(root);
while(queue.isEmpty()==false){
TreeNode node=queue.remove();
System.out.print(node.value+" ");
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
System.out.print("\n");
}
/**
* 13
* / \
* 65 5
* / \ \
* 97 25 37
* / /\ /
* 22 4 28 32
*/
public static void main(String[] args) {
int[] arr={0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};
BinaryTree tree=new BinaryTree(arr);
tree.depthOrderTraversal();
tree.levelOrderTraversal();
}
}
分享到:
相关推荐
内容概要:本文全面介绍了Scratch编程语言,包括其历史、发展、特点、主要组件以及如何进行基本和进阶编程操作。通过具体示例,展示了如何利用代码块制作动画、游戏和音乐艺术作品,并介绍了物理模拟、网络编程和扩展库等功能。 适合人群:编程初学者、教育工作者、青少年学生及对编程感兴趣的各年龄段用户。 使用场景及目标:①帮助初学者理解编程的基本概念和逻辑;②提高学生的创造力、逻辑思维能力和问题解决能力;③引导用户通过实践掌握Scratch的基本和高级功能,制作个性化作品。 其他说明:除了基础教学,文章还提供了丰富的学习资源和社区支持,帮助用户进一步提升技能。
mmexport1734874094130.jpg
基于simulink的悬架仿真模型,有主动悬架被动悬架天棚控制半主动悬架 [1]基于pid控制的四自由度主被动悬架仿真模型 [2]基于模糊控制的二自由度仿真模型,对比pid控制对比被动控制,的比较说明 [3]基于天棚控制的二自由度悬架仿真 以上模型,说明文档齐全,仿真效果明显
内容概要:本文档是《组合数学答案-网络流传版.pdf》的内容,主要包含了排列组合的基础知识以及一些经典的组合数学题目。这些题目涵盖了从排列数计算、二项式定理的应用到容斥原理的实际应用等方面。通过对这些题目的解析,帮助读者加深对组合数学概念和技巧的理解。 适用人群:适合初学者和有一定基础的学习者。 使用场景及目标:可以在学习组合数学课程时作为练习题参考,也可以在复习考试或准备竞赛时使用,目的是提高解决组合数学问题的能力。 其他说明:文档中的题目覆盖了组合数学的基本知识点,适合逐步深入学习。每个题目都有详细的解答步骤,有助于读者掌握解题思路和方法。
YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;
操作系统实验 Ucore lab5
基于matlab开发的学生成绩管理系统GUI界面,可以实现学生成绩载入,显示,处理及查询。
老版本4.0固件,(.dav固件包),支持7700N-K4,7900N-K4等K51平台,升级后出现异常或变砖可使用此版本。请核对自己的机器信息,确认适用后在下载。
YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;
YOLO算法-杂草检测项目数据集-3970张图像带标签-杂草.zip
E008 库洛米(3页).zip
内容概要:本文详细阐述了基于西门子PLC的晶圆研磨机自动控制系统的设计与实现。该系统结合了传感器技术、电机驱动技术和人机界面技术,实现了晶圆研磨过程的高精度和高效率控制。文中详细介绍了控制系统的硬件选型与设计、软件编程与功能实现,通过实验测试和实际应用案例验证了系统的稳定性和可靠性。 适合人群:具备一定的自动化控制和机械设计基础的工程师、研究人员以及从事半导体制造的技术人员。 使用场景及目标:本研究为半导体制造企业提供了一种有效的自动化解决方案,旨在提高晶圆研磨的质量和生产效率,降低劳动强度和生产成本。系统适用于不同规格晶圆的研磨作业,可以实现高精度、高效率、自动化的晶圆研磨过程。 阅读建议:阅读本文时,重点关注晶圆研磨工艺流程和技术要求,控制系统的硬件和软件设计方法,以及实验测试和结果分析。这将有助于读者理解和掌握该自动控制系统的实现原理和应用价值。
YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;
深圳建筑安装公司“挖掘机安全操作规程”
YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;
大题解题方法等4个文件.zip
保障性安居工程考评内容和评价标准.docx
监督机构检查记录表.docx
该项目适合初学者进行学习,有效的掌握java、swing、mysql等技术的基础知识。资源包含源码、视频和文档 资源下载|如果你正在做毕业设计,需要源码和论文,各类课题都可以,私聊我。 商务合作|如果你是在校大学生,正好你又懂语言编程,或者你可以找来需要做毕设的伙伴,私聊我。。内容来源于网络分享,如有侵权请联系我删除。另外如果没有积分的同学需要下载,请私信我。
218) Leverage - 创意机构与作品集 WordPress 主题 2.2.7.zip