数据结构与算法—二叉树的层序、前序中序后序(递归、非递归)遍历

简介: 层序遍历。听名字也知道是按层遍历。我们知道一个节点有左右节点。而每一层一层的遍历都和左右节点有着很大的关系。也就是我们选用的数据结构不能一股脑的往一个方向钻,而左右应该均衡考虑。这样我们就选用队列来实现。

前言



  • 前面介绍了二叉排序树的构造和基本方法的实现。但是排序遍历也是比较重要的一环。所以笔者将前中后序.和层序遍历梳理一遍。
  • 了解树的遍历,需要具有的只是储备有队列,递归,和栈。这里笔者都有进行过详细介绍,可以关注笔者数据结构与算法专栏。持续分享,共同学习。


层序遍历



20190819181114634.png


层序遍历。听名字也知道是按层遍历。我们知道一个节点有左右节点。而每一层一层的遍历都和左右节点有着很大的关系。也就是我们选用的数据结构不能一股脑的往一个方向钻,而左右应该均衡考虑。这样我们就选用队列来实现


  • 对于队列,现进先出。从根节点的节点push到队列,那么队列中先出来的顺序是第二层的左右(假设有)。第二层每个执行的时候添加到队列,那么添加的所有节点都在第二层后面
  • 同理,假设开始pop遍历第n层的节点,每个节点会push左右两个节点进去。但是队列先进先出。它会放到队尾(下一层)。直到第n层的最后一个pop出来,第n+1层的还在队列中整齐排着。这就达到一个层序的效果。


实现的代码也很容易理解:


public void cengxu(node t) {//层序遍历
  Queue<node> q1 = new ArrayDeque<node>();
  if (t == null)
    return;
  if (t != null) {
    q1.add(t);
  }
  while (!q1.isEmpty()) {
    node t1 = q1.poll();
    if (t1.left != null)
      q1.add(t1.left);
    if (t1.right != null)
      q1.add(t1.right);
    System.out.print(t1.value + " ");
  }
  System.out.println();
}


前中后序遍历(递归)



其实这种就是一个类似dfs的思想。用递归实现。前面有很详细的介绍递归算法。我们采用的三序遍历是采用同一个递归。并且大家也都直到递归是一个有来有回的过程。三序遍历只是利用了递归中的来回过程中不同片段截取输出,而达到前(中、后序遍历的结果)。


前序递归


前序的规则就是根结点 ---> 左子树 ---> 右子树.我们在调用递归前进行节点操作。对于前序,就是先访问(输出)该节点。而递归左,递归右侧,会优先递归左侧。直到没有左节点。才会停止。访问次序大致为:


20190820000853382.png


public void qianxu(node t)// 前序递归 前序遍历:根结点 ---> 左子树 ---> 右子树
{
  if (t != null) {
    System.out.print(t.value + " ");// 当前节点
    qianxu(t.left);
    qianxu(t.right);
  }
}


中序递归


有了前序的经验,我们就很好利用递归实现中序遍历。中序遍历的规则是:左子树---> 根结点 ---> 右子树。所以我们访问节点的顺序需要变。

  • 我们直到递归是来回的过程,对于恰好有两个子节点(子节点无节点)的节点来说。只需要访问一次左节点,访问根,访问右节点。即可。
  • 而如果两侧有节点来说。每个节点都要满足中序遍历的规则。我们从根先访问左节点。到了左节点这儿左节点又变成一颗子树也要满足中序遍历要求。所以就要先访问左节点的左节点(如果存在)。那么如果你这样想,规则虽然懂了。但是也太复杂了。那么我们借助递归。因为它的子问题和根节点的问题一致,只是范围减小了。所以我们使用递归思想来解决。
  • 那么递归的逻辑为:考虑特殊情况(特殊就直接访问)不进行递归否则递归的访问左子树(让左子树执行相同函数,特殊就停止递归输出,不特殊就一直找下去直到最左侧节点。)——>输出该节点—>递归的访问右子树.


代码为:


