二叉树递归和非递归遍历（先序、中序、后序）

2024-09-02 11:48
文章标签 二叉树 中序 遍历 递归 后序 先序

本文主要是介绍二叉树递归和非递归遍历（先序、中序、后序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先简要介绍三种遍历方式的递归实现，再详细介绍三种遍历方式的非递归实现。
这里写图片描述
一、三种遍历方式的递归实现

1、先序遍历——按照“根节点-左孩子-右孩子”的顺序进行访问。

    /** 先序遍历二叉树（递归）*/public void PrintBinaryTreePreRecur(TreeNode<T> root){if (root!=null){System.out.print(root.data);PrintBinaryTreePreRecur(root.left);PrintBinaryTreePreRecur(root.right);}}

2、中序遍历——按照“左孩子-根节点-右孩子”的顺序进行访问。

    /** 中序遍历二叉树（递归）*/public void PrintBinaryTreeMidRecur(TreeNode<T> root){if (root!=null){PrintBinaryTreeMidRecur(root.left);System.out.print(root.data);PrintBinaryTreeMidRecur(root.right);}}

3、后序遍历——按照“左孩子-右孩子-根节点”的顺序进行访问。

    /** 后序遍历二叉树（递归）*/public void PrintBinaryTreeBacRecur(TreeNode<T> root){if (root!=null){PrintBinaryTreeBacRecur(root.left);PrintBinaryTreeBacRecur(root.right);System.out.print(root.data);}}

二、三种遍历方式的非递归实现

为了便于理解，这里以下图的二叉树为例，分析二叉树的三种遍历方式的实现过程。

1、前序遍历的非递归实现

根据先序遍历的顺序，先访问根节点，再访问左子树，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的先序遍历顺序为：ABDECF。非递归的实现思路如下：
对于任一节点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
6）直到当前节点P为NULL并且栈空，遍历结束。

根据以上思路，前序遍历的非递归实现代码如下：

/** 先序遍历二叉树（非递归）* 思路：对于任意节点T，访问这个节点并压入栈中，然后访问节点的左子树，*      遍历完左子树后，取出栈顶的节点T，再先序遍历T的右子树*/public void PrintBinaryTreePreUnrecur(TreeNode<T> root){TreeNode<T> p=root;//p为当前节点LinkedList<TreeNode> stack=new LinkedList<>();//stack中存放的其实就是中间的节点//栈不为空时，或者p不为空时循环while(p!=null || !stack.isEmpty()){//当前节点不为空。访问并压入栈中。并将当前节点赋值为左儿子if (p!=null){stack.push(p);System.out.print(p.data);p=p.left;}//当前节点为空：//  1、当p指向的左儿子时，此时栈顶元素必然是它的父节点//  2、当p指向的右儿子时，此时栈顶元素必然是它的爷爷节点//取出栈顶元素，赋值为rightelse{p=stack.pop();p=p.right;}}}

2、中序遍历的非递归实现
根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的中序遍历顺序为：DBEAFC。非递归的实现思路如下：
对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。

根据以上思路，中序遍历的非递归实现代码如下：

/** 中序遍历二叉树（非递归）** 思路：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，*       出栈，访问T->data，再中序遍历T的右子树。*/public void PrintBinaryTreeMidUnrecur(TreeNode<T> root){TreeNode<T> p=root;//p为当前节点LinkedList<TreeNode> stack=new LinkedList<>();//stack中存放的其实就是中间的节点//栈不为空时，或者p不为空时循环while(p!=null || !stack.isEmpty()){//当前节点不为空。压入栈中。并将当前节点赋值为左儿子if (p!=null){stack.push(p);p=p.left;}//当前节点为空：//  1、当p指向的左儿子时，此时栈顶元素必然是它的父节点//  2、当p指向的右儿子时，此时栈顶元素必然是它的爷爷节点//取出并访问栈顶元素，赋值为rightelse{p=stack.pop();System.out.print(p.data);p=p.right;}}}

3、后序遍历的非递归实现

根据后序遍历的顺序，先访问左子树，再访问右子树，后访问根节点，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的后序遍历顺序为：DEBFCA。后序遍历的非递归的实现相对来说要难一些，要保证根节点在左子树和右子树被访问后才能访问，思路如下：
对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。

根据以上思路，后序遍历的非递归实现代码如下：

 /** 后序遍历二叉树（非递归）**/public void PrintBinaryTreeBacUnrecur(TreeNode<T> root){class NodeFlag<T>{TreeNode<T> node;char tag;public NodeFlag(TreeNode<T> node, char tag) {super();this.node = node;this.tag = tag;}}LinkedList<NodeFlag<T>> stack=new LinkedList<>();TreeNode<T> p=root;NodeFlag<T> bt;//栈不空或者p不空时循环while(p!=null || !stack.isEmpty()){//遍历左子树while(p!=null){bt=new NodeFlag(p, 'L');stack.push(bt);p=p.left;}//左右子树访问完毕访问根节点while(!stack.isEmpty() && stack.getFirst().tag=='R'){bt=stack.pop();System.out.print(bt.node.data);}//遍历右子树if (!stack.isEmpty()){bt=stack.peek();bt.tag='R';p=bt.node;p=p.right;}}}

github源码：https://github.com/aweneves/Algorithm1/tree/master/src/Tree
参考：http://blog.csdn.net/lieacui/article/details/52453292
http://blog.csdn.net/aa8568849/article/details/70243956

这篇关于二叉树递归和非递归遍历（先序、中序、后序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1129868。

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
oracle11.2g递归查询（树形结构查询）

oracle11.2g递归查询（树形结构查询）

转自： 一 二 简单语法介绍 一、树型表结构：节点ID 上级ID 节点名称二、公式： select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员：SQL 递归： 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速
阅读更多...
react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注
阅读更多...
Leetcode面试经典150题-128.最长连续序列-递归版本另解

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本 可以看看之前的版本，两个版本面试用哪个都保过 解法都在代码里，不懂就留言或者私信 class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的
阅读更多...
在二叉树中找到两个节点的最近公共祖先（基于Java）

在二叉树中找到两个节点的最近公共祖先（基于Java）

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo
阅读更多...
数据结构--二叉树（C语言实现，超详细！！！）

数据结构--二叉树（C语言实现，超详细！！！）

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树（Binary Tree）是数据结构中一种非常重要的树形结构，它的特点是每个节点最多有两个子节点，通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具
阅读更多...
hashmap的存值，各种遍历方法

hashmap的存值，各种遍历方法

package com.jefflee;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class HashmapTest {// 遍历Hashmap的四种方法public static void main(String[] args) {//hashmap可以存一个null，把
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...
【UVA】10651-Pebble Solitaire（直接递归或者记忆化）

【UVA】10651-Pebble Solitaire（直接递归或者记忆化）

不知道这个题UVA的数据是怎么的，用2个方法交了，第一次直接递归，第二次记忆化剪枝，时间竟然一样！？ 直接郁闷了，简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2