java创建二叉树并递归遍历二叉树前面已有讲解：http://www.cnblogs.com/lixiaolun/p/4658659.html。
在此基础上添加了非递归中序遍历二叉树：
二叉树类的代码：
package binarytree;
import linkedstack.LinkStack;
import linkqueue.LinkQueue;
public class BinaryTree {
class Node
{
public Object data;
public Node lchild;
public Node rchild;
public Node(Object data)
{
this.data = data;
this.lchild = null;
this.rchild = null;
}
}
//根节点
private Node root = null;
private Node node = null;
/**
* 创建树
*
* 以完全二叉树的格式来创建（子树不存在的用0填充），
* 对完全二叉树中每一个节点从0开始进行编号，
* 那么第i个节点的左孩子的编号为2*i+1，右孩子为2*i+2。
*
* */
void createTree(String strtree)
{
LinkQueue lQueue = new LinkQueue();
lQueue.initQueue();
/**
* 完全二叉树中第i层的结点的个数最多为第1到i-1层上所有节点的个数和
* 所以父节点的个数最多为N-1个，N表示节点个数
* */
for(int parentIndex =0; parentIndex<strtree.split(" ").length/2;parentIndex++)
{
if(root == null)
{
root= new Node(strtree.split(" ")[parentIndex]);
//左孩子
root.lchild = new Node(strtree.split(" ")[parentIndex*2+1]);
lQueue.enQueue(root.lchild);
//右孩子
root.rchild = new Node(strtree.split(" ")[parentIndex*2+2]);
lQueue.enQueue(root.rchild);
}else
{
if(!lQueue.isEmpty() && parentIndex*2+1<strtree.split(" ").length)//队列不空
{
node = (Node) lQueue.deQueue();
if(parentIndex*2+1<strtree.split(" ").length)
{
//左孩子
node.lchild = new Node(strtree.split(" ")[parentIndex*2+1]);
lQueue.enQueue(node.lchild);
}
if(parentIndex*2+2<strtree.split(" ").length)
{
//右孩子
node.rchild = new Node(strtree.split(" ")[parentIndex*2+2]);
lQueue.enQueue(node.rchild);
}
}else
{
return;
}
}
}
}
/**
* 先序遍历二叉树
* */
void preOrderTraverse(Node node)
{
if(node == null)
{
return;
}
visit(node);
preOrderTraverse(node.lchild);
preOrderTraverse(node.rchild);
}
/**
* 中序遍历二叉树
* */
void inOrderTraverse(Node node)
{
if(node == null)
{
return;
}
inOrderTraverse(node.lchild);
visit(node);
inOrderTraverse(node.rchild);
}
/**
* 非递归中序遍历二叉树
* */
void inOrderTraverse2(Node node)
{
if(node == null)
{
return;
}
LinkStack lStack = new LinkStack();
lStack.initStack();//初始化栈
Node p =node;
while(p!=null || !lStack.isEmpty())
{
if(p!=null)//遍历左子树，向左走到尽头，并将走过的节点入栈
{
lStack.push(p);
p=p.lchild;
}else//访问节点，向右走一步
{
p=(Node) lStack.pop();
visit(p);
p=p.rchild;
}
}
}
/**
* 后序遍历二叉树
* */
void postOrderTraverse(Node node)
{
if(node == null)
{
return;
}
postOrderTraverse(node.lchild);
postOrderTraverse(node.rchild);
visit(node);
}
/**
* 打印二叉树
* */
public void print()
{
System.out.print("先序遍历：");
preOrderTraverse(root);
System.out.print("\n中序遍历：");
inOrderTraverse(root);
System.out.print("\n非递归中序遍历：");
inOrderTraverse2(root);
System.out.print("\n后序遍历：");
postOrderTraverse(root);
}
/**
* 访问节点
* */
private void visit(Node node)
{
if(!node.data.equals("0"))
{
System.out.print(node.data);
}
}
}
测试类代码：
package binarytree;
public class BinaryTreeMain {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
String strtree="- + / a * e f 0 0 b - 0 0 0 0 0 0 0 0 0 0 c d";//0表示没有值的位置
binaryTree.createTree(strtree);
binaryTree.print();
}
}