通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

详解二叉树的三种非递归遍历方式（附C、java源码）

前言

二叉树的递归遍历方式很简单，三种递归遍历方式的区别，只是printf放的位置不一样而已，这里就不多讲了。把前序遍历代码贴在这里：

//结点
struct Node
{
	int val;
	struct Node* left, * right;
};

//前序遍历
void pre(Node* root)
{
    if (root == null)
        return;
    printf("%d ",root->val);
    pre(root->left);
    pre(root->right);
}

前序、中序和后序这三种非递归的遍历方式，中序是最为简单的，其次是前序，再者就是后序，只是个人感觉。可能每个人感觉都不一样吧。

一、非递归中序遍历

中序遍历顺序： 左子树->头结点->右子树。

如图—出自于《大话数据结构》

所以我们首先需要考虑的是将左手边（左子树）的结点压入栈，当到达底部时（NULL），我们就输出此时栈顶的元素。

然后转而去添加当前结点的右手边（右子树）的结点到栈里。

#define MAXSIZE 20  //整棵树最大的结点数，用于开辟数组当栈使用
typedef struct Node Node;
void in(Node* root)
{
    Node* stack[MAXSIZE] = { 0 };
    int size = 0; //用于指向arr数组，也是用于表示这个数组还有几个元素
    while (size != 0 || root != NULL)
    {
        if (root != NULL)
        {
            stack[size++] = root;
            root = root->left;  //继续往左子树走
        }
        else
        {
            //此时root为NULL，说明来到了左子树的最底部，此时输出栈顶元素，root往右子树走即可
            printf("%c ", stack[--size]->val);
            root = stack[size]->right;
        }
    }
}

二、非递归前序遍历

前序遍历顺序： 头结点->左子树-> 右子树

我记得我在B站学算法的时候，听左程云老师所说，一些的递归行为，都可以自己用栈来实现。

确实，三种非递归的遍历方式实则也是需要自己实现栈的功能。接下来的前序遍历方式，要用到宽度优先遍历的思想，如图：

图片出自《大话数据结构》

先加入第一层的全部数据，然后在栈中使用第一层数据的同时，判断加入第二层的全部数据，第三层的也是一样…

#define MAXSIZE 20  //整棵树最大的结点数，用于开辟数组当栈使用
typedef struct Node Node;
void pre(Node* root)
{
    if (root == NULL)
        return;

    Node* stack[MAXSIZE] = { 0 }; //模拟栈
    int size = 0; //代表此时栈有多少元素
    arr[size++] = root;
    while (size != 0)
    {
        Node* node = stack[--size];
        printf("%c ", node->val);
        //先压入右孩子，再压入左孩子。这样在弹出的时候才是  先弹出左孩子 然后才是右孩子
        //头   左   右
        if (node->right != NULL)
            stack[size++] = node->right;
        if (node->left != NULL)
            stack[size++] = node->left;
    }
}

三、非递归后序遍历

在讲解了非递归的前序遍历，其实我们在前序遍历的基础之上改一下就能完成后序遍历。我们在将前序遍历时，在while循环里，加入左右孩子结点时，先加入栈的是右孩子，然后才是左孩子，只有这样，我们弹出来的顺序才是先左后右。

现在我们只需要改一下加入左右孩子的顺序时，我们先压入栈是左孩子，然后再压入右孩子。 这样弹出来就是先右再左的顺序。那此时再加上头结点，那就是 头结点->右孩子->左孩子 。 此时我们从后面往前面读，就是 左孩子 -> 右孩子 ->头结点。这样就变成了后序遍历了。。。

图片出自《大话数据结构》

#define MAXSIZE 20  //整棵树最大的结点数，用于开辟数组当栈使用
typedef struct Node Node;
void postorder(Node* root)
{
    if (root == NULL)
        return;

    Node* stack1[MAXSIZE] = { 0 }; //主要栈
    Node* stack2[MAXSIZE] = { 0 };  //辅助栈
    int size1 = 0; //主要栈：代表数组的元素个数
    int size2 = 0; //辅助栈: 代表数组的元素个数
    stack1[size1++] = root;
    while (size1 != 0)
    {
        Node* node = stack1[--size1];
        stack2[size2++] = node; //暂时存入辅助栈

        //先压入左孩子，再压入右孩子
        if (node->left != NULL)
            stack1[size1++] = node->left;
        if (node->right != NULL)
            stack1[size1++] = node->right;
    }

    //倒着输出辅助栈的数据即可
    while (size2-- != 0)
        printf("%c ", stack2[size2]->val);
}

非递归与递归方式的遍历，有些相似之处，总结两种不同的方法，就能更深刻的理解这些方法。最后，C/C++的同学，记得回收malloc开辟的空间哦！！！

C语言源码

java语言源码

下期见啦！！！

