Java数据结构——二叉树的遍历（汇总）
2024-08-28 02:54:35
二叉树的遍历分为深度优先遍历（DFS)和广度优先遍历（BFS)
DFS遍历主要有：
- 前序遍历
- 中序遍历
- 后序遍历
一、递归实现DFS
Node.java:
public class Node {
private Object data;
Node richild;
Node lechild;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getRichild() {
return richild;
}
public void setRichild(Node richild) {
this.richild = richild;
}
public Node getLechild() {
return lechild;
}
public void setLechild(Node lechild) {
this.lechild = lechild;
}
public Node(Object data, Node lechild, Node richild) {
super();
this.data = data;
this.richild = richild;
this.lechild = lechild;
}
public Node() {
super();
}
}
递归遍历：
public class BTree {
private static Node root;
//构造树
public static void init() {
Node node1 = new Node("A", null, null);
Node node2 = new Node("B", node1, null);
Node node3 = new Node("C", null, null);
Node node4 = new Node("D", node2, node3);
Node node5 = new Node("E", null, null);
Node node6 = new Node("F", null, node5);
Node node7 = new Node("G", node4, node6);
root = node7;
}
//访问节点
public static void visited(Node n) {
System.out.print(n.getData() + " ");
}
//前序遍历
public static void preOrder(Node n) {
if (n != null) {
visited(n);
preOrder(n.getLechild());
preOrder(n.getRichild());
}
}
//中序遍历
public static void inOrder(Node n) {
if (n != null) {
inOrder(n.getLechild());
visited(n);
inOrder(n.getRichild());
}
}
//后序遍历
public static void postOrder(Node n) {
if (n != null) {
postOrder(n.getLechild());
postOrder(n.getRichild());
visited(n);
}
}
public static void main(String[] args) {
init();
System.out.print("递归前序：");
preOrder(root);
System.out.println();
System.out.print("递归中序：");
inOrder(root);
System.out.println();
System.out.print("递归后序：");
postOrder(root);
System.out.println();
}
}
二、非递归实现DFS（依靠栈）
//前序遍历
public static void preOrder(Node n) {
System.out.print("非递归前序：");
Stack<Node> stack = new Stack<>();
int index = 0;
while (n != null || index > 0) {
while (n != null) {
System.out.print(n.getData() + " ");
stack.push(n);
index++;
n = n.getLechild();
}
n = stack.pop();
index--;
n = n.getRichild();
}
}
//中序遍历
public static void inOrder(Node n) {
System.out.print("非递归中序：");
Stack<Node> stack = new Stack<>();
int index = 0;
while (n != null || index > 0) {
while (n != null) {
stack.push(n);
index++;
n = n.getLechild();
}
n = stack.pop();
System.out.print(n.getData() + " ");
index--;
n = n.getRichild();
}
}
//后序遍历
public static void postOrder(Node n) {
System.out.print("非递归后序：");
Stack<Node> stack = new Stack<>();
int index = 0;
Node lastVisited = null;
while (n != null || index > 0) {
while (n != null) {
stack.push(n);
index++;
n = n.getLechild();
}
n = stack.peek();
if (n.getRichild() == null || n.getRichild() == lastVisited) {
System.out.print(n.getData() + " ");
lastVisited = n;
index--;
stack.pop();
n = null;
} else {
n = n.getRichild();
}
}
}
三、实现层序遍历（依靠队列）
public static void LevenOrder(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
Node temp = null;
while (!queue.isEmpty()) {
temp = queue.poll();
visited(temp);
if (temp.getLeChild() != null) {
queue.add(temp.getLeChild());
}
if (temp.getRChild() != null) {
queue.add(temp.getChild());
}
}
}
最新文章
- java的动态代理机制详解
- Nginx 502 bad gateway问题的解决方法
- struts(三) ---OGNL的学习和理解
- 让C程序更高效的10种方法（转）
- Codeforces Round #350 (Div. 2) F. Restore a Number 模拟构造题
- 阿里云之OSS 开放存储服务开发笔记
- AndroidApplication Fundamentals(Android应用基础)
- GUIText的淡入淡出
- JavaScript入门(8)
- 浏览器中的XML与JavaScript
- C# 创建新RTF文件
- Transfer learning across two sentiment classes using deep learning
- 疯狂JAVA讲义第三章之数组篇
- JS中event.keyCode用法及keyCode对…
- vue filter方法-时间格式化
- linux ar命令参数及用法详解--linux建立、修改或抽取备存文件命
- 20155208徐子涵《网络对抗》Exp2 后门原理与实践
- Vue 父组件方法和参数传给子组件的方法
- 《C#从现象到本质》读书笔记（七）第9章 泛型
- HDU6216