Skip to content

Instantly share code, notes, and snippets.

@shaobin0604

shaobin0604/遍历二叉树.java

Created March 1, 2010 08:13
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shaobin0604/318191 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shaobin0604/318191 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
遍历二叉树.java
import java.util.*;
class Node {
Node left;
Node right;
int key;
public Node(int key) {
this.key = key;
}
}
public class BTree {
Node root;
/**
* the constructor
**/
public BTree() {
this.root = null;
}
public BTree(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException();
}
root = new Node(array[0]);
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
int i = 1;
while(i < array.length) {
if (!queue.isEmpty()) {
Node p = queue.poll();
p.left = new Node(array[i]);
queue.offer(p.left);
i++;
if (i < array.length) {
p.right = new Node(array[i]);
queue.offer(p.right);
i++;
}
}
}
}
/********************************************************************
* 广度优先遍历
*
********************************************************************/
public void breadthFirstTraverse() {
Node p = root;
if (p != null) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(p);
while (!queue.isEmpty()) {
p = queue.poll();
System.out.println(p.key);
if (p.left != null) {
queue.offer(p.left);
}
if (p.right != null) {
queue.offer(p.right);
}
}
}
}
/********************************************************************
* 深度优先遍历
*
********************************************************************/
/**
* iterative traverse
*
**/
public void iterativePreorder() {
Node p = root;
Stack<Node> travStack = new Stack<Node>();
if (p != null) {
travStack.push(p);
while (!travStack.isEmpty()) {
p = travStack.pop();
System.out.println(p.key);
if (p.right != null)
travStack.push(p.right);
if (p.left != null) // left child pushed after right
travStack.push(p.left); // to be on the top of the stack;
}
}
}
public void iterativeInorder() {
Node p = root;
Stack<Node> travStack = new Stack<Node>();
while (p != null) {
while(p != null) { // stack the right child (if any)
if (p.right != null) // and the node itself when going
travStack.push(p.right); // to the left;
travStack.push(p);
p = p.left;
}
p = travStack.pop(); // pop a node with no left child
while (!travStack.isEmpty() && p.right == null) { // visit it and all
System.out.println(p.key); // nodes with no right child;
p = travStack.pop();
}
System.out.println(p.key); // visit also the first node with
if (!travStack.isEmpty()) // a right child (if any);
p = travStack.pop();
else p = null;
}
}
public void iterativeInorderPlus() {
Node p = root;
Stack<Node> travStack = new Stack<Node>();
travStack.push(p);
while (!travStack.empty()) {
while ((p = travStack.peek()) != null) {//向左走到尽头
travStack.push(p.left);
}
travStack.pop(); //pop the null element
if (!travStack.empty()) {
p = travStack.pop(); //访问结点，向右一步
System.out.println(p.key);
travStack.push(p.right);
}
}
}
public void iterativeInorderPlusPlus() {
Node p = root;
Stack<Node> travStack = new Stack<Node>();
while (p != null || !travStack.empty()) {
if (p != null) { //根指针进栈，遍历左子树
travStack.push(p);
p = p.left;
} else { //根指针退栈，访问根结点，遍历右子树
p = travStack.pop();
System.out.println(p.key);
p = p.right;
}
}
}
public void iterativePostorder() {
Node p = root;
Stack<Node> travStack = new Stack<Node>(), output = new Stack<Node>();
if (p != null) { // left-to-right postorder = right-to-left preorder
travStack.push(p);
while (!travStack.isEmpty()) {
p = travStack.pop();
output.push(p);
if (p.left != null)
travStack.push(p.left);
if (p.right != null)
travStack.push(p.right);
}
while (!output.isEmpty()) {
p = output.pop();
System.out.println(p.key);
}
}
}
public void iterativePostorderPlus() {
Node p = root;
Node q = null;
Stack<Node> travStack = new Stack<Node>();
while (p != null || !travStack.empty()) {
if (p != null) { //根指针进栈，遍历左子树
travStack.push(p);
p = p.left;
} else {
p = travStack.peek();
//如果根结点没有右子树，
//或是右子树已经被访问，
//则访问根结点；否则遍历右子树
if (p.right == null || p.right == q) {
p = travStack.pop();
System.out.println(p.key);
q = p;
p = null;
} else {
p = p.right;
}
}
}
}
/**
* recursive traverse
*
*
**/
public void preOrderTraverse(Node p) {
if (p != null) {
System.out.println(p.key);
if (p.left != null) {
preOrderTraverse(p.left);
}
if (p.right != null) {
preOrderTraverse(p.right);
}
}
}
public void inOrderTraverse(Node p) {
if (p != null) {
if (p.left != null) {
inOrderTraverse(p.left);
}
System.out.println(p.key);
if (p.right != null) {
inOrderTraverse(p.right);
}
}
}
public void postOrderTraverse(Node p) {
if (p != null) {
if (p.left != null) {
postOrderTraverse(p.left);
}
if (p.right != null) {
postOrderTraverse(p.right);
}
System.out.println(p.key);
}
}
/**
* 通过转换树遍历
*
* 不使用任何堆栈或线索化遍历一个树也是可能的。
* 有很多这样的算法，它们都是在遍历期间对树进行了暂时的改变，
* 这些改变包含了为一些引用域赋了新的值。但是，树可能会失去
* 它的树结构，这在完成遍历后需要恢复
**/
/**
* Joseph M.Morris 先序遍历
**/
public void morrisPreorder() {
Node p = root, tmp = null;;
while (p != null) {
if (p.left == null) {
System.out.println(p.key);
p = p.right;
}
else {
tmp = p.left;
while (tmp.right != null && tmp.right != p) // go to the rightmost node of the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if (tmp.right == null) { // if 'true' rightmost node was
System.out.println(p.key);
tmp.right = p; // reached, make it a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been
// System.out.println(p.key); // found; visit node p and then cut
tmp.right = null; // the right pointer of the current
p = p.right; // parent, whereby it ceases to be
} // a parent;
}
}
//System.out.printf("temp.key = %s", tmp.key);
}
/**
* Joseph M.Morris 中序遍历
*
* MorrisInorder()
* while 未结束
* if 节点无左子女
* 访问他；
* 到右边；
* else
* 使该节点成为其左子女的最右节点的右子女
* 到这个节点的左子女
**/
public void morrisInorder() {
Node p = root, tmp = null;;
while (p != null) {
if (p.left == null) {
System.out.println(p.key);
p = p.right;
}
else {
tmp = p.left;
while (tmp.right != null && tmp.right != p) // go to the rightmost node of the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if (tmp.right == null) { // if 'true' rightmost node was
tmp.right = p; // reached, make it a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been
System.out.println(p.key); // found; visit node p and then cut
tmp.right = null; // the right pointer of the current
p = p.right; // parent, whereby it ceases to be
} // a parent;
}
}
//System.out.printf("temp.key = %s", tmp.key);
}
/************************************************************
* 测试方法
*
************************************************************/
public static void testBreadthFirstTraverse() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.breadthFirstTraverse();
}
public static void testPreOrderTraverse() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.preOrderTraverse(tree.root);
}
public static void testPreOrderTraverseIterative() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.iterativePreorder();
}
public static void testInOrderTraverse() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.inOrderTraverse(tree.root);
}
public static void testInOrderTraverseIterativePlus() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.iterativeInorderPlus();
}
public static void testPostOrderTraverse() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.postOrderTraverse(tree.root);
}
public static void testPostOrderTraverseIterativePlus() {
BTree tree = new BTree(new int[] {1, 2, 3, 4, 5, 6, 7, });
tree.iterativePostorderPlus();
}
public static void testMorrisPreorder() {
BTree tree = new BTree(new int[] {10, 5, 20, 3, 7, });
tree.morrisPreorder();
}
public static void testMorrisInorder() {
BTree tree = new BTree(new int[] {10, 5, 20, 3, 7, });
tree.morrisInorder();
}
public static void main(String[] args) {
testBreadthFirstTraverse();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment