AI 助理
备案控制台
开发者社区 数据库 文章 正文

二叉树的遍历算法

2023-07-27 79
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二叉树的遍历算法

公众号merlinsea


  • 树的介绍
  • 树是一种非线性的数据结构，即树从一个节点出发可能有多个后继节点。
  • 树的基本术语
  • 节点： A、B、C等元素都是节点，节点不仅包含了数据元素，还包含了指向子树的分支。
  • 节点的度：节点拥有的子树的个数或者分支的个数，比如节点A有三个子树，因此节点A的度为3，节点B有两个子树，因此节点B的度是2
  • 树的度：树中各个节点中度的最大值定义为整颗树的度。比如下面这棵树的度是3
  • 叶子节点：指的是没有子树的节点叫做树的叶子节点，比如下图中的K、L、F、G、M、I、J
  • 内部节点： 指的是除叶子节点意外的其他节点叫内部节点，比如下图中的A、B、C、D、E、H
  • 孩子节点：某一节点的子树称之为改节点的孩子节点，比如A节点的孩子节点是B、C、D
  • 双亲节点：与孩子节点向电影院的节点是双亲节点，比如B节点的双亲是A
  • 兄弟节点：统一节点的孩子节点之间称之为兄弟节点，比如B节点的兄弟节点是C和D
  • 树的高度：从根节点开始所能到达叶子节点中距离最长路径长度称之为树的高度，比如下图的树高是4


640.png


  • 二叉树的定义
  • 每个节点最多只能有两个孩子节点，即二叉树中节点的度只可以为0，1，2
  • 子树有左右之分，不能颠倒，分别称之为左孩子和右孩子。
  • 特殊的二叉树
  • 满二叉树：如果二叉树所有的内部节点都有左右孩子节点，并且所有的孩子节点都集中在同一层中，这样的二叉树称之为满二叉树。
  • 完全二叉树：从上到下，从左到右紧密的排布，不跳跃任何一个位置的二叉树就是完全二叉，比如下图中去掉G节点的右边的树就是一颗完全二叉树，满二叉树是一种特殊的完全二叉树。

640.png


  • 树的顺序存储结构
  • 特点：要求是一颗完全二叉树或者把一颗普通的二叉树补齐虚拟节点保证补齐以后是一颗完全二叉树，然后采用数组的方式进行存储。


640.png


  • 二叉树的链式存储

640.png


public class BTNode {
    public int val;
    public String info;
    public BTNode left;
    public BTNode right;
    public BTNode(){
        val = 0;
        info = "";
        left = right = null;
    }
    public BTNode(int val,String info){
        this.val = val;
        this.info = info;
    }
    @Override
    public String toString() {
        return "BTNode{" +
                "val=" + val +
                ", info='" + info + '\'' +
                '}';
    }
}


  • 二叉树的先序遍历算法(链式存储)
  • 先序遍历的遍历顺序是先访问根节点，然后访问左子树，最后访问右子树的过程。
  • 遍历结果： A，B，D，C，E，F

640.png


  • 先序遍历递归版本代码实现


public class Main {
    public static void main(String[] args) {
        BTNode root = create();
        preOrder(root);
    }
    public static void preOrder(BTNode root){
        if(root == null){
            return;
        }
        System.out.println(root);
        //递归调用左边
        preOrder(root.left);
        //递归调用右边
        preOrder(root.right);
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}
  • 先序遍历非递归版本代码实现
  • 当我们访问到父节点的时候，其实我们在这个时候同时遇见了父节点的左孩子和右孩子，但先序遍历要求先处理了左孩子，再处理右孩子，因此此时我们应该先将右孩子入栈，等访问玩左孩子以后，通过出栈操作可以访问右孩子。


public class Main2 {
    public static void main(String[] args) {
        BTNode root = create();
        preOrderNoCur(root);
    }
    public static void preOrderNoCur(BTNode root){
        if(root == null){
            return;
        }
        Stack<BTNode> stack = new Stack<>();
        //初始化
        stack.push(root);
        //遍历
        while(!stack.empty()){
            BTNode p = stack.pop();
            System.out.println(p);
            if(p.right!=null){
                stack.push(p.right);
            }
            if(p.left!=null){
                stack.push(p.left);
            }
        }
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}


  • 二叉树的中序遍历算法(链式存储)
  • 中序遍历的遍历顺序是先访问左子树，然后访问根，最后访问右子树的过程。
  • 遍历结果：D、B、A、E、C、F

640.png

  • 中序遍历递归版本代码实现


public class Main {
    public static void main(String[] args) {
        BTNode root = create();
        inOrder(root);
    }
    public static void inOrder(BTNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root);
        inOrder(root.right);
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}


  • 中序遍历非递归版本代码实现
  • 当我们遇见A节点的时候，我们需要先处理A.left，处理完以后再处理A，因此A需要夏安入栈
  • 递归->非递归 ： 核心点是当前我们遇见了A，但不能立即处理A，需要先处理A.left再处理A，因此栈具有记忆性特征。

640.png

public class Main2 {
    public static void main(String[] args) {
        BTNode root = create();
        inOrderNoCur(root);
    }
    public static void inOrderNoCur(BTNode root){
        if(root == null){
            return;
        }
        Stack<BTNode> stack = new Stack<>();
        BTNode p = root;
        while(p!=null || !stack.empty()){
            if(p!=null){
                stack.push(p);
                p = p.left;
            }else{
                p = stack.pop();
                System.out.println(p);
                p = p.right;
            }
        }
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}


  • 二叉树的后序遍历算法(链式存储)
  • 后序遍历的遍历顺序是先访问左子树，然后访问右子树，最后访问根的过程。
  • 遍历结果：D、B、E、F、C、A

640.png


  • 后序遍历递归版本代码实现


public class Main {
    public static void main(String[] args) {
        BTNode root = create();
        postOrder(root);
    }
    public static void postOrder(BTNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root);
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}


  • 后序遍历非递归版本代码实现


public class Main2 {
    public static void main(String[] args) {
        BTNode root = create();
        postOrderNoCur(root);
    }
    public static void postOrderNoCur(BTNode root){
        if(root == null){
            return;
        }
        Stack<BTNode> stack = new Stack<>();
        BTNode p = root;
        //最近一次访问的节点
        BTNode lastVisitedNode = null;
        while(p!=null || !stack.empty()){
            if(p!=null){
                stack.push(p);
                p = p.left;
            }else{
               p = stack.peek();
               if(p.right==null || lastVisitedNode == p.right){
                   stack.pop();
                   //说明是从右子树往回走
                   System.out.println(p);
                   //标记最近访问的节点
                   lastVisitedNode = p;
                   // p=null是 为了继续往回走
                   p = null;
               }else{
                   //说明是从左子树往回走
                   p = p.right;
               }
            }
        }
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}


  • 总结以上三种遍历算法的路程流转图
  • 在二叉树遍历的过程中，不论是先序遍历，中序遍历还是后序遍历，均按照这个流程来进行。
  • 第1次遇见就输出，则是先序遍历；
  • 第2次遇见就输出，则是中序遍历；
  • 第3次遇见就输出，则是后序遍历；

640.png


  • 二叉树的层序遍历（链式存储）
  • 层序遍历，顾名思义就是按照二叉树的层次结构一层一层的访问。
  • 下面这个二叉树的层序遍历访问结果是：A、B、C、D、E、F


640.png


  • 层序遍历代码实现


public class Main {
    public static void main(String[] args) {
        BTNode root = create();
        layerOrder(root);
    }
    public static void layerOrder(BTNode root){
        if(root == null){
            return;
        }
        Queue<BTNode> queue = new LinkedList<>();
        //队列初始化
        queue.offer(root);
        //层序遍历
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            System.out.println(cur);
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    public static BTNode create(){
        BTNode a = new BTNode(0,"A");
        BTNode b = new BTNode(1,"B");
        BTNode c = new BTNode(2,"C");
        BTNode d = new BTNode(3,"D");
        BTNode e = new BTNode(4,"E");
        BTNode f = new BTNode(5,"F");
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        return a;
    }
}


文章标签：
数据库管理
算法
存储
关键词：
遍历算法
二叉树遍历算法
二叉树算法
梁同学golang算法
目录
相关文章
光明顶阳顶天
|
8天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码，实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
光明顶阳顶天
26 8
dufadayang
|
11天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率？
选择合适的遍历算法，如按层次遍历树时使用广度优先搜索（BFS），中序遍历二叉搜索树以获得有序序列。优化数据结构，如使用线索二叉树减少空指针判断，自定义节点类增加辅助信息。利用递归与非递归的特点，避免栈溢出问题。多线程并行遍历提高速度，注意线程安全。缓存中间结果，避免重复计算。预先计算并存储信息，提高遍历效率。综合运用这些方法，提高二叉树遍历算法的效率。
dufadayang
32 5
dufadayang
|
11天前
|
算法
树的遍历算法有哪些？
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题；广度优先搜索则在图的最短路径、层次相关的问题中较为常用；而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
dufadayang
20 2
mao29955
|
14天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些？
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法，在许多领域都有着不可或缺的应用，它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展，二叉树遍历算法也在不断地被优化和扩展，以适应新的应用场景和需求。
mao29955
24 0
java冯坚持
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
20 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
1月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
21 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
努力学习的小廉
|
1月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
努力学习的小廉
14 0
【二叉树】—— 算法题
java冯坚持
|
1月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
24 0
半截诗
|
3月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称，即左右子树是否对称.
半截诗
27 0
简简单单做算法
|
26天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中，通过游戏理论优化动态频谱访问，提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本：Matlab 2022a。完整代码包含详细中文注释和操作视频。
简简单单做算法
40 2

热门文章

最新文章

  • 1
    泛型KMP算法
  • 2
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 3
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 4
    算法学习之顺序结构
  • 5
    【算法】算法之美—Fire Net
  • 6
    Node.js使用jsrsasign实现SHA256withRSA加密算法
  • 7
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 8
    字符串相似度算法 递归与动态规划求解分析
  • 9
    【算法研究】Bresenham画线算法
  • 10
    算法导论第十四章 数据结构的扩张
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    98
  • 2
    【redis源码学习】持久化机制，java程序员面试算法宝典pdf
    77
  • 3
    对标腾讯T9架构师的 Android 面试题新鲜出炉，算法真的太重要了
    52
  • 4
    【机器学习】K-means算法与PCA算法之间有什么联系？
    265
  • 5
    【机器学习】维度灾难问题会如何影响K-means算法？
    299
  • 6
    【数据结构与算法 11，高并发系统基础篇
    41
  • 7
    sass 公用10个mixins代码块，算法太TM重要了，前端开发要求
    46
  • 8
    前端开发者必知的缓存淘汰策略：LRU算法解析与实践
    203
  • 9
    2024最新Android算法相关面试大全，请查收
    37
  • 10
    【机器学习】聚类算法中，如何判断数据是否被“充分”地聚类，以便算法产生有意义的结果？
    138

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云OSS设置跨域访问