Java二叉搜索树遍历操作详解【前序、中序、后序、层次、广度优先遍历】

本文实例讲述了Java二叉搜索树遍历操作。分享给大家供大家参考,具体如下:

前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树。

对于二叉树,有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图:

因为树的定义本身就是递归定义,所以对于前序、中序以及后序这三种遍历我们使用递归的方法实现,而对于广度优先遍历需要选择其他数据结构实现,本例中我们使用队列来实现广度优先遍历。

四种基本的遍历思想为:

前序遍历:根结点 ---> 左子树 ---> 右子树
中序遍历:左子树---> 根结点 ---> 右子树
后序遍历:左子树 ---> 右子树 ---> 根结点
层次遍历:从上到下,从左到右。

比如,以下二叉树的各种遍历:

前序遍历:5-3-2-4-6-8
中序遍历:2-3-4-5-6-8
后序遍历:2-4-3-8-6-5
层次遍历:5-3-6-2-4-8

一、前序遍历

依据上文提到的遍历思路:根结点 ---> 左子树 ---> 右子树,代码实现如下:

 //二分搜索树的前序遍历(前序遍历:根结点 ---> 左子树 ---> 右子树)
  public void preOrder() {
    preOrder(root);
  }

  //前序遍历以node为根的二分搜索树,递归算法
  private void preOrder(Node node) {
    if (node == null) {
      return;
    }
    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
  }

二、中序遍历

依据上文提到的遍历思路:左子树 ---> 根结点 ---> 右子树,代码实现如下:

  //二分搜索树的中序遍历(中序遍历:左子树---> 根结点 ---> 右子树)
  public void inOrder() {
    inOrder(root);
  }

  //中序遍历以node为根的二分搜索树,递归算法
  private void inOrder(Node node) {
    if (node == null) {
      return;
    }
    inOrder(node.left);
    System.out.println(node.e);
    inOrder(node.right);
  }

三、后序遍历

依据上文提到的遍历思路:左子树 ---> 右子树 ---> 根结点,代码实现如下:

  //二分搜索树的后序遍历(后序遍历:左子树 ---> 右子树 ---> 根结点)
  public void postOrder() {
    postOrder(root);
  }

  //后序遍历以node为根的二分搜索树,递归算法
  private void postOrder(Node node) {
    if (node == null) {
      return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
  }

四、层次遍历

对于层次遍历,我们基于队列来实现,思路如下:
(1)先在队列中增加根结点
(2)对于随意其余任意节点,在其出队列的时候访问(假设左孩子和右孩子有不为空的情况,入队列)
代码实现如下:

//层次遍历--(基于队列实现)
  public void levelOrder() {

    Queue<Node> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      Node cur = q.remove();
      System.out.println(cur.e);
      if (cur.left != null) {
        q.add(cur.left);
      }
      if (cur.right!=null){
        q.add(cur.right);
      }
    }
  }

源代码地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

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

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

时间: 2020-03-17

java实现 二叉搜索树功能

一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

Java创建二叉搜索树,实现搜索,插入,删除的操作实例

Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1.查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走! 2.插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致. 3.删除: 1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树:当被删节点

Java二叉搜索树基础原理与实现方法详解

