C语言数据结构七：二叉树非递归遍历

article/2025/9/22 16:13:05

二叉树的非递归遍历，必须借助栈的辅助。必须采用栈的这种先进后出的特性。

算法实现思路：

  • 我们先将根节点压入栈中。然后往外弹出元素。直到栈中元素弹完为止。
  • 1、将根节点压入栈中。（但是压入栈中，并不知简单的将根节点压入栈中就完事，我们必须引入一个标记信息。Flag：标识这个节点第几次压入栈中。）(标识：每个结点都要往栈中压两次。第二次再弹出来时，我们取数据。第一次压入栈中，我们将其标注为FALSE，标注是否取值。)
  • 所有节点在第一次弹出时都是false。

重新第一步：

  • 第一步：将根节点压入栈中，将标志位只为FALSE。
  • 第二步：启动while循环：循环条件：栈不为空。
    • 先从栈中弹出栈顶元素。判断元素的标志位：
      • 如果标志位为True则：
        • 该节点值弹出：出栈，然后当前本次循环结束。
    • 如果标志位为false则：

       

      • 将该节点的左子树和右子树压入栈中。（先判断是否为空）
      • 此时入栈就要由顺序要求了。如果想要先序遍历，那么就需要反序压入。确保从栈中弹出元素时，先根后左右。
      • 根节点是二次入栈，将该标志位置为True。
  • 继续执行循环：
    • A先出栈，然后是B，B为false,将左右节点压入栈中，将标志位改为True。
    • 先入B，然后再入C。然后结束本次循环。
    • 先弹出B，然后C的标识位只为True，然后压入DE。不断循环。

我们继续采用前面是用的栈的代码。 

#pragma once#include<stdlib.h>
#include<string.h>#ifdef __cplusplus
extern "C"{
#endif#define MAX 1024//顺序栈数据结构struct SStack{void *data[MAX]; //存放数据的数组int size;//栈中元素的个数};typedef void * SeqStack;//数组高下标的位置当做栈顶，因为不需要移动数组中的元素在插入和删除中//初始化SeqStack Init_SeqStack();//入栈void Push_SeqStack(SeqStack stack, void *data);//出栈void Pop_SeqStack(SeqStack stack);//获得栈顶元素void *Top_SeqStack(SeqStack stack);//获得栈的大小int Size_SeqStack(SeqStack stack);//销毁栈void Destroy_SeqStack(SeqStack stack);#ifdef __cplusplus
}
#endif

采用栈的辅助

#include"SeqStack.h"//初始化
SeqStack Init_SeqStack()
{struct SStack *stack = malloc(sizeof(struct SStack));if (NULL == stack){return NULL;}//memset(stack->data, 0, sizeof(struct SStack));stack->size = 0;for (int i = 0; i < MAX; ++i){stack->data[i] = NULL;}return stack;
}
//入栈
void Push_SeqStack(SeqStack stack, void *data)
{if (NULL == stack){return;}if (NULL == data){return;}struct SStack *s = (struct SStack *)stack;if (s->size == MAX){return;}s->data[s->size] = data;s->size++;
}
//出栈
void Pop_SeqStack(SeqStack stack)
{if (NULL == stack){return;}struct SStack *s = (struct SStack *)stack;if (s->size == 0){return;}s->data[s->size - 1] = NULL;s->size--;
}
//获得栈顶元素
void *Top_SeqStack(SeqStack stack)
{if (NULL == stack){return NULL;}struct SStack *s = (struct SStack *)stack;if (s->size == 0){return NULL;}return s->data[s->size - 1];}
//获得栈的大小
int Size_SeqStack(SeqStack stack)
{if (NULL == stack){return -1;}struct SStack *s = (struct SStack *)stack;return s->size;
}
//销毁栈
void Destroy_SeqStack(SeqStack stack)
{if (NULL == stack){return;}free(stack);
}

为了实现二叉树的非递归遍历：

节点结构体：除了节点，还需要一个标识位。

struct Info
{struct BiNode *node;bool flag;
};

 因为引入bool量，所以引用：<stdbool.h>

struct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};

初始化根节点：返回根节点，然后输入为

