链式二叉树的前序、中序、后序遍历实现（C语言）

目录

前言

二叉树的遍历

模拟实现二叉树（链式二叉树）

前序遍历

前序遍历的实现

二叉树的递归遍历图

中序遍历

中序遍历的实现

后序遍历

后序遍历的实现 

整体代码

前言

        我们在二叉树的基本概念（C语言）中学习了二叉树的基本概念，现在我们开始学习二叉树的三种遍历方式的实现。

二叉树的遍历

概念： 二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
二叉树的递归定义： 二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树，左子树和右子树又同样都是二叉树。
包含内容：
  1. 前序遍历——访问根结点的操作发生在遍历其左右子树之前，即根->左->右
  2. 中序遍历——访问根结点的操作发生在遍历其左右子树之中，即左->根->右
  3. 后序遍历——访问根结点的操作发生在遍历其左右子树之后，即左->右->根

为了方便学习，我们将空的位置仍然以NULL表示 

模拟实现二叉树（链式二叉树）

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreatTree()
{

	TreeNode* node1 = BuyTreeNode(1);

	TreeNode* node2 = BuyTreeNode(2);

	TreeNode* node3 = BuyTreeNode(3);

	TreeNode* node4 = BuyTreeNode(4);

	TreeNode* node5 = BuyTreeNode(5);

	TreeNode* node6 = BuyTreeNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	//node2->right = NULL;
	//node3->left = NULL;
	//node3->right = NULL;
	node4->left = node5;
	node4->right = node6;
	//node5->left = NULL;
	//node5->right = NULL;
	//node6->left = NULL;
	//node6->right= NULL;

	return node1;
}

int main()
{
	TreeNode* root = CreatTree();
	return 0;
}

前序遍历

前序遍历的实现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreatTree()
{

	TreeNode* node1 = BuyTreeNode(1);

	TreeNode* node2 = BuyTreeNode(2);

	TreeNode* node3 = BuyTreeNode(3);

	TreeNode* node4 = BuyTreeNode(4);

	TreeNode* node5 = BuyTreeNode(5);

	TreeNode* node6 = BuyTreeNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	//node2->right = NULL;
	//node3->left = NULL;
	//node3->right = NULL;
	node4->left = node5;
	node4->right = node6;
	//node5->left = NULL;
	//node5->right = NULL;
	//node6->left = NULL;
	//node6->right= NULL;

	return node1;
}