本文实例讲述了Java二叉搜索树基础原理与实现方法.分享给大家供大家参考,具体如下: 前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树. 1 树 1.1 树的定义 树(Tree)是n(n>=0)个节点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的节点: (2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1.T2........Tn,其中每一个集合本身又是一棵树,并且称为根的子树. 此外,树的定义还需要强调以

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的二叉树排序以及遍历文件展示文本格式的文件树

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实现二叉树的深度优先遍历和广度优先遍历算法示例

本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

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实现按层遍历二叉树,按层遍历二叉树可以通过队列来实现.其主要思路如下: 1.先将根节点放入队列中 2.每次都从队列中取出一个结点打印该结点的值 3.若这个结点有子结点,则将它的子结点放入队列尾,知道队列为空. 实现代码如下: import java.util.LinkedList; import java.util.Queue; public class LayerTranverse { //按层遍历二叉树 public static void main(String

Java 实现二叉搜索树的查找、插入、删除、遍历

由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

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

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

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

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

Java实现红黑树(平衡二叉树)的详细过程

目录 前言 红黑二叉查找树 2-3树 2-3树的插入操作 实现红黑二叉树 结尾 前言 在实现红黑树之前,我们先来了解一下符号表. 符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.princeton.edu/home/ 符号表有时候被称为字典,就如同英语字典中,一个单词对应一个解释,符号表有时候又被称之为索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.总的来说,符号表就是将一个键和一个值联系起来,就如Python中的字典,JAVA中的HashMap

利用Java实现红黑树

目录 1.红黑树的属性 2.旋转 3.插入 4.删除 5.所有代码 6.演示 1.红黑树的属性 红黑树是一种二分查找树,与普通的二分查找树不同的一点是,红黑树的每个节点都有一个颜色(color)属性.该属性的值要么是红色,要么是黑色. 通过限制从根到叶子的任何简单路径上的节点颜色,红黑树确保没有比任何其他路径长两倍的路径,从而使树近似平衡. 假设红黑树节点的属性有键(key).颜色(color).左子节点(left).右子节点(right),父节点(parent). 一棵红黑树必须满足下面有下面

Java Map 按照Value排序的实现方法

Map是键值对的集合接口,它的实现类主要包括:HashMap,TreeMap,Hashtable以及LinkedHashMap等. •TreeMap:基于红黑树(Red-Black tree)的 NavigableMap 实现,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法. •HashMap的值是没有顺序的,它是按照key的HashCode来实现的,对于这个无序的HashMap我们要怎么来实现排序呢?参照TreeMap的va

Java模拟QQ桌面截图功能实现方法

本文实例讲述了Java模拟QQ桌面截图功能实现方法.分享给大家供大家参考.具体如下: QQ的桌面截图功能非常方便,去年曾用Java模拟过一个,现整理出来. 本方法首先需要抓到屏幕的整个图象,将图象显示在一个JFrame中,再将JFrame全屏显示,这样就模拟出了一个桌面,Java也就可以获得鼠标的作用区域从而实现桌面中的小范围截屏. import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import

Java基于Socket的文件传输实现方法

本文实例讲述了Java基于Socket的文件传输实现方法.分享给大家供大家参考,具体如下: 1. Java代码如下: package sterning; import java.io.BufferedInputStream; import java.io.DataInputStream; import java.io.DataOutputStream; import java.io.File; import java.io.FileInputStream; import java.net.Ser

Java线程池的几种实现方法及常见问题解答

工作中,经常会涉及到线程.比如有些任务,经常会交与线程去异步执行.抑或服务端程序为每个请求单独建立一个线程处理任务.线程之外的,比如我们用的数据库连接.这些创建销毁或者打开关闭的操作,非常影响系统性能.所以,"池"的用处就凸显出来了. 1. 为什么要使用线程池 在3.6.1节介绍的实现方式中,对每个客户都分配一个新的工作线程.当工作线程与客户通信结束,这个线程就被销毁.这种实现方式有以下不足之处: •服务器创建和销毁工作的开销( 包括所花费的时间和系统资源 )很大.这一项不用解释,可以

java和c#使用hessian通信的方法

本文实例讲述了java和c#使用hessian通信的方法,是非常实用的技巧.分享给大家供大家参考.具体分析如下: 首先,hessian主页为:http://hessian.caucho.com/ 下面通过一个简单的例子学习hessian服务:服务端为Java,客户端为C#. 先要准备好C#和Java的第三方类库,下载地址:http://hessian.caucho.com/ 下载 Hssiancharp.dll及hessian-4.0.37.jar Hessian服务端(java): 打开ecl

Java实现给网站上传图片盖章的方法

本文实例讲述了Java实现给网站上传图片盖章的方法.分享给大家供大家参考.具体如下: 最近无聊,上了一会校友录,觉的校友录的图片都会加入一个章,呵呵,自己也就做了一个,不过只适合jpg格式.发出来给大家研究研究.欢迎讨论! 很老的代码了 /************************************************ * <p>java对图片的操作(只能使用jpg)</p> * 对图片的签章<br> * 对图片的缩图<br> * <p

java中常见的死锁以及解决方法代码

在java中我们常常使用加锁机制来确保线程安全,但是如果过度使用加锁,则可能导致锁顺序死锁.同样,我们使用线程池和信号量来限制对资源的使用,但是这些被限制的行为可能会导致资源死锁.java应用程序无法从死锁中恢复过来,因此设计时一定要排序那些可能导致死锁出现的条件. 1.一个最简单的死锁案例 当一个线程永远地持有一个锁,并且其他线程都尝试获得这个锁时,那么它们将永远被阻塞.在线程A持有锁L并想获得锁M的同时,线程B持有锁M并尝试获得锁L,那么这两个线程将永远地等待下去.这种就是最简答的死锁形式(