构造树如下:其中二叉树节点类
/** 二叉树节点 */ public class BTNode { private char key; private BTNode left, right; public BTNode( char key) { this (key, null , null ); } public BTNode( char key, BTNode left, BTNode right) { this .key = key; this .left = left; this .right = right; } public char getKey() { return key; } public void setKey( char key) { this .key = key; } public BTNode getLeft() { return left; } public void setLeft(BTNode left) { this .left = left; } public BTNode getRight() { return right; } public void setRight(BTNode right) { this .right = right; }}遍历二叉树
/** 二叉树遍历 */ public class BinTree { protected BTNode root; public BinTree(BTNode root) { this .root = root; } public BTNode getRoot() { return root; } /** 构造树 */ public static BTNode init() { BTNode a = new BTNode('A'); BTNode b = new BTNode('B', null , a); BTNode c = new BTNode('C'); BTNode d = new BTNode('D', b, c); BTNode e = new BTNode('E'); BTNode f = new BTNode('F', e, null ); BTNode g = new BTNode('G', null , f); BTNode h = new BTNode('H', d, g); return h; // root } /** 访问节点 */ public static void visit(BTNode p) { System.out.print(p.getKey() + " " ); } /** 递归实现前序遍历 */ protected static void preorder(BTNode p) { if (p != null ) { visit(p); preorder(p.getLeft()); preorder(p.getRight()); } } /** 递归实现中序遍历 */ protected static void inorder(BTNode p) { if (p != null ) { inorder(p.getLeft()); visit(p); inorder(p.getRight()); } } /** 递归实现后序遍历 */ protected static void postorder(BTNode p) { if (p != null ) { postorder(p.getLeft()); postorder(p.getRight()); visit(p); } } /** 非递归实现前序遍历 */ protected static void iterativePreorder(BTNode p) { Stack<BTNode> stack = new Stack<BTNode>(); if (p != null ) { stack.push(p); while (!stack.empty()) { p = stack.pop(); visit(p); if (p.getRight() != null ) stack.push(p.getRight()); if (p.getLeft() != null ) stack.push(p.getLeft()); } } } /** 非递归实现后序遍历 */ protected static void iterativePostorder(BTNode p) { BTNode q = p; Stack<BTNode> stack = new Stack<BTNode>(); while (p != null ) { // 左子树入栈 for (; p.getLeft() != null ; p = p.getLeft()) stack.push(p); // 当前节点无右子或右子已经输出 while (p != null && (p.getRight() == null || p.getRight() == q)) { visit(p); q = p; // 记录上一个已输出节点 if (stack.empty()) return ; p = stack.pop(); } // 处理右子 stack.push(p); p = p.getRight(); } } /** 非递归实现中序遍历 */ protected static void iterativeInorder(BTNode p) { Stack<BTNode> stack = new Stack<BTNode>(); while (p != null ) { while (p != null ) { if (p.getRight() != null ) stack.push(p.getRight()); // 当前节点右子入栈 stack.push(p); // 当前节点入栈 p = p.getLeft(); } p = stack.pop(); while (!stack.empty() && p.getRight() == null ) { visit(p); p = stack.pop(); } visit(p); if (!stack.empty()) p = stack.pop(); else p = null ; } } public static void main(String[] args) { BinTree tree = new BinTree(init()); System.out.print( " Pre-Order:" ); preorder(tree.getRoot()); System.out.println(); System.out.print( " In-Order:" ); inorder(tree.getRoot()); System.out.println(); System.out.print( "Post-Order:" ); postorder(tree.getRoot()); System.out.println(); System.out.print( " Pre-Order:" ); iterativePreorder(tree.getRoot()); System.out.println(); System.out.print( " In-Order:" ); iterativeInorder(tree.getRoot()); System.out.println(); System.out.print( "Post-Order:" ); iterativePostorder(tree.getRoot()); System.out.println(); }}输出结果 Pre-Order:H D B A C G F E In-Order:B A D C H G E F Post-Order:A B C D E F G H Pre-Order:H D B A C G F E In-Order:B A D C H G E F Post-Order:A B C D E F G H
本文出自 “子 孑” 博客，请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/82616
