二叉树遍历算法
2019-07-23 本文已影响16人
xiaolyuh
二叉树遍历算法有4种，先序、中序、后序和层序遍历
先序遍历：先根、后左、再右
中序遍历：先左、后根、再右
后序遍历：先左、后右、再根
层序遍历：从上往下，从左往右
二叉树.png
先序遍历：A → B → D → C
中序遍历：B → D → A → C
后续遍历：D → B → C → A
层序遍历：A → B → C → D
先序遍历：A → B → D → C
/**
* 先序遍历递归：先根、后左、再右
* <p>
* "A","B","D","C"
*/
public static void preorderIterable1(BinTreeNode<String> root, List<String> list) {
if (root == null) {
return;
}
list.add(root.data);
preorderIterable1(root.left, list);
preorderIterable1(root.right, list);
}
/**
* 先序遍历非递归：先根、后左、再右
* a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；
* b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；
* c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。
* <p>
* "A","B","D","C"
*/
public static void preorderIterable2(BinTreeNode<String> root, List<String> list) {
BinTreeNode<String> p = root;
Stack<BinTreeNode<String>> stack = new Stack<>();
while (p != null || !stack.empty()) {
while (p != null) {
list.add(p.data);
stack.push(p);
p = p.left;
}
if (!stack.isEmpty()) {
//节点弹出堆栈
p = stack.pop();
// 转向右子树
p = p.right;
}
}
}
中序遍历：B → D → A → C
/**
* 中序遍历递归：先左、后根、再右
* <p>
* "B","D","A","C"
*/
public static void middleIterable1(BinTreeNode<String> root, List<String> list) {
if (root == null) {
return;
}
middleIterable1(root.left, list);
list.add(root.data);
middleIterable1(root.right, list);
}
/**
* 中序遍历递归：先左、后根、再右
* <p>
* "B","D","A","C"
*/
public static void middleIterable2(BinTreeNode<String> root, List<String> list) {
Stack<BinTreeNode<String>> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
list.add(root.data);
root = root.right;
}
}
}
后续遍历：D → B → C → A
/**
* 后序遍历递归：先左、后右、再根
* <p>
* "B","D","A","C"
*/
public static void backIterable1(BinTreeNode<String> root, List<String> list) {
if (root == null) {
return;
}
backIterable1(root.left, list);
backIterable1(root.right, list);
list.add(root.data);
}
/**
* 中序遍历递归：先左、后右、再根
* <p>
* "B","D","A","C"
*/
public static void backIterable2(BinTreeNode<String> root, List<String> list) {
Stack<BinTreeNode<String>> stack = new Stack<>();
BinTreeNode<String> prev = null, curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
// 添加根节点
stack.push(curr);
// 递归添加左节点
curr = curr.left;
}
// 已经访问到最左节点了
curr = stack.peek();
// 是否存在右节点或者右节点已经访问过的情况下，访问根节点
if (curr.right == null || curr.right == prev) {
stack.pop();
list.add(curr.data);
prev = curr;
// 不重复访问自己
curr = null;
} else {
// 右节点还没有访问过就先访问右节点
curr = curr.right;
}
}
}
层序遍历：A → B → C → D
/**
* 层序遍历
*
* @param root
* @return
*/
public static void layerIterable2(BinTreeNode<String> root, List<String> list) {
LinkedList<BinTreeNode<String>> queue = new LinkedList<>();
if (root == null) {
return;
}
queue.addLast(root);
while (!queue.isEmpty()) {
BinTreeNode<String> p = queue.poll();
list.add(p.data);
if (p.left != null) {
queue.addLast(p.left);
}
if (p.right != null) {
queue.addLast(p.right);
}
}
}
完整代码
package com.xiaolyuh;
import com.alibaba.fastjson.JSON;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/**
* 二叉树的遍历
*
* @author yuhao.wang3
* @since 2019/7/22 19:47
*/
public class BinTreeIterable {
// A
// / \
// B C
// \
// D
static BinTreeNode<String> D = new BinTreeNode<>("D", null, null);
static BinTreeNode<String> B = new BinTreeNode<>("B", null, D);
static BinTreeNode<String> C = new BinTreeNode<>("C", null, null);
static BinTreeNode<String> A = new BinTreeNode<>("A", B, C);
public static void main(String[] args) {
List<String> list = new LinkedList<>();
preorderIterable1(A, list);
System.out.println("先序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
preorderIterable2(A, list);
System.out.println("先序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
middleIterable1(A, list);
System.out.println("中序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
middleIterable2(A, list);
System.out.println("中序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
backIterable1(A, list);
System.out.println("后序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
backIterable2(A, list);
System.out.println("后序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
layerIterable2(A, list);
System.out.println("层序遍历: " + JSON.toJSONString(list));
list = new LinkedList<>();
backIterable2(A, list);
System.out.println("层序遍历: " + JSON.toJSONString(list));
}
/**
* 先序遍历递归：先根、后左、再右
* <p>
* "A","B","D","C"
*/
public static void preorderIterable1(BinTreeNode<String> root, List<String> list) {
if (root == null) {
return;
}
list.add(root.data);
preorderIterable1(root.left, list);
preorderIterable1(root.right, list);
}
/**
* 先序遍历非递归：先根、后左、再右
* a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；
* b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；
* c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。
* <p>
* "A","B","D","C"
*/
public static void preorderIterable2(BinTreeNode<String> root, List<String> list) {
BinTreeNode<String> p = root;
Stack<BinTreeNode<String>> stack = new Stack<>();
while (p != null || !stack.empty()) {
while (p != null) {
list.add(p.data);
stack.push(p);
p = p.left;
}
if (!stack.isEmpty()) {
//节点弹出堆栈
p = stack.pop();
// 转向右子树
p = p.right;
}
}
}
/**
* 中序遍历递归：先左、后根、再右
* <p>
* "B","D","A","C"
*/
public static void middleIterable1(BinTreeNode<String> root, List<String> list) {
if (root == null) {
return;
}
middleIterable1(root.left, list);
list.add(root.data);
middleIterable1(root.right, list);
}
/**
* 中序遍历递归：先左、后根、再右
* <p>
* "B","D","A","C"
*/
public static void middleIterable2(BinTreeNode<String> root, List<String> list) {
Stack<BinTreeNode<String>> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
list.add(root.data);
root = root.right;
}
}
}
/**
* 后序遍历递归：先左、后右、再根
* <p>
* "B","D","A","C"
*/
public static void backIterable1(BinTreeNode<String> root, List<String> list) {
if (root == null) {
return;
}
backIterable1(root.left, list);
backIterable1(root.right, list);
list.add(root.data);
}
/**
* 中序遍历递归：先左、后右、再根
* <p>
* "B","D","A","C"
*/
public static void backIterable2(BinTreeNode<String> root, List<String> list) {
Stack<BinTreeNode<String>> stack = new Stack<>();
BinTreeNode<String> prev = null, curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
// 添加根节点
stack.push(curr);
// 递归添加左节点
curr = curr.left;
}
// 已经访问到最左节点了
curr = stack.peek();
// 是否存在右节点或者右节点已经访问过的情况下，访问根节点
if (curr.right == null || curr.right == prev) {
stack.pop();
list.add(curr.data);
prev = curr;
// 不重复访问自己
curr = null;
} else {
// 右节点还没有访问过就先访问右节点
curr = curr.right;
}
}
}
/**
* 层序遍历
*
* @param root
* @return
*/
public static void layerIterable2(BinTreeNode<String> root, List<String> list) {
LinkedList<BinTreeNode<String>> queue = new LinkedList<>();
if (root == null) {
return;
}
queue.addLast(root);
while (!queue.isEmpty()) {
BinTreeNode<String> p = queue.poll();
list.add(p.data);
if (p.left != null) {
queue.addLast(p.left);
}
if (p.right != null) {
queue.addLast(p.right);
}
}
}
static class BinTreeNode<T> {
/**
* 数据
*/
T data;
/**
* 左节点
*/
BinTreeNode<T> left;
/**
* 右节点
*/
BinTreeNode<T> right;
public BinTreeNode(T data, BinTreeNode left, BinTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return data.toString();
}
}
}
结果：
"C:\Program Files\Java\jdk1.8.0_112\bin\java.exe" -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:52461,suspend=y,server=n -Dvisualvm.id=126231185444436 -javaagent:C:\Users\yuhao.wang3\.IntelliJIdea2018.3\system\captureAgent\debugger-agent.jar -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_112\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_112\jre\lib\rt.jar;C:\Program Files\Java\jdk1.8.0_112\javafx-src.zip;C:\Program Files\Java\jdk1.8.0_112\src.zip;D:\workspace\spring-boot-student\spring-boot-student-concurrent\target\classes;C:\Users\yuhao.wang3\.m2\repository\org\springframework\boot\spring-boot-starter-web\1.5.13.RELEASE\spring-boot-starter-web-1.5.13.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\boot\spring-boot-starter-tomcat\1.5.13.RELEASE\spring-boot-starter-tomcat-1.5.13.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\apache\tomcat\embed\tomcat-embed-core\8.5.31\tomcat-embed-core-8.5.31.jar;C:\Users\yuhao.wang3\.m2\repository\org\apache\tomcat\tomcat-annotations-api\8.5.31\tomcat-annotations-api-8.5.31.jar;C:\Users\yuhao.wang3\.m2\repository\org\apache\tomcat\embed\tomcat-embed-el\8.5.31\tomcat-embed-el-8.5.31.jar;C:\Users\yuhao.wang3\.m2\repository\org\apache\tomcat\embed\tomcat-embed-websocket\8.5.31\tomcat-embed-websocket-8.5.31.jar;C:\Users\yuhao.wang3\.m2\repository\org\hibernate\hibernate-validator\5.3.6.Final\hibernate-validator-5.3.6.Final.jar;C:\Users\yuhao.wang3\.m2\repository\javax\validation\validation-api\1.1.0.Final\validation-api-1.1.0.Final.jar;C:\Users\yuhao.wang3\.m2\repository\org\jboss\logging\jboss-logging\3.3.2.Final\jboss-logging-3.3.2.Final.jar;C:\Users\yuhao.wang3\.m2\repository\com\fasterxml\classmate\1.3.4\classmate-1.3.4.jar;C:\Users\yuhao.wang3\.m2\repository\com\fasterxml\jackson\core\jackson-databind\2.8.11.1\jackson-databind-2.8.11.1.jar;C:\Users\yuhao.wang3\.m2\repository\com\fasterxml\jackson\core\jackson-annotations\2.8.0\jackson-annotations-2.8.0.jar;C:\Users\yuhao.wang3\.m2\repository\com\fasterxml\jackson\core\jackson-core\2.8.11\jackson-core-2.8.11.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-web\4.3.17.RELEASE\spring-web-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-aop\4.3.17.RELEASE\spring-aop-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-beans\4.3.17.RELEASE\spring-beans-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-context\4.3.17.RELEASE\spring-context-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-webmvc\4.3.17.RELEASE\spring-webmvc-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-expression\4.3.17.RELEASE\spring-expression-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\com\alibaba\fastjson\1.2.47\fastjson-1.2.47.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\boot\spring-boot-starter\1.5.13.RELEASE\spring-boot-starter-1.5.13.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\boot\spring-boot\1.5.13.RELEASE\spring-boot-1.5.13.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\boot\spring-boot-autoconfigure\1.5.13.RELEASE\spring-boot-autoconfigure-1.5.13.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\boot\spring-boot-starter-logging\1.5.13.RELEASE\spring-boot-starter-logging-1.5.13.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\ch\qos\logback\logback-classic\1.1.11\logback-classic-1.1.11.jar;C:\Users\yuhao.wang3\.m2\repository\ch\qos\logback\logback-core\1.1.11\logback-core-1.1.11.jar;C:\Users\yuhao.wang3\.m2\repository\org\slf4j\jcl-over-slf4j\1.7.25\jcl-over-slf4j-1.7.25.jar;C:\Users\yuhao.wang3\.m2\repository\org\slf4j\jul-to-slf4j\1.7.25\jul-to-slf4j-1.7.25.jar;C:\Users\yuhao.wang3\.m2\repository\org\slf4j\log4j-over-slf4j\1.7.25\log4j-over-slf4j-1.7.25.jar;C:\Users\yuhao.wang3\.m2\repository\org\springframework\spring-core\4.3.17.RELEASE\spring-core-4.3.17.RELEASE.jar;C:\Users\yuhao.wang3\.m2\repository\org\yaml\snakeyaml\1.17\snakeyaml-1.17.jar;C:\Users\yuhao.wang3\.m2\repository\org\slf4j\slf4j-api\1.7.25\slf4j-api-1.7.25.jar;C:\Users\yuhao.wang3\.m2\repository\com\h2database\h2\1.4.197\h2-1.4.197.jar;D:\Program Files\JetBrains\IntelliJ IDEA 2018.3.2\lib\idea_rt.jar" com.xiaolyuh.BinTreeIterable
Connected to the target VM, address: '127.0.0.1:52461', transport: 'socket'
先序遍历: ["A","B","D","C"]
先序遍历: ["A","B","D","C"]
中序遍历: ["B","D","A","C"]
中序遍历: ["B","D","A","C"]
后序遍历: ["D","B","C","A"]
后序遍历: ["D","B","C","A"]
层序遍历: ["A","B","C","D"]
层序遍历: ["D","B","C","A"]
Disconnected from the target VM, address: '127.0.0.1:52461', transport: 'socket'
Process finished with exit code 0
源码
https://github.com/wyh-spring-ecosystem-student/spring-boot-student/tree/releases
spring-boot-student-concurrent 工程
layering-cache
为监控而生的多级缓存框架 layering-cache这是我开源的一个多级缓存框架的实现，如果有兴趣可以看一下