struct Info* createInfo(struct BiNode *node, bool flag)
{struct Info *info = malloc(sizeof(struct Info));info->flag = flag;info->node = node;return info;
}

初始化栈：

void nonRecursion(struct BiNode *root)
{//初始化栈SeqStack stack = Init_SeqStack();//先把根节点压入栈中Push_SeqStack(stack, createInfo(root, false));while (Size_SeqStack(stack) > 0){//获得栈顶元素	struct Info *info = (struct Info *)Top_SeqStack(stack);//弹出栈顶元素Pop_SeqStack(stack);if (info->flag){printf("%c ",info->node->ch);free(info);continue;}// 这个地方的压栈顺序，就影响了后续的输出顺序。压入栈顺序不同，最后出栈顺序也不同。//将根节压入栈中info->flag = true;Push_SeqStack(stack, info);//将右子树压入栈中if (info->node->rchild != NULL){Push_SeqStack(stack, createInfo(info->node->rchild, false));}//将左子树压入栈中if (info->node->lchild != NULL){Push_SeqStack(stack, createInfo(info->node->lchild, false));}}//销毁栈Destroy_SeqStack(stack);
}

 整体实现：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include"SeqStack.h"struct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};struct Info
{struct BiNode *node;bool flag;
};struct Info* createInfo(struct BiNode *node, bool flag)
{struct Info *info = malloc(sizeof(struct Info));info->flag = flag;info->node = node;return info;
}void nonRecursion(struct BiNode *root)
{//初始化栈SeqStack stack = Init_SeqStack();//先把根节点压入栈中Push_SeqStack(stack, createInfo(root, false));while (Size_SeqStack(stack) > 0){//获得栈顶元素	struct Info *info = (struct Info *)Top_SeqStack(stack);//弹出栈顶元素Pop_SeqStack(stack);if (info->flag){printf("%c ",info->node->ch);free(info);continue;}//将根节压入栈中info->flag = true;Push_SeqStack(stack, info);//将右子树压入栈中if (info->node->rchild != NULL){Push_SeqStack(stack, createInfo(info->node->rchild, false));}//将左子树压入栈中if (info->node->lchild != NULL){Push_SeqStack(stack, createInfo(info->node->lchild, false));}}//销毁栈Destroy_SeqStack(stack);
}void test()
{struct BiNode nodeA = { 'A', NULL, NULL };struct BiNode nodeB = { 'B', NULL, NULL };struct BiNode nodeC = { 'C', NULL, NULL };struct BiNode nodeD = { 'D', NULL, NULL };struct BiNode nodeE = { 'E', NULL, NULL };struct BiNode nodeF = { 'F', NULL, NULL };struct BiNode nodeG = { 'G', NULL, NULL };struct BiNode nodeH = { 'H', NULL, NULL };nodeA.lchild = &nodeB;nodeA.rchild = &nodeF;nodeB.rchild = &nodeC;nodeC.lchild = &nodeD;nodeC.rchild = &nodeE;nodeF.rchild = &nodeG;nodeG.lchild = &nodeH;nonRecursion(&nodeA);}int main(){test();system("pause");return EXIT_SUCCESS;
}


http://chatgpt.dhexx.cn/article/pNeLo9ei.shtml

相关文章

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

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

首先是一个二叉树结构&#xff1a; class TreeNode{public int value;public TreeNode left;public TreeNode right;public TreeNode(){}public TreeNode(int v){valuev;} 非递归的二叉树遍历需要用到栈的先进后出。 先序遍历 步骤&#xff1a; 1、首先定义一个当前正在检索…
阅读更多...
二叉树非递归遍历（c语言）

二叉树非递归遍历（c语言）

结果如下图&#xff1a; #号代表NULL&#xff0c;此时没有节点 一、在c语言中进行二叉树的非递归遍历需要用到栈&#xff0c;而在c语言中没有直接调用栈的接口&#xff0c;所以在实现非递归遍历时需要先实现一个栈&#xff0c;需要用到出栈&#xff0c;入栈&#xff0c;栈顶元…
阅读更多...
二叉树非递归遍历实现（Java）

二叉树非递归遍历实现（Java）

