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 ......
编写一个简单的文本编辑器，要求：具有打开、保存、新建，粘贴、复制等功能；具有一个工具条。编写一个类似 Windows 记事本的简单程序，该程序能够创建新文件、读取已经存在的文件、查看和修改文本以及保存为文本文件。
暂时还不会做，努力中。。。。。。。。 ......
这几天一直在研究Flex中RemoteObject与java的交互问题，可一直不成功，今天终于成功了，但是还有一些疑惑，应该继续努力。
下面是我的经过和碰到的错误：
（1）下载和安装lcds.
在安装目录下会有如下文件，其中lcds.war可以作为我们开发Flex与java交互的模版，把这个文件考到你tomcat的webapps下（当然这种情况是� ......
1．如何学习程序设计？
JAVA是一种平台，也是一种程序设计语言，如何学好程序设计不仅仅适用于JAVA，对C++等其他程序设计语言也一样管用。有编程高手认为，JAVA也好C也好没什么分别，拿来就用。为什么他们能达到如此境界？我想是因为编程语言之间有共通之处，领会了编程的精髓，自然能够做到一通百通。如 ......
一、JAVA。要想成为JAVA（高级）工程师肯定要学习JAVA。一般的程序员或许只需知道一些JAVA的语法结构就可以应付了。但要成为JAVA（高级）工程师，您要对JAVA做比较深入的研究。您应该多研究一下JDBC、IO包、Util包、Text包、JMS、EJB、RMI、线程。如果可能，希望您对JAVA的所有包都浏览一下，知道大概的API，这样您就发现其 ......
