「java树的后序遍历」树的后序遍历与其对应的二叉树

admin 2023-03-22 15:33:11 587

今天给各位分享java树的后序遍历的知识，其中也会对树的后序遍历与其对应的二叉树进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

1、Java如何理解preOrder()的实现
2、用Java实现一个树形结构，并对其进行遍历
3、Java List遍历方法及其效率对比
4、java构建二叉树算法
5、java Map 怎么遍历
6、java TreeSet 倒序是怎么实现的?

Java如何理解preOrder()的实现

这个不是很难理解哈，就是使用递归来遍历树，LZ请看：

首先，这个preOrder这个方法是用来遍历树的，貌似说了个废话，它需要一个

BinaryNodeE p的参数，这个参数就是树上的一个节点。

首先，假如当前p是A，那么判断p是否为null，也就是是否有这个节点，如果有，那么打印p.data，应该是p的信息。

然后再次调用这个preOrder遍历树的方法preOrder（p.left）；preOrder（p.right），但这此传入的节点已经不是A了，而是p.left和p.right，也就是B和C，然后依然跟上面一样，先判断是否有该节点，如果有就打印节点信息，然后再次调用该方法传入自己的左右孩子节点，一次递归循环，自己的左右孩子为null的时候，当然不会走if语句里面的内容，递归也就自然结束了

希望可以帮到LZ

用Java实现一个树形结构，并对其进行遍历

import java.util.Iterator;

import java.util.Random;

import java.util.TreeSet;

