二叉树的深度优先遍历（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;
}
}
。。
相关推荐
本话题主要探讨如何使用非递归算法对无向图进行深度优先遍历（DFS, Depth First Search）和广度优先遍历（BFS, Breadth First Search），这两种遍历方法在图算法中有着广泛的应用。 **1. 邻接表表示法** 在处理大...
本篇文章将深入探讨如何使用Java来实现二叉树的深度优先遍历（DFS, Depth First Search）和广度优先遍历（BFS, Breadth First Search）。 **深度优先遍历** 是一种在图或树中搜索的方法，它尽可能深地探索树的分支...
本文详细介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法，通过实例代码展示了深度优先遍历和广度优先遍历的实现过程，并对二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧进行了详细...
二叉树广度和深度优先遍历，通过递归算法实现二叉树的建立，利用递归算法实现深度优先遍历，使用队列实现广度优先遍历
二叉树的深度优先搜索和广度优先搜索都是常用的搜索算法，它们可以用于遍历二叉树中的所有节点。深度优先搜索可以用于查找二叉树中的某个节点，而广度优先搜索可以用于遍历二叉树中的所有节点。
总之，掌握二叉树的深度遍历和广度遍历是理解和应用数据结构的关键。通过学习这些基本操作，可以更好地解决实际问题，例如在搜索、排序、图论等领域。在实际编程中，理解并灵活运用这些方法，能够提高代码的效率和...
本资料包主要探讨的是图的两种经典遍历方法：深度优先遍历（DFS，Depth-First Search）和广度优先遍历（BFS，Breadth-First Search）。 深度优先遍历是一种用于遍历或搜索树或图的算法，其基本思想是从起点开始，尽...
在这个主题下，我们将深入探讨深度优先遍历（DFS, Depth First Search）和广度优先遍历（BFS, Breadth First Search），以及在树结构中常见的先序、中序和后序遍历。这些遍历方法各有其特点，适用于不同的问题场景。...
在计算机科学中，树是一种非线性数据结构，它由顶点（节点）和连接这些顶点的边组成。在处理树形结构时，遍历是...通过查看和学习这些文件，你可以更深入地了解如何在JavaScript环境下实现树的深度优先和广度优先遍历。
以下是使用C语言编写的二叉树的广度优先遍历（也称为层次遍历）算法的示例代码： #include #include // 定义二叉树的节点结构 typedef struct Node { int data; struct Node* left; struct Node* right; } ...
二叉树的先序，中序，后序递归，非递归遍历和广度优先遍历。此程序是用C语言写的。
本篇文章将深入探讨如何使用JS进行二叉树的广度优先遍历（BFS）。 **一、二叉树的基础概念** 二叉树的基本元素是节点，每个节点包含三个部分：数据、左指针和右指针。在JS中，我们可以创建一个Node类来表示二叉树...
本压缩包提供了一份针对新手学习C语言实现数据结构和算法的资源，特别关注了图的深度优先遍历与广度优先遍历、二叉查找树、二叉树、堆排序算法以及KMP算法。以下是这些知识点的详细说明： 1. **图的深度优先遍历...
二叉树的层次遍历：广度优先搜索（BFS）算法详解与Python实现
本篇文章将重点关注广度优先搜索，即“二叉树遍历广度优先”。 广度优先搜索（BFS）是一种在图或树中寻找路径的算法，它从根节点开始，然后逐层地访问所有相邻节点。在二叉树中，这意味着从根节点开始，先访问所有...
深度优先遍历的实现； 广度优先遍历的实现；
二叉树深度优先遍历、广度优先遍历{非递归}
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考，具体如下： 广度优先(层次遍历) 从树的root开始，从上到下从左到右遍历整个树的节点 数和二叉树的区别就是，二叉树只有左右两个...
在这个压缩包中，包含了一个用C语言实现的程序，用于执行图的深度优先遍历（DFS, Depth-First Search）和广度优先遍历（BFS, Breadth-First Search）。以下是这两个遍历方法的详细解释： 1. **深度优先遍历（DFS）*...