【数据结构】二叉树(二)遍历

上篇已经了解对二叉树有了大概了解,本篇学习二叉树的前序、中序、后序及层序遍历的递归与非递归共7种遍历方法,快收藏吧~

目录

1、前序遍历

递归方式:

迭代方式: 

2、中序遍历

递归方式:

 迭代方式:

3、后序遍历:

递归方式

迭代方式:

4、层序遍历

递归方式

迭代方式: 


二叉树的前序、中序、后序及层序遍历的递归与非递归遍历方法

遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结 点均做一次且仅做一次访问访问结点所做的操作依赖于具体的应用问题(比如:打印节点内容、节点内容加 1)。 遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算之基础。

二叉树的遍历方法有以下四种 :

  • 先序遍历(根左右)

        首先访问根结点,然后递归地遍历左子树,最后遍历右子树。例如对于二叉树:先序遍历的结果为:1->2->4->8->9->5->10->11->3->6->7。

  • 中序遍历(左根右)

        首先遍历左子树,然后访问根结点,最后遍历右子树。例如对于二叉树:中序遍历的结果为:8->4->9->2->10->5->11->1->6->3->7。

  • 后序遍历(左右根)

        首先遍历左子树,然后遍历右子树,最后访问根结点。例如对于二叉树:后序遍历的结果为:8->9->4->10->11->5->2->6->7->3->1。

  • 层序遍历

   自上而下,自左至右逐层访问树的结点的过程就是层序遍历。      

  它是按广度优先搜索的策略,从根结点出发,依次访问每一层上的节点。这种策略在实际应用中使用较多,如在计算机图形学中用于渲染场景图等。例如对于二叉树:层次遍历的结果为:1->2->3->4->5->6->7->8->9->10->11

下面讲解代码,前序遍历、中序遍历和后序遍历的简单递归方法不附图讲解,主要解释它们的迭代方式及层序遍历


1、前序遍历

递归方式:

定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要首先将 root 节点的值加入答案,然后递归调用 preorder(root.left) 来遍历 root 节点的左子树,最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();preorder(root, res);return res;}public void preorder(TreeNode root, List<Integer> res) {if (root == null) {return;}res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}

复杂度分析

时间复杂度:O(n)其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。

迭代方式: 

迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if(root==null) return res;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode p = stack.pop();res.add(p.val);if(p.right!=null)stack.push(p.right);if(p.left!=null)stack.push(p.left);}return res;}
}

注释: 先将root压栈,进入 while 循环,每循环一次栈顶出栈一次并记录该结点,将其左结点右结点压栈,栈为空退出循坏。

时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度:O(n),为迭代过程中显式栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。


2、中序遍历

递归方式:

定义 inorder(root) 表示当前遍历到 root 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树,然后将 root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}

复杂度分析

时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度:O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别

 迭代方式:

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();res.add(root.val);root = root.right;}return res;}
}

子循环中root遍历到root左子树最深层次过程中,依次将左结点压栈,左结点为空退出子循环,将栈顶元素出栈, root=root.right重新进入大循环既可遍历该树所有结点。

时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度:O(n)。空间复杂度取决于栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。 


3、后序遍历

递归方式

定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树,然后递归调用 postorder(root->right) 来遍历 root 节点的右子树,最后将 root 节点的值加入答案即可,递归终止的条件为碰到空节点。

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();postorder(root, res);return res;}public void postorder(TreeNode root, List<Integer> res) {if (root == null) {return;}postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}

复杂度分析

时间复杂度:O(n),其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。

空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。

迭代方式:

我们也可以用迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码(为了更好的注释,代码放入块引用中)

class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<Integer>();

        if (root == null) {

            return res;

        }

        Stack <TreeNode> stack = new Stack<>();

        TreeNode prev = null;

        while (root != null || !stack.isEmpty()) {

            while (root != null) {

                stack.push(root);

                root = root.left;

            }

            root = stack.peek();//  取栈顶元素

//因为是后序遍历,当前结点有无右结点决定它是否打印

//所以取出栈顶元素,判断有无右结点

         //而打印当前结点情况分为两种,1、该结点无右结点  2、该结点的右结点已遍历

      if (root.right == null || root.right == prev) {

                res.add(root.val);

                stack.pop();

                prev = root;//用prev指向root,表示已被遍历

                root = null;

            } else 

                root = root.right;

        }

        return res;

    }

}

如上图情况,若if条件语句不判断 D.right ( K )是否被上次遍历则会陷入K出栈压栈无限循环中

复杂度分析 

时间复杂度:O(n),其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。

空间复杂度:O(n),为迭代过程中显式栈的开销,平均情况下为 O(logn),最坏情况下树呈现链状,为 O(n)。


