二叉树三种遍历(java递归以及非递归实现)

  1. package com.shiyeqiang.tree;  
  2.   
  3. import java.util.Stack;  
  4.   
  5. public class BiTree {  
  6.   
  7.     public static void main(String[] args) {  
  8.   
  9.         // 首先构造叶子节点  
  10.         BiTree leafA1 = new BiTree(4);  
  11.         BiTree leafA2 = new BiTree(5);  
  12.         BiTree leafB1 = new BiTree(6);  
  13.         BiTree leafB2 = new BiTree(7);  
  14.         // 构建二叉树的结构  
  15.         BiTree treeA = new BiTree(2, leafA1, leafA2);  
  16.         BiTree treeB = new BiTree(3, leafB1, leafB2);  
  17.         BiTree tree = new BiTree(1, treeA, treeB);  
  18.   
  19.         System.out.println(“递归前序遍历二叉树结果: “);  
  20.         preOrder(tree);  
  21.         System.out.println();  
  22.         System.out.println(“非递归前序遍历二叉树结果: “);  
  23.         iterativePreOrder(tree);  
  24.         System.out.println();  
  25.         System.out.println(“非递归中序遍历二叉树结果: “);  
  26.         iterativeInOrder(tree);  
  27.         System.out.println();  
  28.         System.out.println(“递归后续遍历二叉树结果: “);  
  29.         iterativePostOrder(tree);  
  30.     }  
  31.   
  32.     private BiTree leftTree;  
  33.     private BiTree rightTree;  
  34.     private Object data;  
  35.   
  36.     public BiTree() {  
  37.   
  38.     }  
  39.   
  40.     public BiTree(Object data) {  
  41.         this.data = data;  
  42.     }  
  43.   
  44.     public BiTree(Object data, BiTree leftTree, BiTree rightTree) {  
  45.         this.data = data;  
  46.         this.leftTree = leftTree;  
  47.         this.rightTree = rightTree;  
  48.     }  
  49.   
  50.     public static void visit(Object data) { // 访问二叉树的数据  
  51.         System.out.print(data + ”  “);  
  52.     }  
  53.   
  54.     public static void preOrder(BiTree tree) {  
  55.         // 递归实现前序遍历二叉树  
  56.         if (tree != null) {  
  57.             visit(tree.data);  
  58.             if (tree.leftTree != null)  
  59.                 preOrder(tree.leftTree);  
  60.             if (tree.rightTree != null)  
  61.                 preOrder(tree.rightTree);  
  62.         }  
  63.     }  
  64.   
  65.     public static void inOrder(BiTree tree) {  
  66.         // 递归实现中序遍历二叉树(左-根–右边)  
  67.         if (tree != null) {  
  68.             if (tree.leftTree != null)  
  69.                 inOrder(tree.leftTree);  
  70.             visit(tree.data);  
  71.             if (tree.rightTree != null)  
  72.                 inOrder(tree.rightTree);  
  73.         }  
  74.     }  
  75.   
  76.     public static void postOrder(BiTree tree) {  
  77.         // 递归实现后序遍历二叉树  
  78.         if (tree != null) {  
  79.             if (tree.leftTree != null)  
  80.                 postOrder(tree.leftTree);  
  81.             if (tree.rightTree != null)  
  82.                 postOrder(tree.rightTree);  
  83.             visit(tree.data);  
  84.         }  
  85.     }  
  86.   
  87.     // 非递归实现前序遍历,根—-左子树—右子树  
  88.     public static void iterativePreOrder(BiTree tree) {  
  89.         Stack<BiTree> stack = new Stack<BiTree>();  
  90.         if (tree != null) {  
  91.             stack.push(tree);  
  92.             while (!stack.isEmpty()) {  
  93.                 tree = stack.pop();  
  94.                 visit(tree.data);  
  95.                 if (tree.rightTree != null)  
  96.                     stack.push(tree.rightTree); // 首先必须是右子树入栈,  
  97.                 if (tree.leftTree != null)  
  98.                     stack.push(tree.leftTree);  
  99.             }  
  100.         }  
  101.     }  
  102.   
  103.     // 非递归实现中序遍历,左—根—右  
  104.     public static void iterativeInOrder(BiTree tree) {  
  105.         Stack<BiTree> stack = new Stack<BiTree>();  
  106.         // 主要是根据入栈以及出栈的思想实现的  
  107.         //以一个1,2,3,4,5,6,7的满二叉树为例:中序遍历如下:  
  108.         //右子树3入栈,根节点1入栈,右子树5入栈,根节点2入栈,根节点4入栈。  
  109.         //左子树4出栈,根节点2出栈,5出战,按照上述规则重新遍历右子树5  
  110.         while (tree != null) {  
  111.             while (tree != null) {  
  112.                 if (tree.rightTree != null)  
  113.                     stack.push(tree.rightTree);// 当前节点右子入栈  
  114.                 stack.push(tree);// 当前节点入栈  
  115.                 tree = tree.leftTree;  
  116.             }  
  117.             tree = stack.pop();  
  118.             // 下面为访问的是叶子节点  
  119.             while (!stack.empty() && tree.rightTree == null) {  
  120.   
  121.                 visit(tree.data);  
  122.                 tree = stack.pop();  
  123.             }  
  124.             visit(tree.data);  
  125.             if (!stack.empty()) {  
  126.                 tree = stack.pop(); // 下一次遍历,其实在这个时候遍历的是右子树把  
  127.   
  128.             } else {  
  129.                 tree = null;  
  130.   
  131.             }  
  132.   
  133.         }  
  134.     }  
  135.   
  136.     // 非递归实现后序遍历  
  137.     public static void iterativePostOrder(BiTree tree) {  
  138.         BiTree tempTree = tree;  
  139.         Stack<BiTree> stack = new Stack<BiTree>();  
  140.         while (tree != null) {  
  141.             // 左子树入栈  
  142.             for (; tree.leftTree != null; tree = tree.leftTree)  
  143.                 stack.push(tree);  
  144.             // 当前节点无右子或右子已经输出  
  145.             while (tree != null  
  146.                     && (tree.rightTree == null || tree.rightTree == tempTree)) {  
  147.                 visit(tree.data);  
  148.                 tempTree = tree;// 记录上一个已输出节点  
  149.                 if (stack.empty())  
  150.                     return;  
  151.                 tree = stack.pop(); //一般处理根节点的时候均是先出战 ,然后再入栈  
  152.             }  
  153.             // 处理右子  
  154.             stack.push(tree);  
  155.             tree = tree.rightTree;  
  156.         }  
  157.     }  
  158. }  

标签