void PrevOrder(TreeNode* root)
{
	if(root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
int main()
{
	TreeNode* root = CreatTree();
	PrevOrder(root);
	return 0;
}

实现步骤：

1、在完成一个二叉树的基础上，我们实现了前序遍历的理论变现，即根->左->右

2、先令前序遍历函数接收总根节点的值（单链表的头）

3、进入函数后判断此时的根节点（1）是否为空，若为空则打印N表示空，若不为空则打印对应的值（1）

4、此后递归的读取当前结点（1）的左子树的根节点（3），若该结点不为空则打印对应的值（3），然后继续递归读取其左子树的根节点（NULL），此时结点为空打印N后返回上一次的位置（3），然后执行当前结点（3）的右递归，当前结点的右子树的根节点（NULL）为空打印N后结束，返回上一次的位置（2）（到这里整个左子树最底层的一个PrevOrder已经结束了），然后执行当前结点（2）的右递归，当前结点的右子树的根节点（NULL）为空打印N后结束，返回上一次位置（1）（到这里整个左子树的倒数第二个PrevOrder已经结束了）

5、接下俩就应该去读取（1）的右子树的根节点（4）了（因为到这里第一个PrevOrder的左递归才算完全结束，现在开始右递归）

6、（4）不为空打印对应的值（4），然后继续递归读取其左子树的根节点（5），不为空打印对应的值（5），然后继续递归读取其左子树的根节点（NULL）为空打印N后返回上一次的位置（5），然后继续递归读取其右子树的根节点（NULL）为空打印N后返回上一次的位置（4）（到这里整个右子最底层的一个PrevOrder已经结束了）然后继续递归读取其右子树的根节点（6），不为空打印对应的值（6），然后继续递归读取其左子树的根节点（NULL）为空打印N后返回上一次的位置（6），然后继续递归读取其右子树的根节点（NULL）为空后打印N后返回上一次的位置（4）

7、至此，该二叉树的前序遍历完成

一共用了五次PrevOrder，左子树两次，右子树两次，主二叉树一次

二叉树的递归遍历图

中序遍历

中序遍历的实现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreatTree()
{

	TreeNode* node1 = BuyTreeNode(1);

	TreeNode* node2 = BuyTreeNode(2);

	TreeNode* node3 = BuyTreeNode(3);

	TreeNode* node4 = BuyTreeNode(4);

	TreeNode* node5 = BuyTreeNode(5);

	TreeNode* node6 = BuyTreeNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	//node2->right = NULL;
	//node3->left = NULL;
	//node3->right = NULL;
	node4->left = node5;
	node4->right = node6;
	//node5->left = NULL;
	//node5->right = NULL;
	//node6->left = NULL;
	//node6->right= NULL;

	return node1;
}

void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
int main()
{
	TreeNode* root = CreatTree();
	InOrder(root);
	return 0;
}

实现步骤：中序遍历只是将前序遍历的PrevOrder中的 (root->data)与 (root->left)交换了位置，具体实现内容建议自行尝试

后序遍历

后序遍历的实现 

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreatTree()
{

	TreeNode* node1 = BuyTreeNode(1);

	TreeNode* node2 = BuyTreeNode(2);

	TreeNode* node3 = BuyTreeNode(3);

	TreeNode* node4 = BuyTreeNode(4);

	TreeNode* node5 = BuyTreeNode(5);

	TreeNode* node6 = BuyTreeNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	//node2->right = NULL;
	//node3->left = NULL;
	//node3->right = NULL;
	node4->left = node5;
	node4->right = node6;
	//node5->left = NULL;
	//node5->right = NULL;
	//node6->left = NULL;
	//node6->right= NULL;

	return node1;
}

void LaterOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	LaterOrder(root->left);
	LaterOrder(root->right);
	printf("%d ", root->data);
}

int main()
{
	TreeNode* root = CreatTree();
	LaterOrder(root);
	printf("\n");
	return 0;
}

注意事项：

1、建议多画图自己尝试一遍

2、搞懂此时的root是谁以及root->data到底打印的是谁的值，是完成三次遍历的基础

整体代码

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreatTree()
{

	TreeNode* node1 = BuyTreeNode(1);

	TreeNode* node2 = BuyTreeNode(2);

	TreeNode* node3 = BuyTreeNode(3);

	TreeNode* node4 = BuyTreeNode(4);

	TreeNode* node5 = BuyTreeNode(5);

	TreeNode* node6 = BuyTreeNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	//node2->right = NULL;
	//node3->left = NULL;
	//node3->right = NULL;
	node4->left = node5;
	node4->right = node6;
	//node5->left = NULL;
	//node5->right = NULL;
	//node6->left = NULL;
	//node6->right= NULL;

	return node1;
}

void PrevOrder(TreeNode* root)
{
	if(root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void LaterOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	LaterOrder(root->left);
	LaterOrder(root->right);
	printf("%d ", root->data);
}

int main()
{
	TreeNode* root = CreatTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	LaterOrder(root);
	printf("\n");
	return 0;
}

~over~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/235775.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

IDE代码编辑器：CLion 2023.3(WinMac)中文激活版

IDE代码编辑器：CLion 2023.3(WinMac)中文激活版

CLion 2023是一款由JetBrains公司为C/C编程设计的跨平台集成开发环境&#xff08;IDE&#xff09;。它集成了丰富的功能和工具&#xff0c;旨在帮助开发人员更高效地进行C/C编程和调试。 以下是这款软件的一些主要特点和功能&#xff1a; 高效的编程体验&#xff1a;为Mac用户提…
阅读更多...
15、lambda表达式、右值引用、移动语义

15、lambda表达式、右值引用、移动语义

前言 返回值后置 auto 函数名 (形参表) ->decltype(表达式) lambda表达式 lambda表达式的名称是一个表达式 (外观类似函数)&#xff0c;但本质绝非如此 语法规则 [捕获表] (参数表) 选项 -> 返回类型 { 函数体; }lambda表达式的本质 lambda表达式本质其实是一个类…
阅读更多...
供应链管理的“牛鼻子”在哪里？

供应链管理的“牛鼻子”在哪里？

什么是供应链管理&#xff1f; 有个定义&#xff1a;供应链管理是使以核心企业为中心的供应链运作达到最优化&#xff0c;以最小的成本&#xff0c;让供应链从采购开始&#xff0c;到满足最终顾客的所有过程&#xff0c;包括物流、信息流、单证流、资金流等均能高效率运作&…
阅读更多...
Windows 安全基础——NetBIOS篇

Windows 安全基础——NetBIOS篇

Windows 安全基础——NetBIOS篇 1. NetBIOS简介 NetBIOS&#xff08;Network Basic Input/Output System, 网络基本输入输出系统&#xff09;是一种接入服务网络的接口标准。主机系统通过WINS服务、广播及lmhosts文件多种模式&#xff0c;把NetBIOS名解析对应的IP地址&#xf…
阅读更多...
3篇EI论文联合复现：基于数据驱动的综合能源系统多阶段分布鲁棒优化调度程序代码！

3篇EI论文联合复现：基于数据驱动的综合能源系统多阶段分布鲁棒优化调度程序代码！

本程序参考了3篇电力系统TOP-EI期刊&#xff0c;将目前的热点研究数据驱动结合综合综合能源系统&#xff0c;利用分布鲁棒处理不确定性问题&#xff0c;程序中算例丰富&#xff0c;注释清晰&#xff0c;干货满满&#xff0c;小编非常推荐这个程序&#xff0c;下面对程序代码详细…
阅读更多...
【代码+案例】详解SPC相关控制图原理及逻辑代码

【代码+案例】详解SPC相关控制图原理及逻辑代码

Xbar-R图&#xff1a;用于监控样本均值和范围&#xff0c;适合小样本量。Xbar-S图&#xff1a;类似Xbar-R图&#xff0c;但适用于大样本量。p图&#xff1a;用于监控一定时间或样本量内的缺陷比率。np图&#xff1a;类似p图&#xff0c;但用于固定样本量。u图&#xff1a;用于监…
阅读更多...
机器学习算法（9）——集成技术（Bagging——随机森林分类器和回归）

机器学习算法（9）——集成技术（Bagging——随机森林分类器和回归）

一、说明 在这篇文章&#xff0c;我将向您解释集成技术和著名的集成技术之一&#xff0c;它属于装袋技术&#xff0c;称为随机森林分类器和回归。 集成技术是机器学习技术&#xff0c;它结合多个基本模块和模型来创建最佳预测模型。为了更好地理解这个定义&#xff0c;我们需要…
阅读更多...
【C++11(三)】智能指针详解--RAII思想循环引用问题

【C++11(三)】智能指针详解--RAII思想循环引用问题

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:C从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习C   &#x1f51d;&#x1f51d; C11 1. 前言2. 为什么要有智能指针?3. RAII思想…
阅读更多...
.NET 材料检测系统崩溃分析

.NET 材料检测系统崩溃分析

Windbg 分析 1. 到底是哪里的崩溃 一直跟踪我这个系列的朋友应该知道分析崩溃第一个命令就是 !analyze -v &#xff0c;让windbg帮我们自动化异常分析。 0:033> !analyze -v CONTEXT: (.ecxr) rax00000039cccff2d7 rbx00000039c85fc2b0 rcx00000039cccff2d8 rdx000000000…
阅读更多...
水库大坝安全监测参数与设备

水库大坝安全监测参数与设备

智慧水利中&#xff0c;水库大坝的安全监测必不可少。做好水库大坝的安全监测&#xff0c;是确保水库大坝结构安全和预防灾害的重要手段。对于预防灾害、保护人民生命财产安全、优化工程管理、改进工程设计、保护环境资源和提高公众信任等方面有着重要的意义。 水利水库大坝安全…
阅读更多...
酷滴科技出席浦发银行第七届国际金融科技创新大赛

酷滴科技出席浦发银行第七届国际金融科技创新大赛

12月7日&#xff0c;浦发银行全球金融科技创新大赛在上海展开决赛。本届大会以“科技金融&#xff0c;激发创新力量”为主题&#xff0c;聚焦金融行业数字化转型过程中的痛点与难点&#xff0c;旨在探讨新时代下金融科技的新角色、新机遇以及新挑战。酷滴科技CEO张沈分享了酷滴…
阅读更多...
花椒油行业分析：预计2025年市场规模将达到350亿元以上

花椒油行业分析：预计2025年市场规模将达到350亿元以上

近年来&#xff0c;麻辣口味在全国普及&#xff0c;随着火锅、川菜、烤鱼、串串香等麻辣餐饮的发展与扩张&#xff0c;花椒的市场需求也日益增长。实际上&#xff0c;花椒的应用远不止于餐饮市场&#xff0c;其背后是庞大而复杂的产业链。 在政策扶持以及日益旺盛的市场需求(尤…
阅读更多...
MySQL - 聚簇索引和非聚簇索引，回表查询，索引覆盖，索引下推，最左匹配原则

MySQL - 聚簇索引和非聚簇索引，回表查询，索引覆盖，索引下推，最左匹配原则

聚簇索引和非聚簇索引 聚簇索引和非聚簇索引是 InnoDB 里面的叫法 一张表它一定有聚簇索引&#xff0c;一张表只有一个聚簇索引在物理上也是连续存储的 它产生的过程如下&#xff1a; 表中有无有主键索引&#xff0c;如果有&#xff0c;则使用主键索引作为聚簇索引&#xff1b;…
阅读更多...
Java - 线程间的通信方式

Java - 线程间的通信方式

线程通信的方式 线程中通信是指多个线程之间通过某种机制进行协调和交互 线程通信主要可以分为三种方式&#xff0c;分别为共享内存、消息传递和管道流。每种方式有不同的方法来实现 共享内存&#xff1a;线程之间共享程序的公共状态&#xff0c;线程之间通过读-写内存中的公…
阅读更多...
成都工业学院Web技术基础（WEB）实验六：ECMAScript基础语法

成都工业学院Web技术基础（WEB）实验六：ECMAScript基础语法

写在前面 1、基于2022级计算机大类实验指导书 2、代码仅提供参考&#xff0c;前端变化比较大&#xff0c;按照要求&#xff0c;只能做到像&#xff0c;不能做到一模一样 3、图片和文字仅为示例&#xff0c;需要自行替换 4、如果代码不满足你的要求&#xff0c;请寻求其他的…
阅读更多...
吉祥物IP怎么结合动捕设备应用在线下活动？

吉祥物IP怎么结合动捕设备应用在线下活动？

一个好的吉祥物IP&#xff0c;不仅可以为品牌带来传播效果和形象具体化的价值&#xff0c;还可以带来一系列的商业利益。 当吉祥物IP接入惯性动作捕捉系统&#xff0c;即可由真人幕后穿戴动捕设备进行实时驱动&#xff0c;可以通过虚拟数字人直播、数字人短视频、数字人线下活动…
阅读更多...
如何在Ubuntu的Linux系统上安装nacos的2.3.0版本

如何在Ubuntu的Linux系统上安装nacos的2.3.0版本

官方网址链接 home (nacos.io)Nacos 快速开始github代码仓库简单介绍 Nacos是阿里巴巴的产品&#xff0c;现在是SpringCloud中的一个组件&#xff0c;其可以用于服务发现和服务健康监测、动态配置服务、动态DNS服务、服务及其元数据管理。安装包下载地址&#xff1a; Releases …
阅读更多...
Python3开发环境的搭建

Python3开发环境的搭建

1&#xff0c;电脑操作系统的确认 我的是win10、64位的&#xff0c;你们的操作系统可自寻得。 2&#xff0c;Python安装包的下载 &#xff08;1&#xff09;浏览器种输入网址&#xff1a;https://www.python.org 选择对应的系统&#xff08;我的是win10/64位) &#xf…
阅读更多...
面试 JVM 八股文五问五答第一期

面试 JVM 八股文五问五答第一期

面试 JVM 八股文五问五答第一期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1.JVM内存布局 Heap (堆区&#xff09; 堆是 OOM 故障最主要的发生区域。它是内存…
阅读更多...
CRM系统的这些功能助您高效管理客户

CRM系统的这些功能助您高效管理客户

客户管理可以理解为企业收集并利用客户信息&#xff0c;满足客户的需求&#xff0c;从而提升客户价值的过程。CRM系统一直被誉为客户管理的“神器”&#xff0c;下面我们就来说说CRM系统有哪些功能可以管理客户&#xff1f; 1、客户信息管理 CRM可以帮助企业收集客户的基本信…
阅读更多...
最新文章

Copyright @ 2022~2023