二叉树遍历(五-最终篇)

简介: 二叉树遍历(五-最终篇)

前言


啦啦啦,小嘟又和大家见面啦,今天小嘟要和大家聊得话题是二叉树三种遍历方式在代码方面的异同。

涉及的对象:二叉树

涉及的内容: (1)前序遍历 (2)中序遍历 (3)后序遍历(4)如何形象的理解遍历方式

涉及的代码:递归代码和迭代代码

重点:找到一种框架适合这三种遍历方式

注:文章首发在掘金,都是自己的账号,不是抄袭

正文

  • 首先我们将下边这个二叉树的三种遍历结果写出来:


前序遍历:[1,2,4,5,3,6]


中序遍历:[4,2,5,1,3,6]


后序遍历:[4,5,2,6,3,1]


注:讲几个很形象的例子,你就能很快的手写出这三种遍历顺序(这里的例子借鉴的是一篇很nice的博客,感觉很适合小白,原文链接小嘟就放在底部喽,需要的读者可以去看看,这个博主比小嘟厉害多了

1.前序遍历

  • 前序遍历,你可以理解成从根节点出发,以逆时针方向前进,将所有结点都遍历一遍


前序遍历递归代码

var preorderTraversal = function(root) {
      let res = [];//最后返回的数组,存储的是遍历的序列
      //这里用到了es6中的箭头函数
      const traversal = (root01)=>{  //如果当前结点为null,
          if(root01 == null) return ;//说明这条路径走到尽头了,需要重新找路
          res.push(root01.val);     //将遇到的打印,这里是存储哦 
          traversal(root01.left);   //找左孩子
          traversal(root01.right);  //找右孩子
      }
      traversal(root);
      return res;//返回值
};



小嘟稍微解释一下,看着代码,我们知道,只要遇到元素,就会将它打印(这里是存储),然后进入自己的左子树,一直递归调用下去,等左子树为null了,递归开始一层一层的往上返回,每返回一层,然后接着进入自己的右子树,进入右子树,也是先进入右子树中的左子树,以此类推,等所有的都找完了,递归函数的层级减为1(此时我们可以理解成,我们是从根节点出去的,这个时候又回到根节点啦)。此处我们验证了上边的遍历顺序是正确的,但是,这只是个思想,不能认为遍历顺序一定是这样的,在迭代代码中,就没有9、10这两步。

2.中序遍历

  • 中序遍历,可以这样思考,将所有结点垂直投影在底部,例如,我们建立一个二维坐标系,横轴为x,纵轴为y,将上边的图搬到该坐标系上,在x轴上得投影就是中序遍历的结果,这个应该比一个一个数快的多啦。


  • 看图是不是很直观呢?嘿嘿嘿,学会就行,小嘟很是希望读者看一眼就会,加油!!!
  • 中序遍历递归代码
var inorderTraversal = function(root) {
       let res = [];//要返回的数组
       const  traversal = (root01)=>{//es6中的箭头函数
            if(root01 == null) return ;
            traversal(root01.left);
            res.push(root01.val);
            traversal(root01.right);
        }
        traversal(root);
        return res;
 };
  • 中序遍历顺序基本和前序遍历差不多,不同点是打印的位置放在了中间,这也是为什么将这种遍历方式称为中序遍历。
  • 3.后序遍历


后序遍历的话你可以把这个理解成是一串葡萄,并且我们规定每次摘葡萄只能摘一颗,不能贪心,而且规定从左往右(也就是先遍历左子树再遍历右子树)摘葡萄。现在看下图的摘葡萄过程,是不是觉得后序遍历其实也就是那一回事


后序遍历递归代码

var postorderTraversal = function(root) {
  let res = [];//要返回的数组
  const traversal = (root01)=>{
      if(root01 == null) return;//找到尽头,需要另换路
      traversal(root01.left);//遍历左子树
      traversal(root01.right);//遍历右子树
      res.push(root01.val);//左右子树遍历结束就只剩中间喽!
  }
  traversal(root);
  return res;
};


  • 现在看递归代码,你会发现,它们三者的代码竟然如此的相似,小嘟我都不知所错了,心里开心的想着:那我要是会了一种,那另外两种不也就拿捏勒,嘿嘿嘿。
  • 4.递归代码总结篇


综上知,我们可以发现三者的递归代码相似程度非常高,难怪别人问的时候只问一次(另外两个很好推啊)。


小嘟来说说代码之间的差异


小嘟自信的说:(1)打印的位置是不一样的 ,一个在最前边,一个在中间,一个在最后。

(2)它们的递归调用函数的顺序是一样的(这个请读者画一下,自己也画了一下,不画也可以,你看代码,除了push位置不同其他的都一样)。

小嘟楠楠的说:然后也就没什么了。现在来一个框架,以后直接用就可以啦!

var postorderTraversal = function(root) {
   let res = [];//要返回的数组
   const traversal = (root01)=>{
       if(root01 == null) return;//找到尽头,需要另换路
       //@key1处
       traversal(root01.left);//遍历左子树
       //@key2处
       traversal(root01.right);//遍历右子树
       //@key3处
   }
   traversal(root);
   return res;
 };
  • 前序遍历:在@key1处编写打印或者存储代码
  • 中序遍历:在@key2处编写打印或者存储代码
  • 后序遍历:在@key3处编写打印或者存储代码
  • 5.迭代代码总结篇

前序遍历

var preorderTraversal = function(root) {
      let res = [];//最后返回的数组,存储的是遍历的序列
      let stack = [];//循环过程中遇到的结点信息
      while(root || stack.length){
          while(root){
              res.push(root.val); //将遇到的打印,这里是存储哦             
              stack.push(root);   // 这里你可以理解成,该结点还要记着怎样找到
                                  // 自己的右孩子。
              root = root.left;   //找左孩子
          }
          let node = stack.pop(); //找不到左孩子了,那就要找该结点的右孩子啦
          root = node.right;      //找右孩子
      }
      return res;
};

中序遍历

var inorderTraversal = function(root) {
   let res  = [];//最后要返回的数组
   let stack = [];//我们用来存储遍历过程中遇到的元素
   //root == null 并且 stack.length == 0(循环退出)    
   while(root||stack.length){
        while(root){//当前元素存在就循环
           stack.push(root);//把当前元素入栈,不是入的值,而是当前的整个元素
           root = root.left;//继续找它的左孩子
        }
        //该元素没有左孩子,那么我们就应该打印该元素
        let node  = stack.pop();//返回该元素并出栈
        res.push(node.val);//将该元素的值压入要返回的栈里边
        root = node.right;//遍历该元素的右孩子
                            //因为左边和中间(父结点)已经遍历过了
   }
   return res;//返回最终的结果
};

后序遍历

var postorderTraversal = function(root) {
   let res = [];//最后要返回的数组
   let stack = [];//遍历过程中遇到的元素结点
   while(root || stack.length){
       while(root){
           res.unshift(root.val);//这个是数组的一个方法
                                 //可以理解成头插法,往首部插入
           stack.push(root);
           root = root.right;
       }
       let node  = stack.pop();
       root = node.left;
   }
   return res;
}; 

它们之间的差异小嘟在之前的几篇文章中都一一讲过了,读者迷惑的话欢迎阅读。嘿嘿嘿(小嘟会把链接放在文章的最下边),现在直接上框架

var preorderTraversal = function(root) {
      let res = [];//最后返回的数组,存储的是遍历的序列
      let stack = [];//循环过程中遇到的结点信息
      while(root || stack.length){
          while(root){
              //@key1处、@key2处         
              stack.push(root);   // 这里你可以理解成,该结点还要记着怎样找到
                                  // 自己的右孩子。
              root = root.left;   //找左孩子
          }
          let node = stack.pop(); //找不到左孩子了,那就要找该结点的右孩子啦
          @key3处
          root = node.right;      //找右孩子
      }
      return res;
};

前序遍历:在@key1处编写打印或者存储代码


中序遍历:在@key3处编写打印或者存储代码


后序遍历:在@key2处编写存储代码


注:

(1).这里不能直接打印哦,因为我们是倒着找的结点

(2).需要改代码,第一处,root = root.left改为root = root.right

(3).第二处,root = node.right 改为 root = node.left

结尾


到今天为止,关于二叉树的三种遍历方法就完美收官了,谢谢各位读者阅读。

文章字数较多,小嘟难免会手抖(嘿嘿嘿),so,欢迎各位批评指正。

创作不易,小嘟这个周末把时间都花在上边了(呜呜呜),周日晚上23:32才完成,所以如果读者还觉得不错的话,可以给小嘟点赞、评论、关注支持一波,小嘟会继续努力下去的。

若读者想让小嘟写某一方面的内容,欢迎评论,小嘟会尽力去做的(要是实在不会,那小嘟只能认错啦)。

最后,祝大家看完该文章有所收获,我们下期再见。

溜啦溜啦...

目录
打赏
0
0
0
0
4
分享
相关文章
Crawl4AI:为大语言模型打造的开源网页数据采集工具
随着大语言模型(LLMs)的快速发展,高质量数据成为智能系统的关键基础。**Crawl4AI**是一款专为LLMs设计的开源网页爬取工具,可高效提取并结构化处理网页数据,突破传统API限制,支持JSON、HTML或Markdown等格式输出。
316 3
Crawl4AI:为大语言模型打造的开源网页数据采集工具
Manus爆火,我发现平替开源项目OpenManus带你玩转AI智能体开发,无需邀请码!
在AI技术日新月异的今天,OpenManus像一把打开智能体开发大门的万能钥匙,让每个人都能轻松构建自己的AI助手!
169 0
Manus的技术实现原理浅析与简单复刻
作者参考网络相关信息并加上个人理解,对Manus的技术实现原理进行深入分析,并做了一个简单版本的复刻,欢迎大家在评论区互相交流探讨~
Manus的技术实现原理浅析与简单复刻
探索Python中的异步编程:从asyncio到Trio
本文将带你深入Python异步编程的心脏地带,从asyncio的基本概念到Trio的高级特性,我们将一起揭开Python异步编程的神秘面纱,并探讨它们如何改变我们的编程方式。
FireCrawl:开源 AI 网络爬虫工具,自动爬取网站及子页面内容,预处理为结构化数据
FireCrawl 是一款开源的 AI 网络爬虫工具,专为处理动态网页内容、自动爬取网站及子页面而设计,支持多种数据提取和输出格式。
1911 19
FireCrawl:开源 AI 网络爬虫工具,自动爬取网站及子页面内容,预处理为结构化数据
深入浅出Python沙箱越狱:原理、方法与防范
今天我们来聊一个有趣的话题 - Python沙箱越狱。在我们开始之前,先来搞清楚什么是Python沙箱吧。 简单来,Python沙箱就像是一个虚拟的"游乐场"。在这个游乐场里,你可以尽情地玩耍(运行Python代码),但是不能伤害到外面的世界(不能访问系统资源或执行危险操作)。这个"游乐场"有围栏(限制),有规则(安全策略),目的就是让你玩得开心,又不会搞出什么大乱子。
|
12月前
|
Python并发编程新纪元:异步编程如何重塑IO与CPU密集型任务的处理方式?
【7月更文挑战第18天】Python异步编程提升IO任务效率,非阻塞模式减少等待时间,优化用户体验。asyncio库与await关键字助力编写非阻塞代码,示例展示异步HTTP请求。CPU密集型任务中,异步编程结合多进程可提升效率。异步编程挑战包括代码复杂性,解决策略包括使用类型提示、异步框架及最佳实践。异步编程重塑任务处理方式,成为现代Python开发的关键。
105 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问