Java实现二叉树的深度优先遍历和广度优先遍历算法示例

本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法。分享给大家供大家参考,具体如下:

1. 分析

二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。

深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。具体说明如下:

先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。

后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。

2. 举例说明

对下图所示的二叉排序树进行遍历,要求使用先序遍历(递归、非递归)、中序遍历(递归、非递归)、后序遍历(递归、非递归)和广度优先遍历。

① 参考代码

package BinaryTreeTraverseTest;
import java.util.LinkedList;
import java.util.Queue;
/**
 * 二叉树的深度优先遍历和广度优先遍历
 * @author Fantasy
 * @version 1.0 2016/10/05 - 2016/10/07
 */
public class BinaryTreeTraverseTest {
  public static void main(String[] args) {
  BinarySortTree<Integer> tree = new BinarySortTree<Integer>();
    tree.insertNode(35);
    tree.insertNode(20);
    tree.insertNode(15);
    tree.insertNode(16);
    tree.insertNode(29);
    tree.insertNode(28);
    tree.insertNode(30);
    tree.insertNode(40);
    tree.insertNode(50);
    tree.insertNode(45);
    tree.insertNode(55);
    System.out.print("先序遍历(递归):");
    tree.preOrderTraverse(tree.getRoot());
    System.out.println();
    System.out.print("中序遍历(递归):");
    tree.inOrderTraverse(tree.getRoot());
    System.out.println();
    System.out.print("后序遍历(递归):");
    tree.postOrderTraverse(tree.getRoot());
    System.out.println();
    System.out.print("先序遍历(非递归):");
    tree.preOrderTraverseNoRecursion(tree.getRoot());
    System.out.println();
    System.out.print("中序遍历(非递归):");
    tree.inOrderTraverseNoRecursion(tree.getRoot());
    System.out.println();
    System.out.print("后序遍历(非递归):");
    tree.postOrderTraverseNoRecursion(tree.getRoot());
    System.out.println();
    System.out.print("广度优先遍历:");
    tree.breadthFirstTraverse(tree.getRoot());
  }
}
/**
 * 结点
 */
class Node<E extends Comparable<E>> {
  E value;
  Node<E> left;
  Node<E> right;
  Node(E value) {
    this.value = value;
    left = null;
    right = null;
  }
}
/**
 * 使用一个先序序列构建一棵二叉排序树(又称二叉查找树)
 */
class BinarySortTree<E extends Comparable<E>> {
  private Node<E> root;
  BinarySortTree() {
    root = null;
  }
  public void insertNode(E value) {
    if (root == null) {
      root = new Node<E>(value);
      return;
    }
    Node<E> currentNode = root;
    while (true) {
      if (value.compareTo(currentNode.value) > 0) {
        if (currentNode.right == null) {
          currentNode.right = new Node<E>(value);
          break;
        }
        currentNode = currentNode.right;
      } else {
        if (currentNode.left == null) {
          currentNode.left = new Node<E>(value);
          break;
        }
        currentNode = currentNode.left;
      }
    }
  }
  public Node<E> getRoot(){
    return root;
  }
  /**
   * 先序遍历二叉树(递归)
   * @param node
   */
  public void preOrderTraverse(Node<E> node) {
    System.out.print(node.value + " ");
    if (node.left != null)
      preOrderTraverse(node.left);
    if (node.right != null)
      preOrderTraverse(node.right);
  }
  /**
   * 中序遍历二叉树(递归)
   * @param node
   */
  public void inOrderTraverse(Node<E> node) {
    if (node.left != null)
      inOrderTraverse(node.left);
    System.out.print(node.value + " ");
    if (node.right != null)
      inOrderTraverse(node.right);
  }
  /**
   * 后序遍历二叉树(递归)
   * @param node
   */
  public void postOrderTraverse(Node<E> node) {
    if (node.left != null)
      postOrderTraverse(node.left);
    if (node.right != null)
      postOrderTraverse(node.right);
    System.out.print(node.value + " ");
  }
  /**
   * 先序遍历二叉树(非递归)
   * @param root
   */
  public void preOrderTraverseNoRecursion(Node<E> root) {
    LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
    Node<E> currentNode = null;
    stack.push(root);
    while (!stack.isEmpty()) {
      currentNode = stack.pop();
      System.out.print(currentNode.value + " ");
      if (currentNode.right != null)
        stack.push(currentNode.right);
      if (currentNode.left != null)
        stack.push(currentNode.left);
    }
  }
  /**
   * 中序遍历二叉树(非递归)
   * @param root
   */
  public void inOrderTraverseNoRecursion(Node<E> root) {
    LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
    Node<E> currentNode = root;
    while (currentNode != null || !stack.isEmpty()) {
      // 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
      while (currentNode != null) {
        stack.push(currentNode);
        currentNode = currentNode.left;
      }
      currentNode = stack.pop();
      System.out.print(currentNode.value + " ");
      currentNode = currentNode.right;
    }
  }
  /**
   * 后序遍历二叉树(非递归)
   * @param root
   */
  public void postOrderTraverseNoRecursion(Node<E> root) {
    LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
    Node<E> currentNode = root;
    Node<E> rightNode = null;
    while (currentNode != null || !stack.isEmpty()) {
      // 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
      while (currentNode != null) {
        stack.push(currentNode);
        currentNode = currentNode.left;
      }
      currentNode = stack.pop();
      // 当前结点没有右结点或上一个结点(已经输出的结点)是当前结点的右结点,则输出当前结点
      while (currentNode.right == null || currentNode.right == rightNode) {
        System.out.print(currentNode.value + " ");
        rightNode = currentNode;
        if (stack.isEmpty()) {
          return; //root以输出,则遍历结束
        }
        currentNode = stack.pop();
      }
      stack.push(currentNode); //还有右结点没有遍历
      currentNode = currentNode.right;
    }
  }
  /**
   * 广度优先遍历二叉树,又称层次遍历二叉树
   * @param node
   */
  public void breadthFirstTraverse(Node<E> root) {
    Queue<Node<E>> queue = new LinkedList<Node<E>>();
    Node<E> currentNode = null;
    queue.offer(root);
    while (!queue.isEmpty()) {
      currentNode = queue.poll();
      System.out.print(currentNode.value + " ");
      if (currentNode.left != null)
        queue.offer(currentNode.left);
      if (currentNode.right != null)
        queue.offer(currentNode.right);
    }
  }
}

