二叉樹遍歷（附Java實(shí)現(xiàn)代碼）

二叉樹遍歷可以有兩種方法：遞歸遍歷的方式與非遞歸遍歷的方式。

先序遍歷就是先遍歷根節(jié)點(diǎn)再左再右；

中序遍歷就是先左再根再右；

后序遍歷就是先左再右再根；

先構(gòu)建這棵樹，然后分別調(diào)用相應(yīng)的方法實(shí)現(xiàn)，代碼如下：

package binarytree;import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack;public class Test {//遞歸遍歷的方式與非遞歸遍歷的方式://一、遞歸的方式：//1、先序遍歷：private static void preOrder1(Node root){if(root == null) return;System.out.print(root.value);preOrder1(root.left);preOrder1(root.right);}//2、中序遍歷：private static void midOrder1(Node root){if(root == null) return;midOrder1(root.left);System.out.print(root.value);midOrder1(root.right);}//3、后序遍歷：private static void postOrder1(Node root){if(root == null) return;postOrder1(root.left);postOrder1(root.right);System.out.print(root.value);}//二、非遞歸的方式：//1、先序遍歷：private static void preOrder2(Node root){if(root == null) return;Stack<Node> stack = new Stack<>();//用棧來存儲(chǔ)（先進(jìn)后出）stack.push(root);while(!stack.isEmpty()){Node node = stack.pop();System.out.print(node.value);if(node.right != null) stack.push(node.right);if(node.left != null) stack.push(node.left);}}//2、中序遍歷private static void midOrder2(Node root){if(root == null) return;Stack<Node> stack = new Stack<>();Node cur = root;while(!stack.isEmpty() || cur != null){while(cur != null){stack.push(cur);cur = cur.left;}Node node = stack.pop();System.out.print(node.value);if(node.right != null) cur= node.right;}}//3、后序遍歷：private static void postOrder2(Node root){if(root == null) return;Stack<Node> stack = new Stack<>();Stack<Node> stack2 = new Stack<>();stack.push(root);while(!stack.isEmpty()){Node node = stack.pop();stack2.push(node);if(node.left != null) stack.push(node.left);if(node.right != null) stack.push(node.right);}while(!stack2.isEmpty()){System.out.print(stack2.pop().value);}}//三、層序遍歷private static void bfs(Node root){if(root == null) return;Queue<Node> queue = new LinkedList<>();//用隊(duì)列來存儲(chǔ)（先進(jìn)先出）queue.add(root);while(!queue.isEmpty()){Node node = queue.poll();System.out.print(node.value);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}}private static List<List<String>> bfs2(Node root){List<List<String>> res = new ArrayList<>();//存儲(chǔ)節(jié)點(diǎn)（List里面套List）Queue<Node> queue = new LinkedList<>();//用隊(duì)列來存儲(chǔ)（先進(jìn)先出）queue.add(root);List<String> list;while(!queue.isEmpty()){int size = queue.size();list = new ArrayList<>();while(size-- > 0){Node node = queue.poll();list.add(node.value);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}res.add(list);}return res;}public static void main(String[] args) {Node nodeA = new Node("A");Node nodeB = new Node("B");Node nodeC = new Node("C");Node nodeD = new Node("D");Node nodeE = new Node("E");Node nodeF = new Node("F");Node nodeG = new Node("G");//構(gòu)建二叉樹nodeA.left = nodeB;nodeA.right = nodeC;nodeB.left = nodeD;nodeB.right = nodeE;nodeC.right = nodeF;nodeE.left = nodeG;preOrder1(nodeA);System.out.println();midOrder1(nodeA);System.out.println();postOrder1(nodeA);System.out.println();preOrder2(nodeA);System.out.println();midOrder2(nodeA);System.out.println();postOrder2(nodeA);System.out.println();bfs(nodeA);bfs2(nodeA);}public static class Node{ //節(jié)點(diǎn)public String value;public Node left;public Node right;public Node(String value){this.value = value;}}}

運(yùn)行結(jié)果如下圖所示：

其中，層序遍歷這里多寫了一個(gè)方法，將每層的節(jié)點(diǎn)存儲(chǔ)起來：

private static List<List<String>> bfs2(Node root){List<List<String>> res = new ArrayList<>();//存儲(chǔ)節(jié)點(diǎn)（List里面套List）Queue<Node> queue = new LinkedList<>();//用隊(duì)列來存儲(chǔ)（先進(jìn)先出）queue.add(root);List<String> list;while(!queue.isEmpty()){int size = queue.size();list = new ArrayList<>();while(size-- > 0){Node node = queue.poll();list.add(node.value);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}res.add(list);}return res;}

在debug中查看res的結(jié)果：

【參考Queue部分】http://blog.sina.com.cn/s/blog_14ffae8a60102x2x6.html
【視頻參考】https://www.bilibili.com/video/BV1oV411d7U5?spm_id_from=333.999.0.0

總結(jié)

以上是生活随笔為你收集整理的二叉树遍历（附Java实现代码）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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