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++;
}
}
}
}
/********************************************************************
* 廣度優(yōu)先遍歷
*
********************************************************************/
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);
}
}
}
}
/********************************************************************
* 深度優(yōu)先遍歷
*
********************************************************************/
/**
* 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(); //訪問結(jié)點(diǎn)，向右一步
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) { //根指針進(jìn)棧，遍歷左子樹
travStack.push(p);
p = p.left;
} else { //根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹
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) { //根指針進(jìn)棧，遍歷左子樹
travStack.push(p);
p = p.left;
} else {
p = travStack.peek();
//如果根結(jié)點(diǎn)沒有右子樹，
//或是右子樹已經(jīng)被訪問，
//則訪問根結(jié)點(diǎn)；否則遍歷右子樹
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);
}
}
/**
* 通過轉(zhuǎn)換樹遍歷
*
* 不使用任何堆?；蚓€索化遍歷一個(gè)樹也是可能的。
* 有很多這樣的算法，它們都是在遍歷期間對樹進(jìn)行了暫時(shí)的改變，
* 這些改變包含了為一些引用域賦了新的值。但是，樹可能會(huì)失去
* 它的樹結(jié)構(gòu)，這在完成遍歷后需要恢復(fù)
**/
/**
* 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 未結(jié)束
* if 節(jié)點(diǎn)無左子女
* 訪問他；
* 到右邊；
* else
* 使該節(jié)點(diǎn)成為其左子女的最右節(jié)點(diǎn)的右子女
* 到這個(gè)節(jié)點(diǎn)的左子女
**/
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();
}
}