② 输出结果

先序遍历(递归):35 20 15 16 29 28 30 40 50 45 55
中序遍历(递归):15 16 20 28 29 30 35 40 45 50 55
后序遍历(递归):16 15 28 30 29 20 45 55 50 40 35
先序遍历(非递归):35 20 15 16 29 28 30 40 50 45 55
中序遍历(非递归):15 16 20 28 29 30 35 40 45 50 55
后序遍历(非递归):16 15 28 30 29 20 45 55 50 40 35
广度优先遍历:35 20 40 15 29 50 16 28 30 45 55

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

您可能感兴趣的文章:

  • 图解红黑树及Java进行红黑二叉树遍历的方法
  • java实现二叉树的创建及5种遍历方法(总结)
  • 图解二叉树的三种遍历方式及java实现代码
  • Java的二叉树排序以及遍历文件展示文本格式的文件树
  • java 完全二叉树的构建与四种遍历方法示例
  • Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
  • Java中二叉树的建立和各种遍历实例代码
  • Java编程实现深度优先遍历与连通分量代码示例
  • java图的深度优先遍历实现随机生成迷宫
  • Java实现利用广度优先遍历(BFS)计算最短路径的方法
  • 基于Java实现的图的广度优先遍历算法
(0)

相关推荐

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • java图的深度优先遍历实现随机生成迷宫

    最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢. 1.从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问. 2.对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访

  • Java编程实现深度优先遍历与连通分量代码示例

    深度优先遍历 深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达. 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点. 当回退到的路口已没有可走的通道时继续回退. 而连通分量,看概念:无向图G的极大连通子图称为G的连通分量( Connected Component).任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量. 下面看看具体实例: package com.dataStructure.gra

  • Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • Java中二叉树的建立和各种遍历实例代码

    这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序->建树 假设现在有个二叉树,如下: 此时遍历顺序是: PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG 现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树 或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的 树节点的定义: class Tree{ char val; Tree lef

  • java 完全二叉树的构建与四种遍历方法示例

    本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下. 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素检查是其是

  • Java的二叉树排序以及遍历文件展示文本格式的文件树

    Java二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的3个特征: 1:当前node的所有左孩子的值都小于当前node的值: 2:当前node的所有右孩子的值都大于当前node的值: 3:孩子节点也满足以上两点 package test.sort; public class BinaryNode { private int value;//current value private BinaryNode lChild;//left chil

  • java实现二叉树的创建及5种遍历方法(总结)

    用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

  • 图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • Java实现利用广度优先遍历(BFS)计算最短路径的方法

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

随机推荐

其他