分別用遞歸和非遞歸方式實現二叉樹先序、中序和后序遍歷
用遞歸和非遞歸方式，分別按照二叉樹先序、中序和后序打印所有的節(jié)點。我們約定:先序遍歷順序 為根、左、右;中序遍歷順序為左、根、右;后序遍歷順序為左、右、根

先序遍歷：建立一個棧，頭節(jié)點入棧，將其出棧并打印，之后再依次將其右子節(jié)點入棧，左子節(jié)點入棧，棧頂節(jié)點出棧并打印，再依次將其右子節(jié)點和左子節(jié)點入棧，再將棧頂節(jié)點出棧并打印，遞歸實現。

public static void preOrderUnRecur(Node head){System.out.println("PreOrder:");if(head != null){Stack<Node> stack = new Stackk<Node>();stack.add(head);while(!stack.isEmpty()){head = stack.pop();System.out.print(head.value + " ");if(head.right ！= null){stack.push(head.right);}if(head.left!= null){stack.push(head.left);}}}System.out,println(); }

中序遍歷：先將二叉樹的左邊界依次入棧，頭節(jié)點出棧并打印，判斷該節(jié)點是否有右子樹，如果有則再將其子樹的左邊界入棧，遞歸實現，若沒有右子樹，繼續(xù)將棧頂節(jié)點出棧并打印，如果有右子樹則再將其子樹左邊界入棧，遞歸實現

public static void inOrderUnRecur(Node head){System.out.println("InOrder:");if(head != null){Stack<Node> stack = new Stack<Node>();while(!stackk.isEmpty() || head != null){if(head != null){stack.push(head);head = head.left;}else{head = stack.pop();System.out.print(head.value + " ");head = head.right;}}}System.out.println(); }
后序遍歷：頭節(jié)點入棧，用一個變量表示棧頂

public static void posOrderUnRecur1(Node head){System.out.print("PosOrder:");if(head != null){Stack<Node> s1 = new Stack<Node>();Stack<Node> s2 = new Stack<Node>();si.push(head);while(!s1.isEmpty()){head = s1.pop();s2.push(head);if(head.left != null){s1.push(head.left);}if(head.right != null){s1.push(head.right);}}while(!s2.isEmpty()){System.out.print(s2.pop().value + " ");}}System.out,println(); }public static void posOrderUnRecur2(Node h){Sytem.out.print("PosOrder:");if(h != null){Stack<Node> stack = new Stack<Node>();stack.push(h);Node c = null;while(!stack.isEmpty()){c = stack.peek();if(c.left ！= null && h != c.left && h != c.right){stack.push(c.left);}else if(c.right != null && h != c.right){stack.push(c.right);}else{System.out.print(stack.pop().value + " ");h = c;}}}System.out.println(); }

總結

以上是生活随笔為你收集整理的分别用递归和非递归方式实现二叉树先序、中序和后序遍历（java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。