1. 二叉樹的前序遍歷（深度優(yōu)先遍歷）

二叉樹的節(jié)點(diǎn)定義

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x;} }

遞歸實(shí)現(xiàn)：

public class MyTest {static ArrayList<Integer> list = new ArrayList<>();public int fisrtTraversal(TreeNode node) {// 判斷該節(jié)點(diǎn)是否存在if (node == null) {return 0;}list.add(node.val);firstTraversal(node.left);firstTraversal(node.right);return 0;} }

非遞歸實(shí)現(xiàn)：

public class MyTest {public ArrayList<Integer> fisrtTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack = new Stack<>();stack.add(root);TreeNode node = null;while (!stack.isEmpty()) {node = stack.pop();list.add(node.val);if (node.left != null) {stack.add(node.left);}if (node.right != null) {stack.add(node.right);}}return list;} }

2. 二叉樹的中序遍歷

遞歸實(shí)現(xiàn)：

public class MyTest {static ArrayList<Integer> list = new ArrayList<>();public int midTraversal(TreeNode node) {// 判斷該節(jié)點(diǎn)是否存在if (node == null) {return 0;}firstTraversal(node.left);list.add(node.val);firstTraversal(node.right);return 0;} }

非遞歸實(shí)現(xiàn)：
利用棧實(shí)現(xiàn)。如圖所示，向左斜下方向依次入棧，直達(dá)葉子節(jié)點(diǎn)；然后出棧兩個(gè)（本身與其父節(jié)點(diǎn)）。

執(zhí)行過(guò)程：
入棧：1、2、4 出棧：4、2
入棧：5 出棧：5
入棧：3、6 出棧：6、2
入棧：7 出棧：7

最終的中序遍歷結(jié)果為：4、2、5、6、2、7

public class MyTest {public ArrayList<Integer> midTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list}Stack<TreeNode> stack = new Stack<>();stack.add(root);TreeNode node = root;while (!stack.isEmpty()) {if ((node != null) && (node.left != null)) {stack.add(node.left);node = node.left;} else {node = stack.pop();list.add(node.val);if (!stack.isEmpty()) {node = stack.pop();list.add(node.val);}node = node.right;}}return list;} }

3. 二叉樹的后序遍歷

遞歸實(shí)現(xiàn)：

public class MyTest {static ArrayList<Integer> list = new ArrayList<>();public int lastTraversal(TreeNode node) {// 判斷該節(jié)點(diǎn)是否存在if (node == null) {return 0;}firstTraversal(node.left);firstTraversal(node.right);list.add(node.val);return 0;} }

非遞歸實(shí)現(xiàn)：
用兩個(gè)棧（Stack1、Stack2）來(lái)實(shí)現(xiàn)。

將node壓入Stack1，取出來(lái)把node的左右子節(jié)點(diǎn)，都?jí)哼M(jìn)Stack2；再把node壓入Stack2。這樣循環(huán)下去，Stack2的出棧順序就是后續(xù)遍歷。

public class MyTest {public ArrayList<Integer> lastTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.add(root);TreeNode node = null;while (!stack1.isEmpty()) {node = stack1.pop();if (node.left != null) {stack1.add(node.left);}if (node.right != null) {stack1.add(node.right);}stack2.add(node);}while (!stack2.isEmpty()) {list.add(stack2.pop().val);}return list;} }

4. 二叉樹的廣度優(yōu)先遍歷（層次遍歷）

非遞歸實(shí)現(xiàn)（利用隊(duì)列）：

public class MyTest {public ArrayList<Integer> levelTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();if (root == null) {return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);TreeNode node = null;while (!queue.isEmpty()) {node = queue.poll();list.offer(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return list;} }

總結(jié)

以上是生活随笔為你收集整理的二叉树遍历的递归、非递归方法（前序、中序、后序，层序）——Java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。