到此这篇关于通俗易懂讲解C语言中二叉树的三种非递归遍历方式的文章就介绍到这了,更多相关C 二叉树非递归遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • java栈实现二叉树的非递归遍历的示例代码

    java栈实现二叉树的非递归遍历的示例代码

    一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法. 二叉树设置 class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); No

  • java二叉树的几种遍历递归与非递归实现代码

    java二叉树的几种遍历递归与非递归实现代码

    前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • 通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

    通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

    详解二叉树的三种非递归遍历方式(附C.java源码) 前言 二叉树的递归遍历方式很简单,三种递归遍历方式的区别,只是printf放的位置不一样而已,这里就不多讲了.把前序遍历代码贴在这里: //结点 struct Node { int val; struct Node* left, * right; }; //前序遍历 void pre(Node* root) { if (root == null) return; printf("%d ",root->val); pre(roo

  • 漫画讲解C语言中最近公共祖先的三种类型

    漫画讲解C语言中最近公共祖先的三种类型

    最近公共祖先定义 查找最近公共祖先 三叉链 代码如下: //三叉链 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode *parent; TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {} }; class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* ro

  • Java中二叉树的建立和各种遍历实例代码

    Java中二叉树的建立和各种遍历实例代码

    这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序->建树 假设现在有个二叉树,如下: 此时遍历顺序是: PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG 现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树 或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的 树节点的定义: class Tree{ char val; Tree lef

  • 一篇文章彻底弄懂Java中二叉树

    一篇文章彻底弄懂Java中二叉树

    目录 一.树形结构 1.1 相关概念 1.2树的表示形式 1.3树的应用:文件系统管理(目录和文件) 二.二叉树 2.1相关概念 2.2 二叉树的基本形态 2.3 两种特殊的二叉树 2.4 二叉树的性质 2.5 二叉树的存储 2.6 二叉树的基本操作 2.6.1二叉树的遍历 2.6.2 二叉树的基本操作 总结 一.树形结构 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.它具有以下的特点:

  • 详解Java中二叉树的基础概念(递归&迭代)

    详解Java中二叉树的基础概念(递归&迭代)

    目录 1.树型结构 1.1概念 1.2概念(重要) 2.二叉树(重点) 2.1概念 2.2二叉树的基本形态 2.3两种特殊的二叉树 2.4二叉树的性质 2.5二叉树的存储 2.6二叉树的基本操作 2.7二叉树的层序遍历 3.二叉树完整代码 1. 树型结构 1.1概念 树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合. 把它叫做树是因为它看 起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 . 1.2 概念(重要) a.节点的度:该节点子树的个数:如

  • Java开发深入分析讲解二叉树的递归和非递归遍历方法

    Java开发深入分析讲解二叉树的递归和非递归遍历方法

    目录 前言 1.递归遍历 2.非迭代遍历 3.二叉树的统一迭代法 前言 二叉树的遍历方法分为前序遍历,中序遍历,后续遍历,层序遍历. 1.递归遍历 对于递归,就不得不说递归三要素:以前序遍历为例 递归入参参数和返回值 因为要打印出前序遍历节点的数值,所以参数里需要传入List在放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下: public void preorder(TreeNode root, List<Integer> resu

  • Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

    Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • 基于java解析JSON的三种方式详解

    本文实例分析了基于java解析JSON的三种方式.分享给大家供大家参考,具体如下: 一.什么是JSON? JSON是一种取代XML的数据结构,和xml相比,它更小巧但描述能力却不差,由于它的小巧所以网络传输数据将减少更多流量从而加快速度. JSON就是一串字符串 只不过元素会使用特定的符号标注. {} 双括号表示对象 [] 中括号表示数组 "" 双引号内是属性或值 : 冒号表示后者是前者的值(这个值可以是字符串.数字.也可以是另一个数组或对象) 所以 {"name"

  • java 引用传递的三种类型小结

    java 引用传递的三种类型小结

    目录 java引用传递的三种类型 第一种 第二种传递方式 第三种传递方式 对于三种引用传递的理解 java引用传值问题 问题起源,一个蠢到家的是失败案例 两类参数传递 基本数据类型 引用数据类型 引用传递 反过来再解决这个案例 java引用传递的三种类型 我这里使用了mldn视频里的例子,只用于学习交流. 第一种 结果:调用前:50 调用后:1000 分析: 理解:好理解 第二种传递方式 先看例子 运行结果: 分析图片: 第三种传递方式 结果: 分析: 对于三种引用传递的理解 第一种和第三种都好

  • Java中mybatis的三种分页方式

    Java中mybatis的三种分页方式

    目录 前言 一.Limit分页 二.RowBounds分页(不推荐使用) 三.Mybatis_PageHelper分页插件 前言 分页是我们在开发中绕不过去的一个坎!当你的数据量大了的时候,一次性将所有数据查出来不现实,所以我们一般都是分页查询的,减轻服务端的压力,提升了速度和效率!也减轻了前端渲染的压力! 注意:由于 java 允许的最大整数为 2147483647,所以 limit 能使用的最大整数也是 2147483647,一次性取出大量数据可能引起内存溢出,所以在大数据查询场合慎重使用!

随机推荐