二叉树的先序中序后续遍历（递归非递归）

转载：http://blog.csdn.net/jssongwei/article/details/50790253

 首先来看一棵二叉树：

1、前序遍历：

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点；
（2）前序遍历左子树；
（3）前序遍历右子树 ；
需要注意的是：遍历左右子树时仍然采用前序遍历方法。可以看出前序遍历后，遍历结果为：631254978
2、中序遍历：
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树；
注意的是：遍历左右子树时仍然采用中序遍历方法。最上图的二叉树用中序遍历的结果是：123456789
3、后续遍历：
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点；
如图所示的二叉树，用后序遍历的结果是：214538796
 
三种遍历的递归实现：
[java] view plain copy
 
  1. public class Node {//二叉树节点  
  2.       
  3.     private int data;  
  4.     private Node leftNode;  
  5.     private Node rightNode;  
  6.       
  7.     public Node(int data, Node leftNode, Node rightNode){  
  8.         this.data = data;  
  9.         this.leftNode = leftNode;  
  10.         this.rightNode = rightNode;  
  11.     }  
  12.       
  13.     public int getData(){  
  14.         return data;  
  15.     }  
  16.       
  17.     public void setData(int data){  
  18.         this.data = data;  
  19.     }  
  20.       
  21.     public Node getLeftNode(){  
  22.         return leftNode;  
  23.     }  
  24.       
  25.     public void setLeftNode(Node leftNode){  
  26.         this.leftNode = leftNode;  
  27.     }  
  28.       
  29.     public Node getRightNode(){  
  30.         return rightNode;  
  31.     }  
  32.       
  33.     public void setRightNode(Node rightNode){  
  34.         this.rightNode = rightNode;  
  35.     }  
  36.       
  37. }  

三种遍历的递归实现：
[java] view plain copy
 
  1. public class BinaryTree_DiGui {  
  2.       
  3.     /* 
  4.      * 二叉树先序中序后序排序 
  5.      * 方式：递归。 
  6.      */  
  7.       
  8.     //注意必须逆序简历，先建立子节点，再逆序往上建立，  
  9.     //因为非叶子节点会使用到下面的节点，而初始化是按顺序初始化得，不逆序建立会报错  
  10.     public static Node init(){  
  11.         Node J = new Node(8, null, null);  
  12.         Node H = new Node(4, null, null);  
  13.         Node G = new Node(2, null, null);  
  14.         Node F = new Node(7, null, J);  
  15.         Node E = new Node(5, H, null);  
  16.         Node D = new Node(1, null, G);  
  17.         Node C = new Node(9, F, null);  
  18.         Node B = new Node(3, D, E);  
  19.         Node A = new Node(6, B, C);  
  20.         return A;  //返回根节点  
  21.     }  
  22.       
  23.     //打印节点数值  
  24.     public static void printNode(Node node){  
  25.         System.out.print(node.getData());  
  26.     }  
  27.       
  28.       
  29.     //先序遍历  
  30.     public static void preOrder(Node root){  
  31.           
  32.         printNode(root);//打印根节点  
  33.           
  34.         if(root.getLeftNode() != null){//使用递归遍历左孩子  
  35.             preOrder(root.getLeftNode());  
  36.         }  
  37.         if(root.getRightNode() != null){//使用递归遍历右孩子  
  38.             preOrder(root.getRightNode());  
  39.         }  
  40.     }  
  41.       
  42.       
  43.     //中序遍历  
  44.     public static void inOrder(Node root){  
  45.           
  46.         if(root.getLeftNode() != null){//使用递归遍历左孩子  
  47.             inOrder(root.getLeftNode());  
  48.         }  
  49.           
  50.         printNode(root);//打印根节点  
  51.           
  52.         if(root.getRightNode() != null){//使用递归遍历右孩子  
  53.             inOrder(root.getRightNode());  
  54.         }  
  55.     }  
  56.       
  57.       
  58.     //后续遍历  
  59.     public static void postOrder(Node root){  
  60.           
  61.         if(root.getLeftNode() != null){//使用递归遍历左孩子  
  62.             postOrder(root.getLeftNode());  
  63.         }  
  64.           
  65.         if(root.getRightNode() != null){//使用递归遍历右孩子  
  66.             postOrder(root.getRightNode());  
  67.         }  
  68.           
  69.         printNode(root);//打印根节点  
  70.     }  
  71.       
  72.       
  73.     public static void main(String[] args){  
  74. //      BinaryTree tree = new BinaryTree();//注释掉本行后类中方法需变为static  
  75.         Node root = init();  
  76.           
  77.         System.out.println("先序遍历");  
  78.         preOrder(root);  
  79.         System.out.println("");  
  80.           
  81.         System.out.println("中序遍历");  
  82.         inOrder(root);  
  83.         System.out.println("");  
  84.           
  85.         System.out.println("后序遍历");  
  86.         postOrder(root);  
  87.         System.out.println("");  
  88.           
  89.     }  
  90.       
  91. }  
 
 

