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;
}
相关文档：
JNI是Java Native Interface的缩写，通过使用native方法，Java可以调用本地C/C++子程序。声明一个本地子程序的方法是：在方法名前添加native修饰，如
public native void myfun();
调用该子程序的方法为：
static{
System.loadLibrary("myfun");
}
在Windows上，上面的myfun即指包含用C/C++写的my ......
1下面哪个是正确的类声明？假设每一段文本都做为一个名称为Fred.java的文件的全部内容？ a
a).
public class Fred{
public int x = 0;
public Fred (int x){
this.x=x;
}
}
b).
public class fred{
public int x = 0;
public Fred (int x){
this.x=x;
}
}
c).
public class ......
为寻求java代码的性能优化，从网上搜到利用final关键字进行编译时inline优化的方法，但是真的有效吗？实际测试中发现未必，甚至性能影响巨大，最终放弃了使用final优化的想法。
测试环境：Windows XP SP2，JDK 1.6.0_15-b03，Eclipse 3.5 SR1。
package test;
public class Test {
public static void main(St ......
final类：为防止他人从你的类上派生新类，此类是不可扩展的。
动态调用比静态调用花费的时间要长。
抽象类：规定一个或多个抽象方法的类本身必须定义为abstract。
例： public abstract string getDescripition
Java中的每一个类都是从Object类扩展而来的。
object类中的equal和toString方� ......
BigDecimal类
双精度浮点型变量double可以处理16位有效数。在实际应用中，需要对更大或者更小的数进行运算和处理。Java在java.math包中提供的API类BigDecimal，用来对超过16位有效位的数进行精确的运算。表5.7中列出了BigDecimal类的主要构造器和方法。
表5.7 BigDecimal类的主要构造器和方法
构造器描述
BigDecimal(in ......