首先理解一下二叉树节点结构。left指向左节点&#xff0c;right指向右节点&#xff0c;val为节点中的值。 class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int x) {val x;}} 先序遍历 //非递归先序遍历&#xff08;需一个辅助栈&#xff0c;顺序为根…
阅读更多...
二叉树遍历的一些非递归算法

二叉树遍历的一些非递归算法

二叉树的非递归算法因为涉及到栈和队列&#xff0c;所以写的时候总是受到伪代码的干扰&#xff0c;要完整的补全栈和队列的结构有些麻烦&#xff0c;这里借鉴了一些大佬的思想&#xff0c;发现可以直接在树中模拟栈和队列的存在&#xff0c;这给非递归的完整代码带来了很大的便…
阅读更多...
三种非递归遍历二叉树的方法

三种非递归遍历二叉树的方法

就以这个树为例&#xff0c;来讲讲二叉树的非递归遍历。 先序遍历&#xff1a; 先序遍历结果为3 4 6 5 8 9&#xff0c;就拿树的左枝为例&#xff0c;3是根&#xff0c;打印&#xff0c;4是3的左孩子&#xff0c;打印&#xff0c;6是4的左孩子&#xff0c;打印&#xff0c;6的…
阅读更多...
二叉树的非递归遍历

二叉树的非递归遍历

目录 一.前序遍历&#xff08;根左右&#xff09; 1.思路图解 2.代码 二.中序遍历&#xff08;左根右&#xff09; 1.思路图解 2.代码 三.后序遍历&#xff08;左右根&#xff09; 1.思路图解 2.代码 四.层序遍历 1.思路图解 2.代码 一.前序遍历&#xff08;根左右…
阅读更多...
smile——Java机器学习引擎

smile——Java机器学习引擎

介绍 Smile&#xff08;统计机器智能和学习引擎&#xff09;是一个基于Java和Scala的快速、全面的机器学习、NLP、线性代数、图形、插值和可视化系统。 凭借先进的数据结构和算法&#xff0c;Smile提供了最先进的性能。Smile有很好的文档记录&#xff0c;请查看项目网站以获取…
阅读更多...
Java机器学习库（Java ML）（一、分类）

Java机器学习库（Java ML）（一、分类）

本文章翻译至Java ML技术文档classification.pdf&#xff0c;代码部分是参考该文档使用IDEA编写&#xff0c;同时加入了运行结果。 分类 本文介绍与分类相关的功能。 该文章假设您已熟悉Java ML的基础知识&#xff0c;如入门教程中所述&#xff08;http://java-ml.sourcefor…
阅读更多...
目前流行的、强大的基于Java的机器学习开发库精选

目前流行的、强大的基于Java的机器学习开发库精选

图片来源: Mindfire Solutions 现如今&#xff0c;拥有深度学习和机器学习领域的技术是科技界的趋势之一&#xff0c;并且企业则希望雇佣一些拥有良好的机器学习知识背景的程序开发工程师。本文将介绍一些目前流行的、强大的基于Java的机器学习库&#xff0c;希望给大家带来帮助…
阅读更多...
JAVA 人工神经网络实现，机器学习，人工智能

JAVA 人工神经网络实现，机器学习，人工智能

人工智能&#xff08;AI&#xff09; 、机器学习&#xff08;ML&#xff09;、深度学习&#xff08;DL&#xff09;、神经网络&#xff08;CNN&#xff09; IT技术圈的人怼这些词汇大家都一定耳熟能详了&#xff0c;可能圈外的也不陌生&#xff0c;但是作为一个作为一个“攻城…
阅读更多...
机器学习java_如何开始使用Java机器学习

机器学习java_如何开始使用Java机器学习

机器学习java 什么是开始使用Java机器学习的最佳工具&#xff1f; 他们已经存在了一段时间&#xff0c;但如今看来&#xff0c;每个人都在谈论人工智能和机器学习。 对于科学家和研究人员而言&#xff0c;它已经不再是秘密&#xff0c;几乎可以在任何新兴技术中实现。 在下面…
阅读更多...
谁说搞Java的不能玩机器学习？

谁说搞Java的不能玩机器学习？

