Java递归、非递归实现二叉树遍历
最近找工作做笔试题发现很重要,就自己写了一点,和大家分享
import java.util.Stack;
import java.util.HashMap;
public class BinTree {
private char date;
private BinTree lchild;
private BinTree rchild;
public BinTree(char c) {
date = c;
}
// 先序遍历递归
public static void preOrder(BinTree t) {
if (t == null) {
return;
}
System.out.print(t.date);
preOrder(t.lchild);
preOrder(t.rchild);
}
// 中序遍历递归
public static void InOrder(BinTree t) {
if (t == null) {
return;
}
InOrder(t.lchild);
System.out.print(t.date);
InOrder(t.rchild);
}
// 后序遍历递归
public static void PostOrder(BinTree t) {
if (t == null) {
return;
}
PostOrder(t.lchild);
PostOrder(t.rchild);
System.out.print(t.date);
}
// 先序遍历非递归
public static void preOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
while (t != null || !s.empty()) {
while (t != null) {
System.out.print(t.date);
s.push(t);
t = t.lchild;
}
if (!s.empty()) {
t = s.pop();
t = t.rchild;
}
}
}
// 中序遍历非递归
public static void InOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
while (t != null || !s.empty()) {
while (t != null) {
s.push(t);
t = t.lchild;
}
if (!s.empty()) {
t = s.pop();
System.out.print(t.date);
t = t.rchild;
}
}
}
// 后序遍历非递归
public static void PostOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
Stack<Integer> s2 = new Stack<Integer>();
Integer i = new Integer(1);
while (t != null || !s.empty()) {
while (t != null) {
s.push(t);
s2.push(new Integer(0));
t = t.lchild;
}
while (!s.empty() && s2.peek().equals(i)) {
s2.pop();
System.out.print(s.pop().date);
}
if (!s.empty()) {
s2.pop();
s2.push(new Integer(1));
t = s.peek();
t = t.rchild;
}
相关文档:
Java学习从入门到精通
一、 JDK (Java Development Kit)
JDK是整个Java的核心,包括了Java运行环境(Java Runtime Envirnment),一堆Java工具和Java基础的类库(rt.jar)。不论什么Java应用服务器实质都是内置了某个版本的JDK。因此掌握JDK是学好Java的第一步。最主流的J ......
create PROCEDURE pagelist
@tablename nvarchar(50),
@fieldname nvarchar(50)='*',
@pagesize int output,--每页显示记录条数
@currentpage int output,--第几页
@orderid nvarchar(50),--主键排序
@sort int,--排序方式,1表示升序,0表示降序排列
......
package barchartdemo1;
import java.awt.Font;
import java.io.FileOutputStream;
import java.io.IOException;
import org.jfree.chart.ChartFactory;
import org.jfree.chart.ChartUtilities;
import org.jfree.chart.JFreeChart;
import org.jfree.chart.axis.CategoryAxis;
import org.jfree.chart.axis.Numbe ......
1.如何学习程序设计?
JAVA是一种平台,也是一种程序设计语言,如何学好程序设计不仅仅适用于JAVA,对C++等其他程序设计语言也一样管用。有编程高手认为,JAVA也好C也好没什么分别,拿来就用。为什么他们能达到如此境界?我想是因为编程语言之间有共通之处,领会了编程的精髓,自然能够做到一通百通。如 ......
一、Array , Arrays
Java所有“存储及随机访问一连串对象”的做法,array是最有效率的一种。
1、
效率高,但容量固定且无法动态改变。
array还有一个缺点是,无法判断其中实际存有多少元素,length只是告诉我们array的容量。
2、Java中有一个Arrays类,专门用来操作array。
a ......