二叉树深度遍历可采用递归与非递归模式，非递归模式多使用栈来实现，二叉树层次遍历则多使用队列来辅助实现。具体实现如下：
package binarytree;
import java.util.LinkedList;
import java.util.Queue;
/**
*
* @ClassName: BinaryTree
* @Description:二叉树遍历总结
* @date 2017-6-16上午9:36:31
*
*/
publicclass BinaryTree {
/**
*
*@ClassName: Node
*@Description:构建结点
*@date 2017-6-16上午9:38:20
*
*@param<E>
*/
publicstatic class Node<Eextends Comparable<E>> {
E value;
Node<E> left;
Node<E> right;
Node(E value) {
this.value = value;
left = null;
right = null;
}
}
/**
*
*@ClassName: BinarySortTree
*@Description:二叉查找树遍历
*@date 2017-6-16上午9:39:07
*
*@param<E>
*/
publicstatic class BinarySortTree<Eextends Comparable<E>> {
private Node<E>root;
BinarySortTree() {
root = null;
}
publicvoid insertNode(E value) {
if (root ==null) {
root = new Node<E>(value);
return;
}
Node<E>currentNode =root;
while (true) {
if (value.compareTo(currentNode.value) > 0) {
if (currentNode.right ==null) {
currentNode.right =new Node<E>(value);
break;
}
currentNode= currentNode.right;
} else {
if (currentNode.left ==null) {
currentNode.left =new Node<E>(value);
break;
}
currentNode= currentNode.left;
}
}
}
public Node<E> getRoot() {
returnroot;
}
/**
*
*@Title: preOrderTraverse
*@Description:先序递归遍历
*@param node
*@return void
*@throws
*/
publicvoid preOrderTraverse(Node<E>node) {
System.out.print(node.value +" ");
if (node.left !=null)
preOrderTraverse(node.left);
if (node.right !=null)
preOrderTraverse(node.right);
}
/**
*
*@Title: inOrderTraverse
*@Description:中序递归遍历
*@param node
*@return void
*@throws
*/
publicvoid inOrderTraverse(Node<E> node){
if (node.left !=null)
inOrderTraverse(node.left);
System.out.print(node.value +" ");
if (node.right !=null)
inOrderTraverse(node.right);
}
/**
*
*@Title: postOrderTraverse
*@Description:后续递归遍历
*@param node
*@return void
*@throws
*/
publicvoid postOrderTraverse(Node<E>node) {
if (node.left !=null)
postOrderTraverse(node.left);
if (node.right !=null)
postOrderTraverse(node.right);
System.out.print(node.value +" ");
}
/**
*
*@Title: preOrderTraverseNoRecursion
*@Description:先序非递归遍历，使用栈
*@param root
*@return void
*@throws
*/
publicvoidpreOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>>stack =new LinkedList<Node<E>>();
Node<E>currentNode =null;
stack.push(root);
while (!stack.isEmpty()) {
currentNode =stack.pop();
System.out.print(currentNode.value +" ");
if (currentNode.right !=null)
stack.push(currentNode.right);
if (currentNode.left !=null)
stack.push(currentNode.left);
}
}
/**
*
*@Title: inOrderTraverseNoRecursion
*@Description:中序非递归遍历,使用栈
*@param root
*@return void
*@throws
*/
publicvoidinOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>>stack =new LinkedList<Node<E>>();
Node<E>currentNode = root;
while (currentNode !=null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode !=null) {
stack.push(currentNode);
currentNode= currentNode.left;
}
currentNode =stack.pop();
System.out.print(currentNode.value +" ");
currentNode =currentNode.right;
}
}
/**
*
*@Title: postOrderTraverseNoRecursion
*@Description:后序非递归遍历，使用栈
*@param root
*@return void
*@throws
*/
publicvoidpostOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>>stack =new LinkedList<Node<E>>();
Node<E>currentNode = root;
Node<E>rightNode = null;
while (currentNode !=null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode !=null) {
stack.push(currentNode);
currentNode= currentNode.left;
}
currentNode =stack.pop();//当前结点没有右结点或上一个结点（已经输出的结点）是当前结点的右结点，则输出当前结点
while (currentNode.right ==null
||currentNode.right == rightNode) {
System.out.print(currentNode.value +" ");
rightNode= currentNode;
if (stack.isEmpty()) {
return; // root以输出，则遍历结束
}
currentNode= stack.pop();
}
stack.push(currentNode);//还有右结点没有遍历
currentNode =currentNode.right;
}
}
/**
*
*@Title: breadthFirstTraverse
*@Description:广度优先遍历即层次遍历，使用队列
*@param root
*@return void
*@throws
*/
publicvoid breadthFirstTraverse(Node<E>root) {
Queue<Node<E>>queue =new LinkedList<Node<E>>();
Node<E>currentNode =null;
queue.offer(root);
while (!queue.isEmpty()) {
currentNode =queue.poll();
System.out.print(currentNode.value +" ");
if (currentNode.left !=null)
queue.offer(currentNode.left);
if (currentNode.right !=null)
queue.offer(currentNode.right);
}
}
}
/**
*
* @Title: main
* @Description:二叉树遍历测试用例
* @param args
* @return void
* @throws
*/
publicstatic void main(String[] args) {
BinarySortTree<Integer>tree =new BinarySortTree<Integer>();
tree.insertNode(35);
tree.insertNode(20);
tree.insertNode(15);
tree.insertNode(16);
tree.insertNode(29);
tree.insertNode(28);
tree.insertNode(30);
tree.insertNode(40);
tree.insertNode(50);
tree.insertNode(45);
tree.insertNode(55);
System.out.print("先序遍历（递归）：");
tree.preOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("中序遍历（递归）：");
tree.inOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("后序遍历（递归）：");
tree.postOrderTraverse(tree.getRoot());
System.out.println();
System.out.print("先序遍历（非递归）：");
tree.preOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("中序遍历（非递归）：");
tree.inOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("后序遍历（非递归）：");
tree.postOrderTraverseNoRecursion(tree.getRoot());
System.out.println();
System.out.print("广度优先遍历：");
tree.breadthFirstTraverse(tree.getRoot());
}
}