4、层序遍历

即逐层地,从左到右访问所有节点。

递归方式

class Solution {List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {order(root,0);return result;}public void order(TreeNode node,int deep){if(node==null)return;deep++;if(result.size()<deep){List<Integer> item=new ArrayList<>();result.add(item);}result.get(deep-1).add(node.val);order(node.left,deep);order(node.right,deep);}
}

在方法void order(TreeNode node,int deep) ,传相应的结点和二维数组下标,设置节点对应位置

加图理解: 

时间复杂度;O(n) 

迭代方式: 

代码设计重点:出栈既遍历。在结点出栈时,同时将不为空的左右结点入栈。进入子循环前,用size记录栈内元素,进入子循环后,依次将栈顶元素弹出,同时将不为空的左右结点入,size--;

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res=new ArrayList<>();if(root==null)return res;Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size=queue.size();List<Integer> list=new ArrayList<>();while(size--!=0){TreeNode top=queue.poll();list.add(top.val);if(top.left!=null)queue.offer(top.left);if(top.right!=null)queue.offer(top.right);}res.add(list);}return res;}
}

时间复杂度;O(n)

二叉树的遍历结束

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/403588.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

XXX【4】策略模式

如上图所示&#xff0c;如果要加入一个新的货币&#xff0c;那么就需要对类中的Calculate函数进行修改&#xff0c;这违背了封闭开放原则。 上图中的方式更加合适&#xff0c;搞一个抽象类&#xff08;方法中可以用多态调用&#xff09;&#xff0c;然后每个货币自己是一个类&a…

每日学习笔记:C++ STL之堆栈容器stack

目录 stack定义 核心接口 stack class声明 stack class定义 用户自定义的Stack Class C11特色的插入元素的新形式 运用实例 stack定义 核心接口 stack class声明 stack class定义 用户自定义的Stack Class C11特色的插入元素的新形式 运用实例

数据结构(邓俊辉)学习笔记】优先级队列 07——堆排序

1.算法 作为完全二叉堆的一个应用&#xff0c;这节来介绍堆排序算法。 是的&#xff0c;谈到优先级队列&#xff0c;我们很自然地就会联想到排序。因为就其功能而言&#xff0c;包括完全二叉堆在内的任何一种优先级队列都天生地具有选取功能&#xff0c;也就是选取其中的最大…

【mkdir rmdir】Centos/Linux mkdir rmdir命令详细介绍

【mkdir & rmdir】Centos/Linux mkdir & rmdir命令详细介绍 简介 mkdir rmdir 简介 mkdir 命令和 rmdir 命令是在 linux 当中比较常用的两个命令&#xff0c;这两个命令前者是创建空目录&#xff0c;后者是删除空目录。rmdir 命令的定位比较尴尬它的功能可以被 rm 命…

“论面向服务架构设计及其应用”写作框架,软考高级,系统架构设计师

论文真题 面向服务架构&#xff08;Service-Oriented Architecture, SOA&#xff09; 是一种应用框架&#xff0c;将日常的业务应用划分为单独的业务功能服务和流程&#xff0c;通过采用良好定义的接口和标准协议将这些服务关联起来。通过实施基于SOA的系统架构&#xff0c;用…

版本更新 《坚持学习计时器》软件V3.1 更新内容:自动实时显出

&#x1f31f; 嗨&#xff0c;我是命运之光&#xff01; &#x1f30d; 2024&#xff0c;每日百字&#xff0c;记录时光&#xff0c;感谢有你一路同行。 &#x1f680; 携手启航&#xff0c;探索未知&#xff0c;激发潜能&#xff0c;每一步都意义非凡。 版本更新 《坚持学习…

海量数据处理商用短链接生成器平台 - 1

第一章 海量数据处理商用短链接生成器平台介绍 第1集 什么是短链接生成器 短链接生成器是一种工具&#xff0c;可以将较长的链接转换成较短的链接。这种工具在许多场景中都很有用&#xff0c;包括营销、社交媒体分享和数据报告等。以下是一些关于短链接生成器的优点和作用&…

ubuntu20.04挂载机械硬盘

环境说明 1.基于清华源地址下载的ubuntu20.04制作的系统盘&#xff0c;然后安装在PC上&#xff08;固态硬盘&#xff09; 2.机械硬盘无法看见 目的 挂载机械硬盘&#xff0c;开机就能自动启动/挂载 参考链接 https://blog.csdn.net/qq_35624642/article/details/137713143…

Socket编程TCP 基础

