当前位置: 首页 > 编程笔记 >

Java语言实现非递归实现树的前中后序遍历总结

酆奇文
2023-03-14
本文向大家介绍Java语言实现非递归实现树的前中后序遍历总结,包括了Java语言实现非递归实现树的前中后序遍历总结的使用技巧和注意事项,需要的朋友参考一下

前言

三种遍历的递归写法都很好写,所以总结一下非递归写法。

先贴一张图复习一下三种遍历方式就进入正文啦~

【注:本文所有代码实现中树的结点定义如下:

public class Node {
  int val;
  Node left;
  Node right;
  Node parent;
  Node() {}
  Node(int val) {
    this.val = val;
  }
}

1.前序遍历

实现思路:

前序遍历的顺序是:根结点 -> 左孩子 -> 右孩子

借助一个栈结构先将根结点压入栈,然后循环每次取出栈顶元素,直到栈为空。如果当前结点有右孩子就先将右孩子压入栈中,如果当前结点有左孩子就将左孩子压入栈中,这里注意顺序,因为栈的结构是先进后出的,为了保证先遍历到左孩子就应该后压左孩子~

代码实现:

【代码使用直接输出的方式打印中序遍历结果,也可以放入一个list中存储~】

public void preOrder(Node head) {
    System.out.println("pre-order:");
    if(head != null) {
      Stack<Node> stack = new Stack<>();
      stack.push(head);
      while(!stack.isEmpty()) {
        head = stack.pop();
        System.out.print(head.val + " ");
        if (head.right != null)
          stack.push(head.right);
        if (head.left != null)
          stack.push(head.left);
      }
    }
  }

2.中序遍历

实现思路:

中序遍历的顺序:左孩子 -> 根结点 -> 右孩子

借助栈结构,将当前结点的左孩子依次入栈直到没有左孩子了就弹出栈顶元素并打印,如果弹出的结点有右孩子就将右孩子的左边界依次入栈,循环…

比如文章开始的那个图中,先将A,B,D依次入栈,此时栈顶元素是D,弹出并打印,D结点有右孩子,将D的右孩子的左边界依次入栈,压入结点G,结点G没有左孩子所以弹出并打印G,此时栈顶元素是B,循环…直到栈中为空且当前结点为空时遍历结束。

代码实现:

public static void inOrderTraverse(Node head) {
    System.out.println("in-order:");
    if(head != null) {
      Stack<Node> stack = new Stack<>();
      while(!stack.isEmpty() || head != null) {
        if(head != null) {
          // 当前节点不为空, 将自己压进栈并将自己的左孩子作为当前节点(压入左边界)
          stack.push(head);
          head = head.left;
        }else {
          // 当前节点为空(没有左孩子了), 将栈顶元素弹出作为当前节点, 并将当前节点的右孩子压进栈
          head = stack.pop();
          System.out.print(head.val + " ");
          head = head.right;
        }
      }
    }
  }

3.后序遍历

实现思路:

后序遍历的顺序:左孩子 -> 右孩子 -> 根结点

仔细想一下,打印每个结点需要访问根结点三次,先从根结点开始找到左孩子,返回再找到右孩子,再返回到根结点,需要访问根结点三次,直接按照当前顺序进行遍历不知如何下手,那么我们可以换一个角度去考虑。

栈结构是先进后出的,那我们不妨借助一个栈先存储 根结点 -> 右孩子 -> 左孩子 的结果,再将其依次弹出就是后序遍历的顺序了。

那实现 根结点 -> 右孩子 -> 左孩子 的方法就很简单了,回忆一下刚才说的前序遍历的方式,前序遍历是先要左孩子,就后压入左孩子,反之,将前序遍历的逻辑改写为:弹出每个栈顶结点作为当前结点并存储到一个辅助栈中,如果当前结点有左孩子就先压入左孩子,如果有右孩子就后压入右孩子,每次取栈顶弹出到辅助栈中。最后将得到的辅助栈中元素依次弹出得到的就是后序遍历的结果。

代码实现:

public static void posOrderTraverse(Node head) {
    System.out.println("pos-order");
    if(head != null) {
      Stack<Node> stack1 = new Stack<>();
      Stack<Node> stack2 = new Stack<>();   // 辅助栈,存储 根 -> 右 -> 左 的结果
      stack1.push(head);
      while(!stack1.isEmpty()) {
        head = stack1.pop();
        stack2.push(head);
        // 有左孩子就先压入左孩子
        if(head.left != null)
          stack1.push(head.left);
        // 有右孩子就后压入右孩子
        if(head.right != null)
          stack1.push(head.right);
      }
      // 逆序打印 根 -> 右 -> 左 的结果,就是后序遍历的结果
      while(!stack2.isEmpty())
        System.out.print(stack2.pop().val + " ");
    }
  }

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对小牛知识库的支持。如果你想了解更多相关内容请查看下面相关链接

 类似资料:
  • 本文向大家介绍Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】,包括了Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Java实现的二叉树常用操作。分享给大家供大家参考,具体如下: 运行结果: 更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作

  • 本文向大家介绍C++实现二叉树非递归遍历方法实例总结,包括了C++实现二叉树非递归遍历方法实例总结的使用技巧和注意事项,需要的朋友参考一下 一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的。现举一个非递归遍历的方法如下,供大家参考。 具体代码如下: 希望本文所述对大家的C++算法学习有所帮助。

  • 主要内容:递归实现,非递归实现二叉树后序遍历的实现思想是:从根节点出发,依次遍历各节点的左右子树,直到当前节点左右子树遍历完成后,才访问该节点元素。 图 1 二叉树   如图 1 中,对此二叉树进行后序遍历的操作过程为: 从根节点 1 开始,遍历该节点的左子树(以节点 2 为根节点); 遍历节点 2 的左子树(以节点 4 为根节点); 由于节点 4 既没有左子树,也没有右子树,此时访问该节点中的元素 4,并回退到节点 2 ,遍

  • 本文向大家介绍Java递归遍历树形结构的实现代码,包括了Java递归遍历树形结构的实现代码的使用技巧和注意事项,需要的朋友参考一下 废话不多说了,直接给大家贴代码,具体代码如下所示: ps:java实现树的递归遍历(用于实现折叠菜单) 1.核心算法 2.实体类(部门) 以上所述是小编给大家介绍的Java递归遍历树形结构的相关内容,希望对大家有所帮助! 更多精彩内容请关注公众号【Java技术迷】,可

  • 主要内容:递归实现,非递归实现二叉树中序遍历的实现思想是: 访问当前节点的左子树; 访问根节点; 访问当前节点的右子树; 图 1 二叉树   以图  1 为例,采用中序遍历的思想遍历该二叉树的过程为: 访问该二叉树的根节点,找到 1; 遍历节点 1 的左子树,找到节点 2; 遍历节点 2 的左子树,找到节点 4; 由于节点 4 无左孩子,因此找到节点 4,并遍历节点 4 的右子树; 由于节点 4 无右子树,因此节点 2 的左子

  • 主要内容:递归实现,非递归实现二叉树先序遍历的实现思想是: 访问根节点; 访问当前节点的左子树; 若当前节点无左子树,则访问当前节点的右子树; 图 1 二叉树   以图  1 为例,采用先序遍历的思想遍历该二叉树的过程为: 访问该二叉树的根节点,找到 1; 访问节点 1 的左子树,找到节点 2; 访问节点 2 的左子树,找到节点 4; 由于访问节点 4 左子树失败,且也没有右子树,因此以节点 4 为根节点的子树遍历完成。但节点