public class Demo{

public static void main(String[] args) throws Exception {

TreeSetInteger ts = new TreeSetInteger();

for(int i = 0; i 10; i++){

ts.add(new Random().nextInt(999));

}

for(IteratorInteger it = ts.iterator(); it.hasNext();){

System.out.println(it.next());

}

//上面是利用TreeSet进行简单的二叉树实现，另有遍历，当然遍历是自然顺序。

//如有需要请自行修改吧。

Java List遍历方法及其效率对比

Java代码

package zbalpha test;

import java util ArrayList;

import java util Iterator;

import java util List;

public class ListTest {

public static void main(String args[]){

ListLong lists = new ArrayListLong();

for(Long i= l;i l;i++){

lists add(i);

}

Long oneOk = oneMethod(lists);

Long oOk = oMethod(lists);

Long threeOk = threeMethod(lists);

Long fourOk = fourMethod(lists);

System out println( One: + oneOk);

System out println( Two: + oOk);

System out println( Three: + threeOk);

System out println( four: + fourOk);

}

public static Long oneMethod(ListLong lists){

Long timeStart = System currentTimeMillis();

for(int i= ;ilists size();i++) {

System out println(lists get(i));

}

Long timeStop = System currentTimeMillis();

return timeStop timeStart ;

}

public static Long oMethod(ListLong lists){

Long timeStart = System currentTimeMillis();

for(Long string : lists) {

System out println(string);

}

Long timeStop = System currentTimeMillis();

return timeStop timeStart ;

}

public static Long threeMethod(ListLong lists){

Long timeStart = System currentTimeMillis();

IteratorLong it = erator();

while (it hasNext())

{

System out println(it next());

}

Long timeStop = System currentTimeMillis();

return timeStop timeStart ;

}

public static Long fourMethod(ListLong lists){

Long timeStart = System currentTimeMillis();

for(IteratorLong i = erator(); i hasNext();) {

System out println(i next());

}

Long timeStop = System currentTimeMillis();

return timeStop timeStart ;

}

容器类可以大大提高编程效率和编程能力在Java 中所有的容器都由SUN公司的Joshua Bloch进行了重新设计丰富了容器类库的功能

Java 容器类类库的用途是保存对象它分为两类

Collection 一组独立的元素通常这些元素都服从某种规则 List必须保持元素特定的顺序而Set不能有重复元素

Map 一组成对的键值对对象即其元素是成对的对象最典型的应用就是数据字典并且还有其它广泛的应用另外 Map可以返回其所有键组成的Set和其所有值组成的Collection 或其键值对组成的Set 并且还可以像数组一样扩展多维Map 只要让Map中键值对的每个值是一个Map即可

迭代器

迭代器是一种设计模式它是一个对象它可以遍历并选择序列中的对象而开发人员不需要了解该序列的底层结构迭代器通常被称为轻量级对象因为创建它的代价小

Java中的Iterator功能比较简单并且只能单向移动

( ) 使用方法iterator()要求容器返回一个Iterator 第一次调用Iterator的next()方法时它返回序列的第一个元素

( ) 使用next()获得序列中的下一个元素

( ) 使用hasNext()检查序列中是否还有元素

( ) 使用remove()将迭代器新返回的元素删除

Iterator是Java迭代器最简单的实现为List设计的ListIterator具有更多的功能它可以从两个方向遍历List 也可以从List中插入和删除元素

List的功能方法

List(interface): 次序是List最重要的特点它确保维护元素特定的顺序 List为Collection添加了许多方法使得能够向List中间插入与移除元素(只推荐 LinkedList使用) 一个List可以生成ListIterator 使用它可以从两个方向遍历List 也可以从List中间插入和删除元素

ArrayList: 由数组实现的List 它允许对元素进行快速随机访问但是向List中间插入与移除元素的速度很慢 ListIterator只应该用来由后向前遍历ArrayList 而不是用来插入和删除元素因为这比LinkedList开销要大很多

LinkedList: 对顺序访问进行了优化向List中间插入与删除得开销不大随机访问则相对较慢(可用ArrayList代替) 它具有方法addFirst() addLast() getFirst() getLast() removeFirst() removeLast() 这些方法(没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈队列和双向队列使用

Set的功能方法

Set(interface): 存入Set的每个元素必须是唯一的因为Set不保存重复元素加入Set的Object必须定义equals()方法以确保对象的唯一性 Set与Collection有完全一样的接口 Set接口不保证维护元素的次序

HashSet: 为快速查找而设计的Set 存入HashSet的对象必须定义hashCode()

TreeSet: 保持次序的Set 底层为树结构使用它可以从Set中提取有序的序列

LinkedHashSet: 具有HashSet的查询速度且内部使用链表维护元素的顺序(插入的次序) 于是在使用迭代器遍历Set时结果会按元素插入的次序显示

lishixinzhi/Article/program/Java/hx/201311/26494

java构建二叉树算法

//******************************************************************************************************//

//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//

//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //数据元数

private BinTree left,right; //指向左,右孩子结点的链

BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点

int front;//层次遍历时队首

int rear;//层次遍历时队尾

public BinTree()

{

}

public BinTree(Object data)

{ //构造有值结点

this.data = data;

left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //构造有值结点

this.data = data;

this.left = left;

this.right = right;

}

public String toString()

{

return data.toString();

}//前序遍历二叉树

public static void preOrder(BinTree parent){

if(parent == null)

return;

System.out.print(parent.data+" ");

preOrder(parent.left);

preOrder(parent.right);

}//中序遍历二叉树

public void inOrder(BinTree parent){

if(parent == null)

return;

inOrder(parent.left);

System.out.print(parent.data+" ");

inOrder(parent.right);

}//后序遍历二叉树

public void postOrder(BinTree parent){

if(parent == null)

return;

postOrder(parent.left);

postOrder(parent.right);

System.out.print(parent.data+" ");

}// 层次遍历二叉树

public void LayerOrder(BinTree parent)

{

elements[0]=parent;

front=0;rear=1;

while(frontrear)

{

try

{

if(elements[front].data!=null)

{

System.out.print(elements[front].data + " ");

if(elements[front].left!=null)

elements[rear++]=elements[front].left;

if(elements[front].right!=null)

elements[rear++]=elements[front].right;

front++;

}

}catch(Exception e){break;}

}

}//返回树的叶节点个数

public int leaves()

{

if(this == null)

return 0;

if(left == nullright == null)

return 1;

return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());

}//结果返回树的高度

public int height()

{

int heightOfTree;

if(this == null)

return -1;

int leftHeight = (left == null ? 0 : left.height());

int rightHeight = (right == null ? 0 : right.height());

heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;

return 1 + heightOfTree;

}

//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层

public int level(Object object)

{

int levelInTree;

if(this == null)

return -1;

if(object == data)

return 1;//规定根节点为第一层

int leftLevel = (left == null?-1:left.level(object));

int rightLevel = (right == null?-1:right.level(object));

if(leftLevel0rightLevel0)

return -1;

levelInTree = leftLevelrightLevel?rightLevel:leftLevel;

return 1+levelInTree;

}

//将树中的每个节点的孩子对换位置

public void reflect()

{

if(this == null)

return;

if(left != null)

left.reflect();

if(right != null)

right.reflect();

BinTree temp = left;

left = right;

right = temp;

}// 将树中的所有节点移走,并输出移走的节点

public void defoliate()

{

String innerNode = "";

if(this == null)

return;

//若本节点是叶节点，则将其移走

if(left==nullright == null)

{

System.out.print(this + " ");

data = null;

return;

}

//移走左子树若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本节点，放在中间表示中跟移走...

innerNode += this + " ";

data = null;

//移走右子树若其存在

if(right!=null){

right.defoliate();

right = null;

}

/**

* @param args

public static void main(String[] args) {

// TODO Auto-generated method stub

BinTree e = new BinTree("E");

BinTree g = new BinTree("G");

BinTree h = new BinTree("H");

BinTree i = new BinTree("I");

BinTree d = new BinTree("D",null,g);

BinTree f = new BinTree("F",h,i);

BinTree b = new BinTree("B",d,e);

BinTree c = new BinTree("C",f,null);

BinTree tree = new BinTree("A",b,c);

System.out.println("前序遍历二叉树结果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍历二叉树结果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍历二叉树结果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("层次遍历二叉树结果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的层次: "+tree.level("F"));

System.out.println("这棵二叉树的高度: "+tree.height());

System.out.println("--------------------------------------");

tree.reflect();

System.out.println("交换每个节点的孩子节点后......");

System.out.println("前序遍历二叉树结果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍历二叉树结果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍历二叉树结果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("层次遍历二叉树结果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的层次: "+tree.level("F"));

System.out.println("这棵二叉树的高度: "+tree.height());

}

java Map 怎么遍历

java Map 遍历一般有四种方式

方式一: 这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。

方式二：在for-each循环中遍历keys或values。

如果只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet。

该方法比entrySet遍历在性能上稍好（快了10%），而且代码更加干净。

方式三：使用Iterator遍历

使用泛型：

不使用泛型：

你也可以在keySet和values上应用同样的方法。

方法四: 通过键找值遍历（效率低）

作为方法一的替代，这个代码看上去更加干净；但实际上它相当慢且无效率。

因为从键取值是耗时的操作（与方法一相比，在不同的Map实现中该方法慢了20%~200%）。如果安装了FindBugs，它会做出检查并警告你关于哪些是低效率的遍历。所以尽量避免使用。

总结:

如果仅需要键(keys)或值(values)使用方法二。

如果所使用的语言版本低于java 5，或是打算在遍历时删除entries，必须使用方法三。

否则使用方法一(键值都要)。

扩展资料：

类似的遍历算法：

二叉树的遍历算法

1、先（根）序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴ 访问根结点；

⑵ 遍历左子树；

⑶ 遍历右子树。

2、中（根）序遍历的递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵访问根结点；

⑶遍历右子树。

3、后（根）序遍历得递归算法定义：

若二叉树非空，则依次执行如下操作：

⑴遍历左子树；

⑵遍历右子树；

⑶访问根结点。

参考资料：百度百科——Java

java TreeSet 倒序是怎么实现的?

TreeSet是一个有序的集合。

第一：构造、增加、遍历、删除和判断是否包含某个元素同HashSet是一致的。、

第二：证明TreeSet是一个有序的集合。

TreeSet hashSet = new TreeSet();

hashSet.add("a"); //向集合中添加一个字符串

hashSet.add("e");

hashSet.add("b");

hashSet.add("d");

hashSet.add("c");

Iterator it = hashSet.iterator();

while(it.hasNext()){

System.out.println(it.next()+",");

}

输出结果是：

注意：（1）从结果中可以看出元素被排序了，但是这个用默认的排序方法。如何自定义排序呢？可以实现Comparator接口来自定义排序。例如：

import java.util.Comparator;

import ws.wph.android.util.StringUtils;

public class MyCmp implements Comparator {

public int compare(Object element1, Object element2) {

int x = element2.toString().compareTo(element1.toString());

return x;

}

然后将该类的对象作为TreeSet构造方法的实参，即TreeSet hashSet = new TreeSet(new

MyCmp());。原理是：向TreeSet增加元素时，自动调用MyCmp类的compare(Object element1, Object

element2)方法，根据方法返回值决定element1和element2的顺序。（此时的输出结果是：e,

a,）

（2）当element1 == element2时返回0，element1 element2 返回正数，element1 element2返回负数。

第三：按照学生成绩排序，当成绩相同时按照学号排序

public int compare(Object element1, Object element2) {

int x=0;

Stuendt s1 = (Stuendt)element1;

Stuendt s2 = (Stuendt)element2;

if(s1.getScore() s2.getScore()){

x=-1;

}else if(s1.getScore() s2.getScore()){

x=1;

}else{

x = s1.getSno().compareTo(s2.getSno());

}

return x;

}

（3）将汉字转换成拼音

public static String getPingYin(String src){

char[] t1 = null;

t1=src.toCharArray();

String[] t2 = new String[t1.length];

HanyuPinyinOutputFormat t3 = new HanyuPinyinOutputFormat();

t3.setCaseType(HanyuPinyinCaseType.LOWERCASE);

t3.setToneType(HanyuPinyinToneType.WITHOUT_TONE);

t3.setVCharType(HanyuPinyinVCharType.WITH_V);

String t4="";

int t0=t1.length;

try {

for (int i=0;it0;i++)

{

//判断是否为汉字字符

if(java.lang.Character.toString(t1[i]).matches("[\\u4E00-\\u9FA5]+"))

{

t2 = PinyinHelper.toHanyuPinyinStringArray(t1[i], t3);

t4+=t2[0];

}

else

t4+=java.lang.Character.toString(t1[i]).toLowerCase();

}

return t4;

}catch (BadHanyuPinyinOutputFormatCombination e1) {

e1.printStackTrace();

}

return t4;

}

但是需要导入一个包

java树的后序遍历的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于树的后序遍历与其对应的二叉树、java树的后序遍历的信息别忘了在本站进行查找喔。

标签：java树的后序遍历