二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）
深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
深度优先遍历有先、中、后序方式，方法可以递归和非递归
广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。(从根节点开始，一层一层遍历)
DFS:ABDECFG
BFS:ABCDEFG
DFS实现：
数据结构：栈
父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可
BFS实现：
数据结构：队列
父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可
package com.test;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/**
* 树的遍历方式 深度优先遍历：递归和非递归两种 广度优先遍历：
*
*/
public class PrintTree {
public static void main(String[] args) {
TreeNode tree = createTree();
// System.out.println("递归方式先序遍历：");
// ForeachTree.rePreTree(tree);
//System.out.println("非递归方式先序遍历：");
//ForeachTree.nRePreTree(tree);
//System.out.println();
//ForeachTree.nRePreTree2(tree);
// System.out.println("递归方式中序遍历：");
//ForeachTree.reInTree(tree);
// System.out.println("非递归方式中序遍历：");
ForeachTree.nReInTree(tree);
// System.out.println("递归方式后序遍历：");
// ForeachTree.reEndTree(tree);
// System.out.println("非递归方式后序遍历：");
// ForeachTree.nReEndTree(tree);
//System.out.println("广度优先遍历：");
//ForeachTree.BFSTree(tree);
}
/**
* 创建一个用作测试的树
*
* @return
*/
public static TreeNode createTree() {
/*
* 示例：
* 1
* 2 3
* 4 5 6 7
* 8 9
*/
TreeNode root = new TreeNode(1);
TreeNode left1Tree = new TreeNode(2);
TreeNode left2Tree = new TreeNode(4);
TreeNode left3Tree = new TreeNode(8);
TreeNode left4Tree = new TreeNode(6);
TreeNode right1Tree = new TreeNode(5);
TreeNode right2Tree = new TreeNode(9);
TreeNode right3Tree = new TreeNode(3);
TreeNode right4Tree = new TreeNode(7);
left2Tree.leftNode = left3Tree;
right1Tree.rightNode = right2Tree;
left1Tree.leftNode = left2Tree;
left1Tree.rightNode = right1Tree;
right3Tree.leftNode = left4Tree;
right3Tree.rightNode = right4Tree;
root.leftNode = left1Tree;
root.rightNode = right3Tree;
return root;
}
}
class ForeachTree {
/**
* 先序遍历：根左右的顺序--递归方式
*
* @param tree
*/
public static void rePreTree(TreeNode tree) {
if (tree != null) {
System.out.println(tree.val);
rePreTree(tree.leftNode);
rePreTree(tree.rightNode);
}
}
/**
* 先序遍历：根左右的顺序--非递归方式
* 思路：
* 1. 获取当前节点，首先输出当前节点，然后将其两个节点压入栈中，然后利用栈的先进后出的特性，弹出节点并获取其子节点
* 2. 在此判断条件为当前节点不为空，若为空则直接结束本次循环然后进行下一次循环
* @param tree
*/
public static void nRePreTree(TreeNode tree) {
// 创建栈，由于深度遍历是
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(tree);
while (stack != null && !stack.isEmpty()) {
TreeNode te = stack.pop();
System.out.println(te.val);
List<TreeNode> trees = te.getChildren();
if(trees == null) continue;
for(TreeNode t:trees) {
if(t!=null) {
stack.push(t);
}
}
}
}
public static void nRePreTree2(TreeNode tree) {
// 创建栈，由于深度遍历是
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(tree);
while (stack != null && !stack.isEmpty()) {
TreeNode te = stack.pop();
System.out.println(te.val);
if(te.rightNode != null){
stack.push(te.rightNode);
}
if(te.leftNode != null){
stack.push(te.leftNode);
}
}
}
/**
* 中序遍历：左根右的顺序--递归方式
*
* @param tree
*/
public static void reInTree(TreeNode tree) {
if (tree != null) {
reInTree(tree.leftNode);
System.out.println(tree.val);
reInTree(tree.rightNode);
}
}
/**
* 中序遍历：左根右的顺序--非递归方式
* 思路：
* 1. 由于中序遍历方式为左根右，所以先判断当前节点是否有左子节点，若有的话将当前节点的左子节点置为空（防止下次遍历到重复判
* 断）再压入栈，然后将当前节点的左子节点压入栈，一次类推
* 2. 直到当前节点没有左子节点时，输出当前节点的值，然后判断是否有右子节点，若有的话则继续进行压栈操作（在此有一技巧之处在
* 于若该节点的左右子节点都没有的话，则不需要将当前节点压入栈--在第一次获取当前节点时已经将当前节点弹出了）
* 3. 注：只有在当前节点有左子节点时需要将当前节点压入栈，因为遍历顺序为左中右，所以在当前节点有左节点时，需要再进行回根节
* 点查找输出根节点的值，若当前节点没有左节点时，则不需要记录上一节点
* @param tree
*/
public static void nReInTree(TreeNode tree) {
// 创建栈，由于深度遍历是
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(tree);
while(stack != null && !stack.isEmpty()) {
TreeNode root = stack.pop();
if(root.leftNode != null) {
TreeNode left = root.leftNode;
root.leftNode = null;
stack.push(root);
stack.push(left);
}else {
System.out.println(root.val);
if(root.rightNode != null) {
TreeNode right = root.rightNode;
stack.push(right);
}
}
}
}
/**
* 后序遍历：左右根的顺序--递归方式
*
* @param tree
*/
public static void reEndTree(TreeNode tree) {
if (tree != null) {
reEndTree(tree.leftNode);
reEndTree(tree.rightNode);
System.out.println(tree.val);
}
}
/**
* 后序遍历：左右根的顺序--非递归方式
*
* @param tree
*/
public static void nReEndTree(TreeNode tree) {
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(tree);
while( stack != null && !stack.isEmpty()) {
TreeNode root = stack.pop();
if(root.leftNode != null) {
TreeNode left = root.leftNode;
root.leftNode = null;
stack.push(root);
stack.push(left);
}else if(root.rightNode != null) {
TreeNode right = root.rightNode;
root.rightNode = null;
stack.push(root);
stack.push(right);
}else {
System.out.println(root.val);
}
}
}
/**
* 广度优先遍历
*
* @param tree
*/
public static void BFSTree(TreeNode tree) {
Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.push(tree);
while (queue != null && !queue.isEmpty()) {
TreeNode root = queue.pop();
System.out.println(root.val);
if (root.leftNode != null) {
queue.add(root.leftNode);
}
if (root.rightNode != null) {
queue.add(root.rightNode);
}
}
}
}
class TreeNode {
int val;
public TreeNode(int val) {
this.val = val;
}
TreeNode leftNode;
TreeNode rightNode;
/**
* 获取该节点的所有左右子节点-先右后左
* 由于所有遍历方式都是从左向右的顺序，所以压入栈时需要先将右子节点压入，后将左子节点压入，
* 因此在此获取子节点时先添加右子节点，后添加左子节点
* @return
*/
public List<TreeNode> getChildren() {
List<TreeNode> list = new LinkedList<TreeNode>();
if (this.rightNode != null)
list.add(this.rightNode);
if (this.leftNode != null)
list.add(this.leftNode);
return list.size() == 0 ? null : list;
}
}
。。
相关推荐
二叉树广度和深度优先遍历，通过递归算法实现二叉树的建立，利用递归算法实现深度优先遍历，使用队列实现广度优先遍历
实现二叉树的深度遍历广度遍历等关于二叉树的基本操作
主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
NULL 博文链接：https://redhacker.iteye.com/blog/413606
js代码-二叉树广度优先遍历
二叉树的先序，中序，后序递归，非递归遍历和广度优先遍历。此程序是用C语言写的。
主要介绍了PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次),结合实例形式详细分析了php针对二叉树的深度优先遍历与广度优先遍历相关操作技巧与注意事项,需要的朋友可以参考下
深度优先遍历的实现； 广度优先遍历的实现；
二叉树深度优先遍历、广度优先遍历{非递归}
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考，具体如下： 广度优先(层次遍历) 从树的root开始，从上到下从左到右遍历整个树的节点 数和二叉树的区别就是，二叉树只有左右两个...
二叉树遍历广度优先
算法-二叉树的深度优先和广度优先遍历（包含源程序）.rar
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考，具体如下： 广度优先(层次遍历) 从树的root开始，从上到下从左到右遍历整个树的节点 数和二叉树的区别就是，二叉树只有左右两个...
本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法。分享给大家供大家参考。具体如下： #二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $...
深度优先遍历和广度优先遍历三、面试题+励志 这不就是二叉树吗？嗯，风景都在提示我该学学二叉树了 一、什么是深度优先遍历 深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点...
实现由先序、中序序列构造二叉树，由后序、中序序列构造二叉树，广度优先遍历以root为根结点的子树，中序遍历（递归，非递归）以root为根结点的子树
从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。【中科院软件所 1999 六、2-（1）（2分）】 ①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均...