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.String是最基本的数据类型么？
答：不是。基本的数据类型包括：byte,int,char,long,float,double,boolean和short.
java.lang.String类是final类型的，因此不可以继承这个类，不能修改这个类。
2.静态变量和实例变量的区别？
答：static i = 10 ;//常量
&nb ......
Set和数学中的集合是同一个概念，就是没有重复元素的集合。
这篇文章主要论述了Set是如何实现"没有重复元素"（no duplicate elements）的，以及阐述了什么是“重复”（duplicate），是相同的地址空间？是equals的返回值为true？是compareTo的返回值为0 ？还是有相同的hashCode？本文还给出了在什么情况下使用什� ......
一、JAVA。要想成为JAVA（高级）工程师肯定要学习JAVA。一般的程序员或许只需知道一些JAVA的语法结构就可以应付了。但要成为JAVA（高级）工程师，您要对JAVA做比较深入的研究。您应该多研究一下JDBC、IO包、Util包、Text包、JMS、EJB、RMI、线程。如果可能，希望您对JAVA的所有包都浏览一下，知道大概的API，这样您就发现其 ......