public void zhongxu(node t)// 中序遍历 中序遍历:左子树---> 根结点 ---> 右子树
{
  if (t != null) {
    zhongxu(t.left);
    System.out.print(t.value + " ");// 访问完左节点访问当前节点
    zhongxu(t.right);
  }
}


后序递归


同理,有了前面的分析,后续就是左子树 ---> 右子树 ---> 根结点


public void houxu(node t)// 后序遍历 后序遍历:左子树 ---> 右子树 ---> 根结点
{
  if (t != null) {
    houxu(t.left);
    houxu(t.right);
    System.out.print(t.value + " "); // 访问玩左右访问当前节点
  }
}


非递归前序



法一(技巧)


  • 非递归的前序。我们利用栈的性质替代递归,因为递归有时候在效率方面不是令人满意的。

利用栈,我们直到栈的顺序为现金先出。那么顺序如何添加?递归是左递归,右递归。但是利用栈要相反,因为如果左进栈、右进栈会出现以下后果:


20190820123939564.png


所以,我们要利用递归的思路,需要先放右节点进栈,再放左节点进栈,这个下次·再取节点取到左节点·,这个节点再右节点进栈,左节点进栈。然后循环一直到最后会一直优先取到左节点。达到和递归顺序相仿效果。


20190820125033981.png


每pop完添加右左节点直接输出(访问)即可完成前序非递归遍历。


public void qianxu3(node t)// 非递归前序 栈 先左后右  t一般为root
{
  Stack<node> q1 = new Stack<node>();
  if (t == null)
    return;
  if (t != null) {
    q1.push(t);
  }
  while (!q1.empty()) {
    node t1 = q1.pop();
    if (t1.right != null) {
      q1.push(t1.right);
    }
    if (t1.left != null) {
      q1.push(t1.left);
    }
    System.out.print(t1.value + " ");
  }
}


法二(传统)


方法二和非递归中序遍历的方法类似,只不过需要修改输出时间,在进栈时候输入访问节点即可。具体参考中序遍历分析


public void qianxu2(node t) {
    Stack<node> q1 = new Stack(); 
    while(!q1.isEmpty()||t!=null)
    {
      if (t!=null) {
        System.out.print(t.value+" ");
        q1.push(t);       
        t=t.left;
      }
      else {
        t=q1.pop();
        t=t.right;
      }
    }
  }


非递归中序



非递归中序和前序有所区别。

我们直到中序排列的顺序是:左节点,根节点,右节点。那么我们在经过根节点的前面节点 不能释放, 因为后面还需要用到它。所以要用栈先储存


它的规则大致为

  • 依次存入左节点所有点,直到最左侧在栈顶。
  • 开始抛出栈顶并访问。(例如第一个抛出2)。如果有右节点。那么将右节点加入栈中然后右节点一致左下遍历直到尾部。(这里5和7没有左节点,所以不加)但是如果抛出15。右节点加入23.再找23的左侧节点加入栈顶。就这样循环下去直到栈为空


可行性分析:中序是左—中—右的顺序。访问完左侧。当抛出当前点的时候说明左侧已经访问完(或者自己就是左侧),那么需要首先访问当前点的右侧。那么这个右节点把它当成根节点重复相同操作(因为右节点要满足先左再右的顺序)。这样其实就是模拟了一个递归的过程,需要自己思考。


20190820183037577.png


实现代码1:


public void zhongxu2(node t) {
  Stack<node> q1 = new Stack(); 
  while(!q1.isEmpty()||t!=null)
  {
    if (t!=null) {
      q1.push(t);
      t=t.left;
    }
    else {
      t=q1.pop();
      System.out.print(t.value+" ");
      t=t.right;
    }
  }
}


实现代码2:(个人首次写的)


