Java实现二叉树的遍历

    Java实现二叉树的遍历

public class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;

// 前序遍历
public static void preOrder(BinaryTreeNode tree) {
if (tree == null)
return;
System.out.print(tree.value + " ");
preOrder(tree.left);
preOrder(tree.right);
}

/**
 * 二叉树前序遍历的循环实现方式
 * 
 * @param tree
 */
public static void preOrderLoop(BinaryTreeNode tree) {
if (tree == null)
return;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;

while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
System.out.print(node.value + " ");
node = node.left;
} else {
BinaryTreeNode item = stack.pop();
node = item.right;
}
}
}

// 中序遍历
public static void inOrder(BinaryTreeNode tree) {
if (tree == null)
return;
inOrder(tree.left);
System.out.print(tree.value + " ");
inOrder(tree.right);
}

/**
 * 二叉树中序遍历的循环实现
 * 
 * @param tree
 */
public static void inOrderLoop(BinaryTreeNode tree) {
if (tree == null)
return;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;

while (node != null || !stack.empty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
BinaryTreeNode item = stack.pop();
System.out.print(item.value + " ");
node = item.right;
}
}
}

// 后序遍历
public static void postOrder(BinaryTreeNode tree) {
if (tree == null)
return;
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.value + " ");
}

/**
 * 二叉树后序遍历的循环实现
 * 
 * @param tree
 */
public static void postOrderLoop(BinaryTreeNode tree) {
if (tree == null)
return;
HashSet<BinaryTreeNode> visited = new HashSet<BinaryTreeNode>();
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;

while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
BinaryTreeNode item = stack.peek();
if (item.right != null && !visited.contains(item.right))
node = item.right;
else {
System.out.print(item.value + " ");
visited.add(item);
stack.pop();
}
}
}
}

public static void main(String[] args) {
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();

list1.add(1);
list1.add(2);
list1.add(4);
list1.add(7);
list1.add(3);
list1.add(5);
list1.add(6);
list1.add(8);

list2.add(4);
list2.add(7);
list2.add(2);
list2.add(1);
list2.add(5);
list2.add(3);
list2.add(8);
list2.add(6);

BinaryTreeNode tree = BinaryTreeNode.Construct(list1, list2);
BinaryTreeNode.preOrderLoop(tree);
System.out.println();
BinaryTreeNode.inOrderLoop(tree);
System.out.println();
BinaryTreeNode.postOrderLoop(tree);
}

}

本文出自 “许大树” 博客，请务必保留此出处http://abelxu.blog.51cto.com/9909959/1968112