简介 机器学习在全球范围内越来越受欢迎和使用。 它已经彻底改变了某些应用程序的构建方式&#xff0c;并且可能会继续成为我们日常生活中一个巨大的&#xff08;并且正在增加的&#xff09;部分。没有什么包装且机器学习并不简单。 它对许多人来说似乎非常复杂并常常令人生畏…
阅读更多...
基于 Java 机器学习自学笔记 （第51-53天：kNN）

基于 Java 机器学习自学笔记 （第51-53天：kNN）

注意&#xff1a;本篇为50天后的Java自学笔记扩充&#xff0c;内容不再是基础数据结构内容而是机器学习中的各种经典算法。这部分博客更侧重与笔记以方便自己的理解&#xff0c;自我知识的输出明显减少&#xff0c;若有错误欢迎指正&#xff01; 目录 一、关于数据集及其导入…
阅读更多...
基于 Java 机器学习自学笔记 （第66至68天：主动学习之ALEC）

基于 Java 机器学习自学笔记 （第66至68天：主动学习之ALEC）

注意&#xff1a;本篇为50天后的Java自学笔记扩充&#xff0c;内容不再是基础数据结构内容而是机器学习中的各种经典算法。这部分博客更侧重于笔记以方便自己的理解&#xff0c;自我知识的输出明显减少&#xff0c;若有错误欢迎指正&#xff01; 目录 前言 一、关于学习的分类…
阅读更多...
超全！基于Java的机器学习项目、环境、库...

超全！基于Java的机器学习项目、环境、库...

https://yq.aliyun.com/articles/278837?utm_sourcetuicool&utm_mediumreferral 摘要&#xff1a; 你是一名希望开始或者正在学习机器学习的Java程序员吗&#xff1f; 利用机器学习编写程序是最佳的学习方式。你可以从头开始编写算法&#xff0c;但是利用现有的开源库&am…
阅读更多...
结合Java和机器学习技术，如何驾驭大数据提升业务效率和竞争力？

结合Java和机器学习技术，如何驾驭大数据提升业务效率和竞争力？

随着大数据的不断增长和发展&#xff0c;越来越多的企业和组织开始关注如何利用大数据来提高业务效率和竞争力。在大数据分析领域&#xff0c;Java和机器学习技术是两个非常重要的方向。本文将介绍这两个技术的基本概念、应用场景和发展趋势&#xff0c;并重点探讨如何结合Java…
阅读更多...
25个JAVA 机器学习工具包

25个JAVA 机器学习工具包

本列表总结了25个Java机器学习工具&库&#xff1a; 1. Weka集成了数据挖掘工作的机器学习算法。这些算法可以直接应用于一个数据集上或者你可以自己编写代码来调用。Weka包括一系列的工具&#xff0c;如数据预处理、分类、回归、聚类、关联规则以及可视化。 2.Massive Onli…
阅读更多...
7个最好的Java机器学习开发库

7个最好的Java机器学习开发库

IT派 - {技术青年圈} 持续关注互联网、区块链、人工智能领域 摘要&#xff1a; 本文将介绍一些目前流行的、强大的基于Java的机器学习库。 图片来源: Mindfire Solutions 摘要&#xff1a;现如今&#xff0c;拥有深度学习和机器学习领域的技术是科技界的趋势之一&#xff0c;并…
阅读更多...
基于 Java 机器学习自学笔记 （第71-73天：BP神经网络）

基于 Java 机器学习自学笔记 （第71-73天：BP神经网络）

注意&#xff1a;本篇为50天后的Java自学笔记扩充&#xff0c;内容不再是基础数据结构内容而是机器学习中的各种经典算法。这部分博客更侧重于笔记以方便自己的理解&#xff0c;自我知识的输出明显减少&#xff0c;若有错误欢迎指正&#xff01; 前言 本文是我计划描述BP神经网…
阅读更多...
如何开始Java机器学习

如何开始Java机器学习

什么是开始使用Java机器学习的最佳工具&#xff1f; 他们已经存在了一段时间&#xff0c;但如今看来&#xff0c;每个人都在谈论人工智能和机器学习。 对于科学家和研究人员而言&#xff0c;它已不再是秘密&#xff0c;几乎可以在任何新兴技术中实现。 在下面的文章中&#x…
阅读更多...
推荐文章

Copyright @ 2022~2023