public void zhongxu3(node t)// 先储藏所有左侧点,抛出一个点,访问该点右节点,对右节点在储存所有子左节点
{
  Stack<node> q1 = new Stack();
  if (t == null)
    return;
  if (t != null) {
    q1.push(t);
  }
  node t1 = q1.peek();// 不能抛出,要先存最左侧
  while (t1.left != null) {
    t1 = t1.left;
    q1.push(t1);
  }
  while (!q1.isEmpty()) {
    node t2 = q1.pop();
    System.out.print(t2.value + " ");
    if (t2.right != null) {
      t2 = t2.right;
      q1.push(t2);
      while (t2.left != null) {
        t2 = t2.left;
        q1.push(t2);
      }
    }
  }
}


非递归后序※



非递归后序遍历有两种方法

一种方法是利用和前面中序、前序第二种方法类似的方法进入压栈出栈,但是要借助额外的标记次数,一个节点访问第二次才能输出。(这个访问第一次是入栈,第二次是子树解决完毕自己即将出栈(先不出栈))。


法1(传统方法)


在前面的前序和中序先到最左侧压入栈的时候,两种顺序依次是


  • 前序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈——>右孩子入出——>右出栈 在入栈时候操作即可前序
  • 中序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈 ——>右孩子入出——>右出栈按照出栈顺序即可完成中序


而在后序遍历中:它有这样的规则:


  • 入栈,第一次访问
  • 即将出栈。第二次访问,
  • 如果有右孩子,先不出栈把右孩子压入栈第一次访问,如果没右孩子。访问从栈中弹出。
  • 循环重复,直到栈为空


20190821185244847.png


实现代码为(用map记录节点出现次数):


public void houxu2(node t) {
  Stack<node> q1 = new Stack(); 
  Map<Integer,Integer >map=new HashMap<>();
  while(!q1.isEmpty()||t!=null)
  {
    if (t!=null) {
      q1.push(t);
      map.put(t.value, 1); //t.value标记这个值节点出现的次数
      t=t.left;
    }
    else {
      t=q1.peek();
      if(map.get(t.value)==2) {//第二次访问,抛出
        q1.pop();
        System.out.print(t.value+" ");
        t=null;//需要往上走
      }
      else {
        map.put(t.value, 2);
        t=t.right;
      }
    }
  }
}


法2(双栈):


另一种方法是借助双栈进行处理。我们曾在前序方法一借助一个栈右压,左压。持续让达到一个前序遍历的效果。但是这个方法很难实现后续。


分析相同方法,如果我们先压左,再压右,那么我们获得的顺序将是和前序完全相反的顺序(顺序为中间,右侧,左侧倒过来刚好是左侧、右侧、中间的后续)对称看起来的前序。即用另一个栈将序列进行反转顺序


20190821131644294.png


如果再这个过程,我们利用另一个栈进行储存,将它的首次入栈用一个栈存入,相当于起到一个反转的作用


20190821132255583.png


实现代码为:


public void houxu3(node t)// q1和q2 q1要先右后左,先遍历右侧,q1先装右侧就把右侧放到前面,左侧放在上面(栈顶)
{
  Stack<node> q1 = new Stack();
  Stack<node> q2 = new Stack();
  if (t == null)
    return;
  if (t != null) {
    q1.push(t);
  }
  while (!q1.isEmpty()) {
    node t1 = q1.pop();
    q2.push(t1);
    if (t1.left != null) {
      q1.push(t1.left);
    }
    if (t1.right != null) {
      q1.push(t1.right);
    }
  }
  while (!q2.isEmpty()) {
    node t1 = q2.pop();
    System.out.print(t1.value + " ");
  }
}


总结



测试结果:


20190822120124509.png


这部分内容比较多,也可能比较杂,希望大家好好吸收,也可能笔者写的大意或者错误。还请大佬指正。!


  • 另外,完整代码还请关注公众号(bigsai)。笔者认真更新数据结构与算法。有兴趣可以关注一波学一起学习。回复数据结构或者爬虫有精心准备学习资料赠送。


目录
相关文章
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
22 1
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
24 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
28 0
|
2月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
45 0
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
84 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
33 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
22 0
数据结构与算法学习十四:常用排序算法总结和对比
|
2月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
37 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题