通过栈实现三种遍历（非递归）：
[java] view plain copy
 
  1. public class BinaryTree_Zhan {  
  2.       
  3.     /* 
  4.      *  
  5.      * 二叉树先序中序后序排序 
  6.      * 方式：采用非递归方式。 
  7.      */  
  8.       
  9.     //注意必须逆序简历，先建立子节点，再逆序往上建立，  
  10.     //因为非叶子节点会使用到下面的节点，而初始化是按顺序初始化得，不逆序建立会报错  
  11.     public static Node init(){  
  12.         Node J = new Node(8, null, null);  
  13.         Node H = new Node(4, null, null);  
  14.         Node G = new Node(2, null, null);  
  15.         Node F = new Node(7, null, J);  
  16.         Node E = new Node(5, H, null);  
  17.         Node D = new Node(1, null, G);  
  18.         Node C = new Node(9, F, null);  
  19.         Node B = new Node(3, D, E);  
  20.         Node A = new Node(6, B, C);  
  21.         return A;  //返回根节点  
  22.     }  
  23.       
  24.     //打印节点数值  
  25.     public static void printNode(Node node){  
  26.         System.out.print(node.getData());  
  27.     }  
  28.       
  29.       
  30.     public static void preOrder_stack(Node root){//先序遍历  
  31.           
  32.         Stack<Node> stack = new Stack<Node>();  
  33.         Node node = root;  
  34.           
  35.         while(node != null || stack.size()>0){//将所有左孩子压栈  
  36.             if(node != null){//压栈之前先访问  
  37.                 printNode(node);  
  38.                 stack.push(node);  
  39.                 node = node.getLeftNode();  
  40.                   
  41.             }else{  
  42.                 node = stack.pop();  
  43.                 node = node.getRightNode();  
  44.             }  
  45.         }  
  46.     }  
  47.       
  48.       
  49.     public static void inOrder_Stack(Node root){//中序遍历  
  50.           
  51.         Stack<Node> stack = new Stack<Node>();  
  52.         Node node = root;  
  53.           
  54.         while(node != null || stack.size()>0){  
  55.             if(node != null){  
  56.                 stack.push(node);//直接压栈  
  57.                 node = node.getLeftNode();  
  58.             }else{  
  59.                 node = stack.pop();//出栈并访问  
  60.                 printNode(node);  
  61.                 node = node.getRightNode();  
  62.             }  
  63.         }  
  64.     }  
  65.       
  66.       
  67.     public static void postOrder_Stack(Node root){//后续遍历  
  68.           
  69.         Stack<Node> stack = new Stack<Node>();  
  70.         Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后续遍历的结果  
  71.         Node node = root;  
  72.         while(node != null || stack.size()>0){  
  73.             if(node != null){  
  74.                 output.push(node);  
  75.                 stack.push(node);  
  76.                 node = node.getRightNode();  
  77.             }else{  
  78.                 node = stack.pop();  
  79.                 node = node.getLeftNode();  
  80.             }  
  81.         }  
  82.           
  83.         while(output.size()>0){  
  84.             printNode(output.pop());  
  85.         }  
  86.           
  87.     }  
  88.       
  89.       
  90.     public static void main(String[] args){  
  91.           
  92.         Node root = init();  
  93.           
  94.         System.out.println("先序遍历");  
  95.         preOrder_stack(root);  
  96.         System.out.println("");  
  97.           
  98.         System.out.println("中序遍历");  
  99.         inOrder_Stack(root);   
  100.         System.out.println("");  
  101.           
  102.         System.out.println("后序遍历");  
  103.         postOrder_Stack(root);  
  104.         System.out.println("");  
  105.     }  
  106.   
  107. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xiaolovewei/p/8242513.html