java二叉树遍历

 

前序遍历（DLR）

　　前序遍历也叫做先根遍历，可记做根左右。

　　前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

　　若二叉树为空则结束返回，否则：

　　（1）访问根结点. 　（2）前序遍历左子树.

　　

　　（3）前序遍历右子树 . 　注意的是：遍历左右子树时仍然采用前序遍历方法。

　　

　　如上图所示二叉树

　　前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树

　　遍历结果：ABDECF

　　中序遍历，也叫中根遍历，顺序是 左子树，根，右子树

　　遍历结果：DBEAFC

　　后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根

　　遍历结果：DEBFCA

 

import java.util.Stack;

/** 二叉树节点 */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(); }}