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

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题

先序+中序->建树

假设现在有个二叉树,如下:

此时遍历顺序是:

PreOrder: GDAFEMHZ
InOrder: ADEFGHMZ
PostOrder: AEFDHZMG

现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树
或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的

树节点的定义:

class Tree{
	char val;
	Tree left;
	Tree right;
	Tree(char val, Tree left, Tree right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
	Tree(){
	}
	Tree(char val){
		this.val = val;
		this.left = null;
		this.right =null;
	}
}

建树:

public static Tree buildTree(char[] preOrder, char[] inOrder){
	//preOrder是先序序列
	//inOrder是中序序列
	if(preOrder == null || preOrder.length == 0){
		return null;
	}
	Tree root = new Tree(preOrder[0]);
	//找到inOrder中的root的位置
	int inOrderIndex = 0;
	for (char i = 0; i < inOrder.length; i++){
		if(inOrder[i] == root.val){
			inOrderIndex = i;
		}
	}
	//preOrder的左子树和右子树部分
	char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);
	char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length);
	//inOrder的左子树和右子树部分
	char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex);
	char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length);
	//递归建立左子树和右子树
	Tree leftChild = buildTree(preOrderLeft, inOrderLeft);
	Tree rightChild = buildTree(preOrderRight, inOrderRight);
	root.left = leftChild;
	root.right = rightChild;
	return root;
}

中序+后序去建树其实是一样的,此处不写了

各种遍历

后序遍历

public static void postOrderPrint(Tree root){
    //后续遍历
    //左右根
    if(root.left != null){
      postOrderPrint(root.left);
    }
    if(root.right != null){
      postOrderPrint(root.right);
    }
    System.out.print(root.val + " ");
  }

举一反三,先序和中序是一样的,此处不写了

层序遍历

可以用一个队列Queue,初始先把root节点加入到队列,当队列不为空的时候取队列头的节点node,打印node的节点值,如果node的左右孩子不为空将左右孩子加入到队列中即可

public static void layerOrderPrint(Tree root){
    if(root == null){
      return;
    }
    //层序遍历
    Queue<Tree> qe = new LinkedList<Tree>();
    qe.add(root);
    while(!qe.isEmpty()){
      Tree node = qe.poll();
      System.out.print(node.val + " ");
      if(node.left != null){
        qe.add(node.left);
      }
      if(node.right != null){
        qe.add(node.right);
      }
    }
  }

深度优先和广度优先

其实就是换个说法而已,深度优先不就是先序遍历嘛,广度优先就是层序遍历

public static void deepFirstPrint(Tree root){
    //深度优先遍历等价于先序遍历
    //所以可以直接使用先序遍历
    if(root == null){
      return;
    }
    System.out.print(root.val + " ");
    if(root.left != null){
      deepFirstPrint(root.left);
    }
    if(root.right != null){
      deepFirstPrint(root.right);
    }
  }

public static void deepFirstPrintNoneRec(Tree root){
    //深度优先遍历的非递归形式
    if(root == null){
      return;
    }
    Stack<Tree> st = new Stack<Tree>();
    st.add(root);
    while(!st.isEmpty()){
      Tree node = st.pop();
      System.out.print(node.val + " ");
      //栈是后进先出的
      //先加右孩子后加左孩子
      if(node.right != null){
        st.add(node.right);
      }
      if(node.left != null){
        st.add(node.left);
      }
    }
  }

main函数:

public static void main(String[] args) {
    char[] preOrder = "GDAFEMHZ".toCharArray();
    char[] inOrder = "ADEFGHMZ".toCharArray();
    Tree root = Main.buildTree(preOrder, inOrder);
//   Main.postOrderPrint(root); //后序遍历
//   Main.layerOrderPrint(root); //层序遍历
//   Main.deepFirstPrint(root); //深度优先遍历
//   Main.deepFirstPrintNoneRec(root); //深度优先遍历的非递归版本
  }

总结

以上就是本文关于Java中二叉树的建立和各种遍历实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

Java编程求二叉树的镜像两种方法介绍

Java语言描述二叉树的深度和宽度

Java二叉树路径和代码示例

如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

您可能感兴趣的文章:

  • Java完全二叉树的创建与四种遍历方法分析
  • 图解二叉树的三种遍历方式及java实现代码
  • 详解java实现遍历二叉树的三种情况
  • java实现二叉树的创建及5种遍历方法(总结)
  • java 完全二叉树的构建与四种遍历方法示例
  • 图解红黑树及Java进行红黑二叉树遍历的方法
  • Java的二叉树排序以及遍历文件展示文本格式的文件树
(0)

