|
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(); } } |
|
|
来自： shaobin0604@1... > 《数据结构》
