图解二叉树的三种遍历方式及java实现代码
作者:Acamy丶 时间:2022-02-08 12:03:32
二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子。
1.二叉树节点
作为图的特殊形式,二叉树的基本组成单元是节点与边;作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用。
如下,给出了二叉树节点的数据结构图示和相关代码:
// 定义节点类:
private static class BinNode {
private Object element;
private BinNode lChild;// 定义指向左子树的指针
private BinNode rChild;// 定义指向右子树的指针
public BinNode(Object element, BinNode lChild, BinNode rChild) {
this.element = element;
this.lChild = lChild;
this.rChild = rChild;
}
}
2.递归遍历
二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序。
按惯例左兄弟优先于右兄弟,故若将节点及其孩子分别记作V、L和R,则下图所示,局部访问的次序可有VLR、LVR和LRV三种选择。根据节点V在其中的访问次序,三种策略也相应地分别称作先序遍历、中序遍历和后序遍历,下面将分别介绍。
2.1 先序遍历
图示:
代码实现:
/**
* 对该二叉树进行前序遍历 结果存储到list中 前序遍历
*/
public static void preOrder(BinNode node) {
list.add(node); // 先将根节点存入list
// 如果左子树不为空继续往左找,在递归调用方法的时候一直会将子树的根存入list,这就做到了先遍历根节点
if (node.lChild != null) {
preOrder(node.lChild);
}
// 无论走到哪一层,只要当前节点左子树为空,那么就可以在右子树上遍历,保证了根左右的遍历顺序
if (node.rChild != null) {
preOrder(node.rChild);
}
}
2.2 中序遍历
图示:
代码实现:
/**
* 对该二叉树进行中序遍历 结果存储到list中
*/
public static void inOrder(BinNode node) {
if (node.lChild != null) {
inOrder(node.lChild);
}
list.add(node);
if (node.rChild != null) {
inOrder(node.rChild);
}
}
2.3 后序遍历
实例图示:
代码实现:
/**
* 对该二叉树进行后序遍历 结果存储到list中
*/
public static void postOrder(BinNode node) {
if (node.lChild != null) {
postOrder(node.lChild);
}
if (node.rChild != null) {
postOrder(node.rChild);
}
list.add(node);
}
附:测试相关代码
private static BinNode root;
private static List<BinNode> list = new ArrayList<BinNode>();
public static void main(String[] args) {
init();
// TODO Auto-generated method stub
//preOrder(root);
//inOrder(root);
postOrder(root);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i).element + " ");
}
}
// 树的初始化:先从叶节点开始,由叶到根
public static void init() {
BinNode b = new BinNode("b", null, null);
BinNode a = new BinNode("a", null, b);
BinNode c = new BinNode("c", a, null);
BinNode e = new BinNode("e", null, null);
BinNode g = new BinNode("g", null, null);
BinNode f = new BinNode("f", e, g);
BinNode h = new BinNode("h", f, null);
BinNode d = new BinNode("d", c, h);
BinNode j = new BinNode("j", null, null);
BinNode k = new BinNode("k", j, null);
BinNode m = new BinNode("m", null, null);
BinNode o = new BinNode("o", null, null);
BinNode p = new BinNode("p", o, null);
BinNode n = new BinNode("n", m, p);
BinNode l = new BinNode("l", k, n);
root = new BinNode("i", d, l);
}
来源:http://www.jianshu.com/p/f0a6d594711d
标签:java,二叉树,遍历
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java Web学习之Cookie和Session的深入理解
2022-10-28 14:47:10
![](https://img.aspxhome.com/file/2023/0/77490_0s.jpg)
关于Mybatis插入对象时空值的处理
2023-08-28 21:58:00
Java Timer使用讲解
2023-11-28 20:30:33
Java事务管理学习之Spring和Hibernate详解
2023-04-11 00:01:25
![](https://img.aspxhome.com/file/2023/4/62684_0s.png)
C#中委托的基础入门与实现方法
2022-05-24 22:04:24
![](https://img.aspxhome.com/file/2023/2/80072_0s.png)
C#中读写INI文件的方法例子
2022-10-21 23:14:48
Java语法基础之运算符学习笔记分享
2021-12-18 02:13:17
![](https://img.aspxhome.com/file/2023/6/71866_0s.png)
Spring Cloud中FeignClient实现文件上传功能
2023-06-23 07:57:09
Android Flutter使用本地数据库编写备忘录应用
2023-09-15 17:24:09
![](https://img.aspxhome.com/file/2023/6/109226_0s.webp)
java两个integer数据判断相等用==还是equals
2021-06-14 00:46:52
Java流程控制之选择结构
2021-10-24 08:12:50
![](https://img.aspxhome.com/file/2023/4/67464_0s.jpg)
Spring boot 集成Dubbox的方法示例
2023-09-22 23:49:04
给c#添加SetTimeout和SetInterval函数
2021-07-02 00:58:08
![](https://img.aspxhome.com/file/2023/7/77237_0s.png)
Java实现AWT四大事件的详细过程
2023-11-28 18:39:52
![](https://img.aspxhome.com/file/2023/6/60076_0s.png)
Android 实现签到足迹功能
2023-06-21 15:16:24
![](https://img.aspxhome.com/file/2023/3/83543_0s.jpg)
彻底搞懂Java多线程(一)
2023-08-02 10:42:30
![](https://img.aspxhome.com/file/2023/2/71632_0s.png)
Spark Streaming算子开发实例
2023-03-17 02:28:41
![](https://img.aspxhome.com/file/2023/8/80928_0s.jpg)
spring boot入门之诞生背景及优势影响
2021-09-16 06:31:57
![](https://img.aspxhome.com/file/2023/6/69356_0s.png)
java map转Multipart/form-data类型body实例
2023-04-19 13:16:18
Java使用JDBC实现Oracle用户认证的方法详解
2022-10-06 08:59:36