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

article/2025/9/22 17:00:02

        二叉树的非递归算法因为涉及到栈和队列，所以写的时候总是受到伪代码的干扰，要完整的补全栈和队列的结构有些麻烦，这里借鉴了一些大佬的思想，发现可以直接在树中模拟栈和队列的存在，这给非递归的完整代码带来了很大的便利，与我而言，深受启发！

1.先序创建二叉树

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100//定义二叉树的结构体
typedef struct BiNode {char data;struct BiNode* lchild;struct BiNode* rchild;
}BiNode, * BiTree;//先序创建二叉树
BiTree CreateBiTree() {BiNode* T = NULL;char ch;ch = getchar();//先序输入树的各个节点值if (ch != '#') {T = (BiNode*)malloc(sizeof(BiNode));T->data = ch;T->lchild = CreateBiTree();T->rchild = CreateBiTree();}else {T = NULL;}return T;
}

2.非递归先序遍历二叉树

//非递归先序遍历二叉树
void PreOrder(BiTree T) {BiTree stack[MAXSIZE], node;//模拟栈int top = 0;if (T == NULL) {printf("树为空树!\n");return;}else {top++;stack[top] = T;while (top > 0) {//出栈node = stack[top--];printf("%c ", node->data);//先把右子树放进去，再放左子树，栈先进后出，左先出if (node->rchild != NULL) {stack[++top] = node->rchild;//入栈}if (node->lchild != NULL) {stack[++top] = node->lchild;}}}
}

3.非递归中序遍历二叉树 