相关推荐

  • 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二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的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 完全二叉树的构建与四种遍历方法示例

    本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下. 有如下的一颗完全二叉树: 先序遍历结果应该为: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实现代码

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

  • 详解java实现遍历二叉树的三种情况

    遍历二叉树,从上往下遍历.但是同层节点可以从左向右遍历,也可以从右向左遍历(也就是之字型遍历),其中,都需要队列进行实现.只是按照之字型稍微麻烦一些. (1)从上往下打印出二叉树的每个节点,同层节点从左至右打印. 需要一个队列,队列里面放节点(从根节点开始),然后依次进行打印. import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; class TreeNode{ int val = 0;

  • Java完全二叉树的创建与四种遍历方法分析

    本文实例讲述了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中二叉树的建立和各种遍历实例代码

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

  • java 对文件夹目录进行深度遍历实例代码

    java 对文件夹目录进行深度遍历实例代码 1.题目 对指定目录进行所有内容的列出(包含子目录中的内容),也可以理解为对目录进行深度遍历. 2.解题思想 从电脑中获取文件目录,建立函数对其遍历,在这个函数中需要对该目录中的每个文件进行判断,如果文件还是目录,则调用函数本身继续对其进行遍历,如果文件不是目录,则直接输出文件名.为了加强显示的效果,我们还可以建立一个getSpace函数,对其进行缩进. 需要注意的是,不要直接遍历C盘的内容,其目录层次太深,含有太多的系统级文件,容易返回为空,导致空指

  • 一篇文章彻底弄懂Java中二叉树

    目录 一.树形结构 1.1 相关概念 1.2树的表示形式 1.3树的应用:文件系统管理(目录和文件) 二.二叉树 2.1相关概念 2.2 二叉树的基本形态 2.3 两种特殊的二叉树 2.4 二叉树的性质 2.5 二叉树的存储 2.6 二叉树的基本操作 2.6.1二叉树的遍历 2.6.2 二叉树的基本操作 总结 一.树形结构 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.它具有以下的特点:

  • 详解Java中二叉树的基础概念(递归&迭代)

    目录 1.树型结构 1.1概念 1.2概念(重要) 2.二叉树(重点) 2.1概念 2.2二叉树的基本形态 2.3两种特殊的二叉树 2.4二叉树的性质 2.5二叉树的存储 2.6二叉树的基本操作 2.7二叉树的层序遍历 3.二叉树完整代码 1. 树型结构 1.1概念 树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合. 把它叫做树是因为它看 起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 . 1.2 概念(重要) a.节点的度:该节点子树的个数:如

  • Java之map的常见用法讲解与五种循环遍历实例代码理解

    目录 一.概述: 二.Map集合的功能介绍 三.map官方总结 四.实例 五.循环遍历的五种方法 一.概述: 将键映射到值的对象 一个映射不能包含重复的键 每个键最多只能映射到一个值 Map接口和Collection接口的不同 Map是双列的,Collection是单列的 Map的键唯一,Collection的子体系Set是唯一的 Map集合的数据结构针对键有效,跟值无关;Collection集合的数据结构是针对元素有效 二.Map集合的功能介绍 a:添加功能 V put(K key,V val

  • java把excel内容上传到mysql实例代码

    mysql 表列名 num1,num2,num3,num4,num5,num6 表名Excle 上传的方法 package com.web.connection; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import org.apache.commons.logging.Log; import org.apache.commons.loggi

  • Java编程实现二项分布的采样或抽样实例代码

    本文研究的主要是Java编程实现二项分布的采样或抽样,下面是具体实现代码. 如下程序为n=100,p=0.9的二项分布采样,共采样10000次 package function; import org.apache.commons.math3.distribution.BetaDistribution; import org.apache.commons.math3.distribution.BinomialDistribution; import org.apache.commons.math

  • Java后缀数组之求sa数组的实例代码

    后缀数组的一些基本概念请自行百度,简单来说后缀数组就是一个字符串所有后缀大小排序后的一个集合,然后我们根据后缀数组的一些性质就可以实现各种需求. public class MySuffixArrayTest { public char[] suffix;//原始字符串 public int n;//字符串长度 public int[] rank;// Suffix[i]在所有后缀中的排名 public int[] sa;// 满足Suffix[SA[1]] < Suffix[SA[2]] --

  • Java发送带html标签内容的邮件实例代码

    如下所示: package test; import javax.mail.internet.InternetAddress; import javax.mail.internet.MimeMessage; import javax.mail.internet.MimeUtility; import javax.mail.Session; import javax.mail.MessagingException; import javax.mail.Transport; public class

  • java使用RandomAccessFile类基于指针读写文件实例代码

    java API中提供了一个基于指针操作实现对文件随机访问操作的类,该类就是RandomAccessFile类,该类不同于其他很多基于流方式读写文件的类.它直接继承自Object. public class RandomAccessFile extends Objectimplements DataOutput, DataInput, Closeable{...} 1.使用该类时可以指定对要操作文件的读写模式. 第一种模式是只读模式,第二种模式是读写模式.在创建该类实例时指定. @Test pu

随机推荐