21、数据结构与算法基础:二叉树的非递归遍历

摘要

二叉树的遍历可以用递归的方式简单实现,但是递归也有其局限性,所以非递归实现是否可行?下面的文章就会告诉答案。递归的局限性是什么?文章中也会给出作者的理解。

二叉树的遍历有 4 种方式,分别是前序遍历、中序遍历、后序遍历和层序遍历,它们的区别如下表:

遍历方法 访问顺序
前序遍历(Preorder Traversal) 根节点、左子树、右子树
中序遍历(Inorder Traversal) 左子树、根节点、右子树
后序遍历(Postorder Traversal) 左子树、右子树、根节点
层序遍历(Level Order Traversal) 从上到下、从左到右依次访问每一个节点

在《数据结构与算法-基础(八)遍历二叉树》中使用递归的方式实现这些遍历(递归方法可以看第八期文章),遍历二叉树使用递归方式实现,在代码上会更加简单明了,同时也不能忽视它的缺点(递归的普遍缺点):

1、 递归是本质是调用自身,那么在时间和空间上需要更多的消耗;
2、 递归思想核心就是把一个问题拆分为多个小问题,多个小问题重叠的部分,就是增加重复计算消耗;
3、 递归实际上是将函数不断地压入栈,那么就会存在栈溢出的情况(递归层级多的情况下);

那么是否有其他的遍历实现方案?本文就是介绍遍历二叉树的另外一个方案,统称为非递归遍历,了解这个方案的好处有:

1、 多增加一个实现方案,在应用场景中实现时,可以多一个选择;
2、 一个方案本质是解决某方面的思考和逻辑,通过这个方案了解和学习它的思维和逻辑,方面在解决问题时多一个思路;

准备

在实现遍历之前,先要确定二叉树的类结构,类中有 root 来作为根节点,size 记录二叉树中的节点(或元素)数量:

public class BinaryTree<E> implements BinaryTreeInfo {
   
     

	protected int size;
	protected Node<E> root;
}

Node 类中有记录父节点、左子节点、右子节点和存放元素变量这 4 个基本属性:

protected static class Node<E> {
   
     
  Node<E> parent;
  Node<E> left;
  Node<E> right;
  E element;
}

前序遍历

前序遍历的顺序是根节点、左子树、右子树。这里用堆栈(stack)的数据结构来实现,大致的逻辑是:

1、 将root赋值给node,然后循环;
2、 当node不是null时,打印node,然后将右子节点压入stack,左子节点赋值给node,进行下一个循环;
3、 当stack是null时,退出循环完成遍历;
4、 当stack不为null,node是null时,就从stack中推出一个node;

代码逻辑中需要注意这几点:

1、 root是null时,不可以遍历;
2、 在循环之前,创建stack;
3、 当右子节点不是null时,才能压入stack;

public void preorderTanversal() {
   
     
  if (root == null) return;
   Node<E> node = root;
   Stack<Node<E>> stack = new Stack<>();
   while (true) {
   
     
     if (node != null) {
   
     

       // 访问 node 节点
      print(node.element)
      // 将右子节点入栈
      if (node.right != null) {
   
     
        stack.push(node.right);
      }
      // 向左走
      node = node.left;
    } else if (stack.isEmpty()) {
   
     
      return;
    } else {
   
      // node 为 null,stack 不为空
      node = stack.pop();
    }
  }
}

中序遍历

中序遍历访问的顺序是左子树、根节点、右子树。中序遍历的逻辑是:

1、 从根节点开始,一直向左遍历,将遍历到的节点一次压入stack中;
2、 从stack中推出node,访问node的元素,然后将右子节点赋值给node;
3、 当stack为null时,完成循环;

写代码时需要特别注意的细节,当 node 为 null 时,不能执行压入 stack 操作,中序遍历相对于前序遍历需要多过几遍代码,帮助更好的理解。

public void inorderTraversal() {
   
     
  if (root == null) return;
   Node<E> node = root;
   Stack<Node<E>> stack = new Stack<>();

   while (true) {
   
     
    if (node != null) {
   
     
      stack.push(node);
      node = node.left;
    } else if (stack.isEmpty()) {
   
     
      return;
    } else {
   
      // node 为 null, stack 不为 null
      // 访问 node 节点
      node = stack.pop();
      print(node.element)
      // 让右节点进行中序遍历
      node = node.right;
    }
  } 
}

后序遍历

后序遍历的访问顺序是左子树、右子树、根节点。大致的代码逻辑是:

1、 定义变量prev记录上次被stack推出的node,将root压入stack,然后开始循环;
2、 查看stack顶部的node,当node不是叶子节点,prev的父节点不是stack的顶部节点时,就分别将node的左右非空子节点压入stack;
3、 如果2中的条件不满足,那么就推出stack的node赋值给prev,并访问node;
4、 结束循环的条件是stack为null;

这里用变量 prev 目的就是保证压入 stack 中的节点能保证左子节点、右子节点、节点的顺序:

public void postorderTraversal() {
   
     
  if (root == null) return;
  // 记录上一次弹出的节点
  Node<E> prev = null;
  Stack<Node<E>> stack = new Stack<>();
  stack.push(root);

   while (!stack.isEmpty()) {
   
     
    Node<E> top = stack.peek(); 
    if (top.isLeaf() ||(prev != null && prev.parent == top)) {
   
     
      prev = stack.pop();
      // 访问节点
      print(prev.element)
    } else {
   
     
      if (top.right != null) {
   
     
        stack.push(top.right);
      }

      if (top.left != null) {
   
     
        stack.push(top.left);
      }
    }
  }

层序遍历

层序遍历的访问顺序是从根节点开始,从上到下,从左到右依次访问节点,这里用队列的数据结构来处理:

1、 将根节点入队到队列中,以队列不为null为循环条件开始遍历;
2、 队列出队node,访问node,并将node的左右非空子节点入队;

public void leverOrderTraversal() {
   
     
  if (root == null) return;
  Queue<Node<E>> queue = new LinkedList<>();

  // 第一节点入队
  queue.offer(root);
  while (!queue.isEmpty()) {
   
     
    Node<E> node = queue.poll();
    // 访问节点
    print(node.element)

    if (node.left != null) {
   
     
      queue.offer(node.left);
    }

    if (node.right != null) {
   
     
      queue.offer(node.right);
    }
  }
}

用队列实现层序遍历的方式是一个非常奇特的点,这样的实现方式值得多看几遍。

总结

  • 二叉树的遍历方式都可以用非递归的方式实现;
  • 使用栈或者队列的方式,核心目的就是保证它的访问顺序,代码中要特别注意循环的条件;
  • 中序遍历和后序遍历是比较难理解,需要多看几遍,层序遍历是非常奇特点切入点,值得多看几遍。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: