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;
}
相关文档：
首先，强烈推荐你先参考Sun官方的Java代码/编程规范：
http://java.sun.com/docs/codeconv/html/CodeConvTOC.doc.html
你可以打破以上的任一规则，不过一定要有个好理由，并且记录下来。
永远，永远，永远不要在没有记录堆栈跟踪信息（stack trace）或是重新抛出异常的情况下捕获异常，俗称“吃掉异常&rd ......
JAVA
学习笔记（一）：
JAVA
体系及其编程的过程
哎，毕业了也一段时间了，只知道天天抄代码，
JAVA
的基础知识基本是忘掉了，加上以前一直没有系统地学习过，感觉快要废了。还是好好静下心来学学基础吧。不能天天考抄代码过日子啊。。。。（下文大多来自课本以及一些技术视频上的内容，基本理解了一些了，� ......
熟悉C++的人对于两个字符串比较的代码一定很了解：
(string1==string2)
但在java中，这个代码即使在两个字符串完全相同的情况下也会返回false
Java中必须使用string1.equals(string2)来进行判断
补充
如果：
string s1=new String("Hello");
string s2=new String("Hello");
则(s1==s2)=false
如果 ......
最简单的服务器接受单用户请求的socket编程模型，代码写得不好，只是用来阐明意思
client side
import java.net.*;
import java.util.*;
import java.io.*;
public class Client {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
tr ......
1．如何学习程序设计？
JAVA是一种平台，也是一种程序设计语言，如何学好程序设计不仅仅适用于JAVA，对C++等其他程序设计语言也一样管用。有编程高手认为，JAVA也好C也好没什么分别，拿来就用。为什么他们能达到如此境界？我想是因为编程语言之间有共通之处，领会了编程的精髓，自然能够做到一通百通。如 ......
