深度遍历,即尽可能往树的纵深的方向搜索,所以优先深入遍历树的左节点,直至叶子节点,再往回遍历已遍历的节点的右节点。使用栈来实现
package com.practice;
import java.util.LinkedList;
public class DepthFirstSearch {
public static TreeNode createTree(int[] arr, int i) {
TreeNode root = null;
if(i<arr.length) {
root = new TreeNode(arr[i]);
root.left = createTree(arr, 2*i+1);
root.right = createTree(arr, 2*i+2);
}
return root;
}
public static void search(int[] arr) {
TreeNode root = createTree(arr, 0);
if(root==null) return;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
while(!list.isEmpty()) {
TreeNode node = list.pop();
System.out.print(node.val+",");
if(node.right!=null) list.push(node.right);
if(node.left!=null) list.push(node.left);
}
}
public static void main(String[] args) {
int[] arr = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };
search(arr);
}
}
广度优先遍历,即层序遍历,优先将根节点遍历完,再遍历根节点的子节点。使用队列来实现
package com.practice;
import java.util.LinkedList;
import java.util.Queue;
public class WidthFirstSearch {
public static TreeNode createTree(int[] arr, int i) {
TreeNode root = null;
if(i<arr.length) {
root = new TreeNode(arr[i]);
root.left = createTree(arr, 2*i+1);
root.right = createTree(arr, 2*i+2);
}
return root;
}
public static void search(int[] arr) {
TreeNode root = createTree(arr, 0);
if(root==null) return;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i=0;i<size;i++) {
TreeNode node = queue.poll();
System.out.print(node.val+",");
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
}
}
public static void main(String[] args) {
int[] arr = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };
search(arr);
}
}
分享到:
相关推荐
实现二叉树的深度遍历广度遍历等关于二叉树的基本操作
二叉树广度和深度优先遍历,通过递归算法实现二叉树的建立,利用递归算法实现深度优先遍历,使用队列实现广度优先遍历
二叉树的遍历:二叉树的各种遍历 图的遍历:图的深度遍历,广度遍历 一元多项式的相关设计: 停车场的课程设计(堆栈和队列的使用,停车出车) 迷宫的递归算法(需要修改)
给定一个二叉树的数据结构,通过JavaScript实现二叉树的广度遍历和深度遍历。
二叉树深度优先遍历、广度优先遍历{非递归}
前序遍历 中序遍历 后序遍历 深度遍历 广度遍历 插入排序 选择排序 冒泡排序 快速排序 堆排序 希尔排序 合并排序 快速3排序
主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
C++版的二叉树遍历源码,包括:广度优先、深度优先、先序遍历(递归/非递归)、中序遍历(递归/非递归)、后序遍历(递归/非递归)。
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
深度优先遍历的实现; 广度优先遍历的实现;
//广度优先遍历 void BFSPrint(Node *p); //深度优先遍历 void DFSPrint(Node *p); //插入操作 void Insert(Info key); //插入节点 void InsertNode(Node *&root;,Info key); //删除操作 void Remove(Info...
NULL 博文链接:https://redhacker.iteye.com/blog/413606
对于二叉树,有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很...
包括两个程序,一个实现二叉树的三种递归遍历,求结点数,求深度,求广度,另一个实现二叉树的非递归遍历,经调试无误
二叉树的遍历 PHP遍历二叉树的实现,深度优先,广度优先,非递归实现;
算法-二叉树的深度优先和广度优先遍历(包含源程序).rar
主要介绍了PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次),结合实例形式详细分析了php针对二叉树的深度优先遍历与广度优先遍历相关操作技巧与注意事项,需要的朋友可以参考下
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
数据结构二叉树,先序,中序,后序遍历,深度,广度优先搜索,所有的功能一应俱全,大家可以自行组装,别忘了,评分哦