import java.io.IOException;
import java.util.Stack;
public class BinaryTree {
private char root;
private BinaryTree left;
private BinaryTree right;
private int height;
/*
* Internal a binaryTree by one element
*
* @param element the required
*/
BinaryTree(char element) {
this(element, null, null);
}
/*
* Internal a binaryTree by three element
*
* @param element the root element
*
* @param lt the left subtree
*
* @param rt the right subtree
*/
BinaryTree(char element, BinaryTree lt, BinaryTree rt) {
root = element;
left = lt;
right = rt;
}
/*
* Internal the method to insert into a binaryTree
*
* @param element the insert element
*
* @param bt the tree needed to insert
*/
private BinaryTree insert(char element, BinaryTree bt) {
if (bt == null)
return new BinaryTree(element);
int compareResult = element - bt.root;
if (compareResult > 0) {
bt.right = insert(element, bt.right);
}
if (compareResult < 0) {
bt.left = insert(element, bt.left);
} else
;
bt.height = Math.max(height(bt.left), height(bt.right)) + 1;
return bt;
}
/*
* Return the height of node t, or -1, if null.
*/
private int height(BinaryTree t) {
return t == null ? -1 : t.height;
}
private void PreTravel(BinaryTree k1)// travel a tree by pre-order
{
if (k1 == null)
return;
else {
System.out.print(k1.root);
PreTravel(k1.left);
PreTravel(k1.right);
}
}
private void MidTravel(BinaryTree k1)// travel a tree by mid-order
{
if (k1 == null)
return;
else {
MidTravel(k1.left);
System.out.print(k1.root);
MidTravel(k1.right);
}
}
private void SufTravel(BinaryTree k1)// travel a tree by suf-order
{
if (k1 == null)
return;
else {
SufTravel(k1.left);
SufTravel(k1.right);
System.out.print(k1.root);
}
}
/*
* Internal method to travel a tree without recursion
*
* @param k1 the tree to be traveled
*/
private void PreSTravel(BinaryTree k1) {
Stack<BinaryTree> s = new Stack<BinaryTree>();
if (k1 == null)
return;
else {
System.out.print(k1.root);
s.push(k1.right);
s.push(k1.left);
}
while (!s.empty()) {
BinaryTree bt = s.pop();
if (bt != null) {
System.out.print(bt.root);
s.push(bt.right);
s.push(bt.left);
}
}
}
/*
* Internal method to travel a tree by cursion in mid
*
* @param k1 the tree to be traveled
*/
private void MidSTravel(BinaryTree k1) {
Stack<BinaryTree> s = new Stack<BinaryTree>();
BinaryTree bt = k1;
while (bt != null || !s.empty()) {
while (bt != null) {//先把左子树都压入栈
s.push(bt);
bt = bt.left;
}
if (!s.empty()) {
bt = s.pop();//弹出栈顶
System.out.print(bt.root);
bt = bt.right;
}
}
}
/*
* Internal method to travel a tree without crusion in suf
*
* @param k1 the tree to be traveled
*/
private void SufSTravel(BinaryTree k1) {//后序遍历算法，先遍历当前节点的左孩子，右孩子，最后访问当前节点
Stack<BinaryTree> s = new Stack<BinaryTree>();
BinaryTree cur;
BinaryTree pre = null;
s.push(k1);
while (!s.empty()) {
cur = s.peek();
if ((cur.left == null && cur.right == null) //当前节点为叶子节点或者孩子节点都已经被访问过了
|| (pre != null && (pre == cur.left || pre == cur.right))) {
System.out.print(cur.root); //访问当前节点
s.pop();
pre = cur; //用来判断访问和下一次访问是否相同
} else {//如果不是，则将左孩子压入栈，去看左孩子是否有孩子或者是否遍历过
if (cur.right != null)
s.push(cur.right);
if (cur.left != null)
s.push(cur.left);
}
}
}
/*
* Internal the method to describe a tree
*
* @param bt the tree needed to be describe
*/
private void display(BinaryTree bt) {
if (bt != null) {
System.out.print(bt.root);
if (bt.left != null) {
System.out.print("(");
display(bt.left);
}
if (bt.right != null) {
System.out.print(",");
display(bt.right);
System.out.print(")");
}
}
}
public static void main(String[] args) {
String test = "749358";
// TODO Auto-generated method stub
char ch = 0;
try {
ch = (char) System.in.read();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
BinaryTree bt = new BinaryTree(ch);
try {
ch = (char) System.in.read();
while (ch != ‘#‘) {
bt.insert(ch, bt);
ch = (char) System.in.read();
}
} catch (Exception e) {
e.printStackTrace();
}
System.out.println(bt.height);
System.out.print("树的结构为: ");
bt.display(bt);
System.out.println();
System.out.print("前序遍历<递归>: ");
bt.PreTravel(bt);
System.out.println();
System.out.print("前序遍历<栈>: ");
bt.PreSTravel(bt);
System.out.println();
System.out.print("中序遍历<递归>: ");
bt.MidTravel(bt);
System.out.println();
System.out.print("中序遍历<栈>: ");
bt.MidSTravel(bt);
System.out.println();
System.out.print("后序遍历<递归>: ");
bt.SufTravel(bt);
System.out.println();
System.out.print("后序遍历<栈>: ");
bt.SufSTravel(bt);
}
}
原文：http://my.oschina.net/Sheamus/blog/378520