原题出自百度的笔试:
简述树的深度优先及广度优先遍历算法,并说明非递归实现。
当时我看到这个题目的时候,已经完全记不得非递归算法该怎么实现了,后来查阅了一下,要用到两个辅助的数据结构:
深度优先遍历--->栈;
广度优先遍历--->队列;
这里以二叉树为例来实现。
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();
}
}
分享到:
相关推荐
深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现 深度优先遍历 广度优先遍历 的实现
图的深度遍历和广度遍历是两个重要的算法,这也是我们理解并掌握图这一数据结构的基础。通过此程序算法可以进一步掌握图的构造以及遍历的相关知识。
在邻接矩阵的存储结构下,实现图的深度优先遍历和广度优先遍历。
无向图的连接表存储结构的创建算法 从编号为v的顶点出发,深度优先遍历图的算法 对具有G.vexnum个顶点的图的深度优先遍历的算法 从图G的v顶点出发,广度优先遍历图的...对具有G.vexnum个顶点的图的广度优先遍历的算法
本源文件CPP中代码使用深度优先和广度优先遍历图的算法。
程序设计任务: 设计一个程序,实现以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。基本要求:以邻接表或者邻接矩阵为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的...
javascript通过递归和栈实现树深度优先遍历和广度优先遍历
C++编写的图的存储与深度优先与广度优先遍历
深度优先遍历和广度优先遍历 建立图的应用等等
树的深度优先遍历与广度优先遍历树的深度优先遍历与广度优先遍历
图的遍历,非常经典啊,包括深度优先和广度优先遍历以及先序、中序、和后序等等,只有你想不到,没有我做不到的,希望对你有所帮助。
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
实现图的深度与广度优先遍历 c++6.0运行
数据结构中的图结构,其中最重要的两个遍历算法——深度优先遍历与广度优先遍历
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 注: 1.代码共182行。 2.代码经过多次编译运行,无错误。
本程序方便的实现了图的深度、广度优先遍历。是数据结构中的一部分,现与大家分享
本资源是用C语言所写的,数据结构中图的创建及其相关的深度,广度遍历
直接演示:求深度优先遍历、广度优先遍历、最短路径、最小生成树
图的深度优先遍历和广度优先遍历
数据结构有关的图的深度优先和广度优先遍历