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;
}
相关文档:
1、 串操作:使用字符串存贮一个英文句子“Java is an object oriented programming
language”。显示该句子,并算出每个单词的字母数和平均字母数,并按单词升序排列输出(不用数组,只用串操作)
public class homework21 {
public static void main(String[] args) {
&nb ......
为寻求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 ......
BigDecimal类
双精度浮点型变量double可以处理16位有效数。在实际应用中,需要对更大或者更小的数进行运算和处理。Java在java.math包中提供的API类BigDecimal,用来对超过16位有效位的数进行精确的运算。表5.7中列出了BigDecimal类的主要构造器和方法。
表5.7 BigDecimal类的主要构造器和方法
构造器描述
BigDecimal(in ......
熟悉C++的人对于两个字符串比较的代码一定很了解:
(string1==string2)
但在java中,这个代码即使在两个字符串完全相同的情况下也会返回false
Java中必须使用string1.equals(string2)来进行判断
补充
如果:
string s1=new String("Hello");
string s2=new String("Hello");
则(s1==s2)=false
如果 ......
1.如何学习程序设计?
JAVA是一种平台,也是一种程序设计语言,如何学好程序设计不仅仅适用于JAVA,对C++等其他程序设计语言也一样管用。有编程高手认为,JAVA也好C也好没什么分别,拿来就用。为什么他们能达到如此境界?我想是因为编程语言之间有共通之处,领会了编程的精髓,自然能够做到一通百通。如 ......