一.什么是Socket(套接字&#xff09; 定义&#xff1a;就是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。一个套接字就是网络上进程通信的一端&#xff0c;提供了应用层进程利用网络协议交换数据的机制。从所处的地位来讲&#xff0c;套接字上联应用进程&#x…

C:每日一练:单身狗(2.0版本)

前言&#xff1a; 今天在刷题的时候突然看到一道题&#xff0c;疑似一位故题。仔细一看&#xff0c;欸&#xff01;这不是就是单身狗的升级版吗&#xff1f;我想那必须再安排一篇&#xff0c;不过由于本篇文章与上一篇单身狗文章所涉及的知识点基本相同&#xff0c;所以还请大…

政企单位如何选择适合规模的即时通讯软件?

政企单位在不同规模的组织结构中都面临着沟通和协作的挑战。为了提高工作效率和团队协作能力&#xff0c;选择适合规模的即时通讯软件至关重要。本文将为政企单位在选择适合规模的即时通讯软件时提供一些关键要素和指导&#xff0c;同时重点介绍WorkPlus作为一个可以迎合政企单…

谷歌的高级指令有哪些

今天会分享一些组合用法&#xff0c;这样就能节省许多时间可以放在跟进客户上面&#xff08;本文只介绍谷歌的搜索指令&#xff0c;并无推广&#xff09; part one 谷歌常用的搜索引擎指令&#xff1a; 1、Inurl&#xff0c;在网址中 2、Intext&#xff0c;在网页内容中 3、…

tcpdump入门——抓取三次握手数据包

1. 使用docker启动一个tcp应用 参考&#xff1a;https://blog.csdn.net/LONG_Yi_1994/article/details/141175526 2. 获取容器id docker ps |grep gochat 3. 获取容器的 PID 首先&#xff0c;你需要获得容器的进程 ID&#xff08;PID&#xff09;。可以使用 docker inspect…

遥感之常用各种指数总结大全

目前在遥感领域基本各种研究领域都会用到各种各样的指数&#xff0c;如水体指数&#xff0c;植被指数&#xff0c;农业长势指数&#xff0c;盐分指数&#xff0c;云指数&#xff0c;阴影指数&#xff0c;建筑物指数&#xff0c;水质指数&#xff0c;干旱指数等等众多。 本文对上…

【Web】巅峰极客2024 部分题解

目录 EncirclingGame GoldenHornKing php_online admin_Test EncirclingGame 玩赢游戏就行 GoldenHornKing 利用点在传入的app 可以打python内存马 /calc?calc_reqconfig.__init__.__globals__[__builtins__][exec](app.add_api_route("/flag",lambda:__i…

STM32通过I2C硬件读写MPU6050

目录 STM32通过I2C硬件读写MPU6050 1. STM32的I2C外设简介 2. STM32的I2C基本框图 3. STIM32硬件I2C主机发送流程 10位地址与7位地址的区别 7位主机发送的时序流程 7位主机接收的时序流程 4. STM32硬件与软件的波形对比 5. STM32配置硬件I2C外设流程 6. STM32的I2C.h…

Java Web|day6.MyBatis-Plus

MyBatisPlus 定义 mybatis-plus是一款Mybatis增强工具&#xff0c;用于简化开发&#xff0c;提高效率。 核心功能 注解 TableName 注解在类上&#xff0c;指定类和数据库表的映射关系。实体类的类名&#xff08;转成小写后&#xff09;和数据库表名相同时&#xff0c;可以不…

网络协议九 应用层 HTTPS

一 什么是 HTTPS 前面我们看到HTTP 有很多安全问题&#xff0c;因此引出了 对称加密 和 不对称加密。 那么这个对称加密和不对称加密&#xff0c;我们怎么和HTTP结合起来呢&#xff1f;HTTPS 就是弄好的 HTTP 和 加密结合的协议。 通过HTTP加密后的数据&#xff0c;整个传输过…

Fly Catcher:通过监测恶意信号来检测飞机欺骗

Fly Catcher 的开发者 Angelina Tsuboi 是一名飞行员、网络安全研究员和发明家。 她决定着手一个将这三个不同兴趣结合起来的项目&#xff0c;以解决航空雷达系统的一个重大问题。 ADS-B 系统最初用于基本的飞机定位和跟踪&#xff0c;Tsuboi 对该系统的网络安全方面进行了深…

Java语言程序设计——篇十四(1)

&#x1f33f;&#x1f33f;&#x1f33f;跟随博主脚步&#xff0c;从这里开始→博主主页&#x1f33f;&#x1f33f;&#x1f33f; 欢迎大家&#xff1a;这里是我的学习笔记、总结知识的地方&#xff0c;喜欢的话请三连&#xff0c;有问题可以私信&#x1f333;&#x1f333;&…