//非递归中序遍历二叉树
void InOrder(BiTree T) {BiTree stack[MAXSIZE], node;int top = 0;if (T == NULL) {printf("树为空树!\n");return;}node = T;while (node != NULL || top > 0) {//将所有的左子树节点入栈while (node != NULL) {stack[++top] = node;node = node->lchild;}//此时指针指向节点的左孩子为空节点，访问节点node = stack[top--];printf("%c ", node->data);//指针指向右孩子node = node->rchild;}
}

4.非递归后序遍历二叉树 

//非递归后序遍历二叉树
void PostOrder(BiTree T) {BiNode* p = T;BiNode* stack[MAXSIZE];BiNode* r = NULL;//辅助指针,记录被访问过的节点int top = 0;while (p || top > 0) {  while (p) {     //走到最左边stack[top++] = p;p = p->lchild;}p = stack[top - 1]; //指针指向最后一个入栈的左节点if (NULL== p->rchild || p->rchild == r) {//此节点没有右孩子或者右孩子已经访问过printf("%c ", p->data);//访问该节点值top--;  r = p;  //记录最近访问过的节点p = NULL;   //节点访问完后重置p指针}else {p = p->rchild; //右孩子存在则指向右孩子，重复上面操作}}
}

5.非递归层序遍历二叉树 

//非递归层序遍历二叉树
void InvertLevel(BiTree T) {BiTree stack[MAXSIZE],node;//栈node = T;int front = 0;//模拟队列队头int rear = 0;//模拟队列队尾stack[rear++] = node;if (T == NULL) {printf("树为空树！\n");return;}while (front != rear) {//队列不为空node = stack[front++];//先获取队头元素，然后再指向队列的下一位元素printf("%c ", node->data);//访问节点元素if (node->lchild) {     stack[rear++] = node->lchild; //此节点左孩子不空，则入队列}if (node->rchild) {stack[rear++] = node->rchild; //此节点右孩子不空，则入队列}} //自上而下，从左到右依次遍历
}

6.非递归层序遍历求解二叉树的高度

//非递归层序遍历求解二叉树的高度
int TreeDepth(BiTree T) {if (!T)return 0;   //树空，高度为0BiTree Q[MAXSIZE];  //设置队列Qint front = -1, rear = -1;  //队头和队尾指针int last = 0,level = 0;    //last指向每层的最后一个节点的位置Q[++rear] = T;  //根节点入队BiTree p;   //工作指针while (front < rear) {  //队列不为空，则循环p = Q[++front]; //队列元素出队，对其进行访问if (p->lchild)Q[++rear] = p->lchild;  //左孩子入队if (p->rchild)Q[++rear] = p->rchild;  //右孩子入队if (front == last) {    //处理该层的最右结点level++;last = rear;    //last指向下一层}}return level;
}

 7.完整代码+测试运行

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100//定义二叉树的结构体
typedef struct BiNode {char data;struct BiNode* lchild;struct BiNode* rchild;
}BiNode, * BiTree;//先序创建二叉树
BiTree CreateBiTree() {BiNode* T = NULL;char ch;ch = getchar();//先序输入树的各个节点值if (ch != '#') {T = (BiNode*)malloc(sizeof(BiNode));T->data = ch;T->lchild = CreateBiTree();T->rchild = CreateBiTree();}else {T = NULL;}return T;
}//非递归先序遍历二叉树
void PreOrder(BiTree T) {BiTree stack[MAXSIZE], node;//模拟栈int top = 0;if (T == NULL) {printf("树为空树!\n");return;}else {top++;stack[top] = T;while (top > 0) {//出栈node = stack[top--];printf("%c ", node->data);//先把右子树放进去，再放左子树，栈先进后出，左先出if (node->rchild != NULL) {stack[++top] = node->rchild;//入栈}if (node->lchild != NULL) {stack[++top] = node->lchild;}}}
}
//非递归中序遍历二叉树
void InOrder(BiTree T) {BiTree stack[MAXSIZE], node;int top = 0;if (T == NULL) {printf("树为空树!\n");return;}node = T;while (node != NULL || top > 0) {//将所有的左子树节点入栈while (node != NULL) {stack[++top] = node;node = node->lchild;}//此时指针指向节点的左孩子为空节点，访问节点node = stack[top--];printf("%c ", node->data);//指针指向右孩子node = node->rchild;}
}
//非递归后序遍历二叉树
void PostOrder(BiTree T) {BiNode* p = T;BiNode* stack[MAXSIZE];BiNode* r = NULL;//辅助指针,记录被访问过的节点int top = 0;if (T == NULL) {printf("树为空树!\n");return;}while (p || top > 0) {  while (p) {     //走到最左边stack[top++] = p;p = p->lchild;}p = stack[top - 1]; //指针指向最后一个入栈的左节点if (NULL== p->rchild || p->rchild == r) {//此节点没有右孩子或者右孩子已经访问过printf("%c ", p->data);//访问该节点值top--;  r = p;  //记录最近访问过的节点p = NULL;   //节点访问完后重置p指针}else {p = p->rchild; //右孩子存在则指向右孩子，重复上面操作}}
}
//非递归层序遍历二叉树
void InvertLevel(BiTree T) {BiTree stack[MAXSIZE],node;//栈node = T;int front = 0;//模拟队列队头int rear = 0;//模拟队列队尾stack[rear++] = node;if (T == NULL) {printf("树为空树！\n");return;}while (front != rear) {//队列不为空node = stack[front++];//先获取队头元素，然后再指向队列的下一位元素printf("%c ", node->data);//访问节点元素if (node->lchild) {     stack[rear++] = node->lchild; //此节点左孩子不空，则入队列}if (node->rchild) {stack[rear++] = node->rchild; //此节点右孩子不空，则入队列}} //自上而下，从左到右依次遍历
}
//非递归层序遍历求解二叉树的高度
int TreeDepth(BiTree T) {if (!T)return 0;   //树空，高度为0BiTree Q[MAXSIZE];  //设置队列Qint front = -1, rear = -1;  //队头和队尾指针int last = 0,level = 0;    //last指向每层的最后一个节点的位置Q[++rear] = T;  //根节点入队BiTree p;   //工作指针while (front < rear) {  //队列不为空，则循环p = Q[++front]; //队列元素出队，对其进行访问if (p->lchild)Q[++rear] = p->lchild;  //左孩子入队if (p->rchild)Q[++rear] = p->rchild;  //右孩子入队if (front == last) {    //处理该层的最右结点level++;last = rear;    //last指向下一层}}return level;
}
int main() {BiTree T = CreateBiTree();// BiTree T = create_tree();printf("非递归先序遍历二叉树：\n");PreOrder(T);printf("\n");printf("非递归中序遍历二叉树：\n");InOrder(T);printf("\n");printf("非递归后序遍历二叉树：\n");PostOrder(T);printf("\n");printf("非递归层序遍历二叉树：\n");InvertLevel(T);printf("\n");printf("非递归计算二叉树的深度为：\n");printf("树的深度为：%d\n", TreeDepth(T)); return 0;
}


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

相关文章

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

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

就以这个树为例&#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…
阅读更多...
如何开始使用 Java 机器学习

如何开始使用 Java 机器学习

开始Java机器学习的最好工具是什么&#xff1f; 这个问题已经有一段时间了&#xff0c;但最近这些日子几乎每个人都在谈论人工智能和机器学习。这已经不再是一个保留给科学家和研究者的秘密&#xff0c;而是几乎实现于每一项新兴技术中。 在下面的章节中&#xff0c;我们会做一…
阅读更多...
6大最常用的Java机器学习库一览

6大最常用的Java机器学习库一览

导读&#xff1a;机器学习是目前盛行于世的技术之一&#xff0c;这几年一时风头无两。虽然在机器学习中&#xff0c;Python是人工智能从业者使用最多的编程语言&#xff0c;但是&#xff0c;Java 在项目开发中仍然发挥着不可替代的作用&#xff0c;而且许多流行的机器学习框架本…
阅读更多...
基于 Java 机器学习自学笔记 （第60天：过去十日的总结）

基于 Java 机器学习自学笔记 （第60天：过去十日的总结）

注意&#xff1a;本篇为50天后的Java自学笔记扩充&#xff0c;内容不再是基础数据结构内容而是机器学习中的各种经典算法。这部分博客更侧重于笔记以方便自己的理解&#xff0c;自我知识的输出明显减少&#xff0c;若有错误欢迎指正&#xff01; 目录 1.尝试作为知识的输出者 …
阅读更多...
机器学习入门-用Java实现简单感知机

机器学习入门-用Java实现简单感知机

一、通俗理解机器学习 1、机器学习是人工智能的一种&#xff0c;如图所示&#xff0c;它是人工智能的一个子方向。 2、机器学习有点像人类的学习过程。 1. 人类学习通过经验(事件)&#xff0c;归纳出规律。 2. 机器学习通过数据&#xff0c;训练出模型。 3、机器学习不是基于编…
阅读更多...
推荐文章

Copyright @ 2022~2023