链式二叉树的前,中,后序遍历 AND 结点个数及高度等 文末附带全部代码

目录

  • 前言
  • 1. 前序遍历
  • 2. 中序遍历
  • 3. 后续遍历
  • 4. 二叉树结点的个数
  • 5. 二叉树叶子结点个数
  • 6. 二叉树的高度
  • 7. 二叉树第K层结点的个数
  • 8. 二叉树查找值为x的结点
  • 全部代码
  • 总结

正文开始

前言

本文旨在介绍二叉树的链式存储中一些函数的实现

博客主页: 酷酷学!!!

更多文章, 期待关注~

前置说明: 在学习二叉树的基本操作前, 需要先创建一棵二叉树, 然后才能学习相关的基本操作. 由于目前阶段对二叉树结构掌握不够深入, 为了降低大家学习成本, 此处手动快速创建一棵简单的二叉树, 快速进入二叉树操作学习, 等二叉树结构了解查差不多时, 我们反过头来再研究二叉树真正的创建方式.

typedef int BTDatatype;

typedef struct BTNode
{
	BTDatatype data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

BTNode* BuyNode(int x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}


BTNode* CreateTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);


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

	return node1;
}

注意: 上述代码并不是创建二叉树的方式, 真正创建二叉树方式期待后续博客

首先实现下面的方法之前我们先来回顾一下二叉树:

什么是二叉树?

  1. 空树
  2. 非空：根结点，根结点的左子树、根结点的右子树组成的。

在这里插入图片描述

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

1. 前序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

在这里插入图片描述

我们先来看前序遍历:

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。简单来说遍历的顺序为 根 -> 左子树 ->右子树

递归的本质: 拆成当前问题和子问题, 返回条件: 最小规模的子问题

我们可以把大问题化小, 首先拆成根, 左子树, 右子树的结构, 然后左子树 又可以拆成 根 左子树 右子树的结构, 结束条件为树为空树.

代码实现:

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

运行结果:
在这里插入图片描述

前序遍历递归图解：

在这里插入图片描述

如图我们可以看出:

前序遍历依次访问的数据为:
1 2 3 4 5 6
如果加上对空树的访问, NULL简写为N:
1 2 3 N N N 4 5 N N 6 N N

下面为递归展开图, 不太理解的伙伴可以参考:

在这里插入图片描述

2. 中序遍历

中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

即, 每棵树 先访问左子树, 在访问根, 最后访问右子树

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

递归展开图:

在这里插入图片描述

3. 后续遍历

后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

即, 每一棵树,先访问左子树, 在访问右子树, 最后访问根

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

4. 二叉树结点的个数

求二叉树结点的个数, 这里初学者很容易先到使用遍历来求结点个数,如下:

// 错误示范
int TreeSize(BTNode* root)
{
	static int size = 0;
	if (root == NULL)
		return 0;
	else
		++size;

	TreeSize(root->left);
	TreeSize(root->right);

	return size;
}

首先做个铺垫再来讲解这段代码的问题

静态全局变量和静态局部变量的区别在于作用域和生存周期。

静态全局变量： 静态全局变量在整个文件中都是可见的，即其作用域为整个文件。静态全局变量只能被当前文件内的函数访问，其他文件无法访问。静态全局变量的生存周期为整个程序的执行期间，即在程序启动时分配内存，在程序结束时释放内存。

静态局部变量： 静态局部变量只在定义它的函数内部可见，即其作用域为定义它的函数内部。静态局部变量的生存周期为整个程序的执行期间，即在程序启动时分配内存，在程序结束时释放内存。与普通局部变量不同的是，静态局部变量只会在第一次进入函数时初始化一次，之后每次进入函数都会保留上一次的值。

静态全局变量和静态局部变量都可以被修改，但是有一些区别：

静态全局变量： 静态全局变量可以被当前文件内的任何函数修改，因为其作用域为整个文件。其他文件无法直接修改静态全局变量。但是，由于其作用域广泛，可能会被不同函数多次修改，导致程序的可维护性降低。

静态局部变量： 静态局部变量只能在定义它的函数内部被修改，其他函数无法直接修改静态局部变量。由于其作用域限制在函数内部，静态局部变量对于其他函数来说是不可见的，因此可以更好地控制变量的访问权限。此外，静态局部变量在函数调用之间保持其值不变，可以用于在函数调用之间保持状态或者记录某些信息。

因为每次调用函数size都是在栈区开辟的局部变量, 当函数结束后局部变量也会被系统回收, 这里用了static来修饰size, 看似没什么问题, 但是如果多次调用函数问题就来了

在这里插入图片描述
那么如何解决, 我们可以使用全局变量:

int size = 0;
int TreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		++size;

	TreeSize(root->left);
	TreeSize(root->right);

	return size;
}

void TreeSize(BTNode* root, int* psize)
{
	if (root == NULL)
		return 0;
	else
	++(*psize);

	TreeSize(root->left, psize);	
	TreeSize(root->right, psize);
}

但是上述的写法虽然可以, 但是每次调用之前都需要重置size的值,过于麻烦

int size = 0;
TreeSize(root, &size);
printf("TreeSize:%d\n",size);

size = 0;
TreeSize(root, &size);
printf("TreeSize:%d\n", size);

最好的解决方案还是回归本质, 因为二叉树本身就是递归定义的, 我们采用递归的思想, 分而治之, 问题就迎刃而解

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) 
	+ BinaryTreeSize(root->right) + 1;
}

首先分为左子树和右子树, 每一棵树都有左子树和右子树, 我们只需要统计每一棵树的左子树和右子树总结点个数加上自己.为空就等于0, 不为空左子树结点个数加上右子树结点个数, 返回给上一层
在这里插入图片描述

5. 二叉树叶子结点个数

叶子结点的个数, 空树就返回0, 递归的思想, 如果左子树和右子树都是空, 则就是叶子节点, 返回1, 统计左子树和右子树的叶子节点个数即可.

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

6. 二叉树的高度

还是采用递归的思想, 一棵树的高度等于左子树的高度与右子树的高度较高的那个树加+1, 结束条件空树就是0.

在这里插入图片描述

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return left > right ? left + 1 : right + 1;
}

7. 二叉树第K层结点的个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//子问题
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);

将复杂度问题划分为子问题, 每一层即下一层的k-1层结点的个数, 如果k==1则返回1.

在这里插入图片描述

8. 二叉树查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root == x)
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;

}

这里要返回一个结点, 因为是递归调用函数, 所以返回值会逐层返回, 将树划分为子问题, 现在如果为NULL,则返回NULL, 如果找到了就返回该结点, 没找到就调用函数去查找左子树与右子树, 如果左子树找到了就返回左子树的结点不需要去右子树查找了, 如果都没找到则返回NULL.

全部代码

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int BTDatatype;

typedef struct BTNode
{
	BTDatatype data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

BTNode* BuyNode(int x);

void PrevOrder(BTNode* root);
void InOrder(BTNode* root);
void PostOrder(BTNode* root);

//二叉树结点的个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树的高度
int TreeHeight(BTNode* root);

//二叉树第K层结点的个数
int BinaryTreeLevelKSize(BTNode* root ,int k);

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x);

Tree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"

BTNode* BuyNode(int x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

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

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

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

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return left > right ? left + 1 : right + 1;
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root == x)
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;

}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"

BTNode* CreateTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);


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

	return node1;
}


int main()
{
	BTNode* root = CreateTree();
	PrevOrder(root);
	//InOrder(root);
	//PostOrder(root);
	//int size = BinaryTreeSize(root);
	//int size = TreeHeight(root);
	//int size = BinaryTreeLeafSize(root);
	//int size = BinaryTreeLevelKSize(root,3);
	//printf("%d ", size);
	return 0;
}

总结

关于二叉树这块比较复杂, 递归的思路需要清晰, 每一次递归调用的作用是什么, 为什么要这样写, 写代码之前手动画一遍递归调用简图, 只要思路通了, 代码就顺了, 不要觉得是在浪费时间, 因为时间本就是来解决问题的.

完, 感谢关注~

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

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

相关文章

dubbo复习：（9）配置中心的大坑，并不能像spring cloud那样直接从配置中心读取自定义的配置

dubbo复习：（9）配置中心的大坑，并不能像spring cloud那样直接从配置中心读取自定义的配置

配置中心只是为 Dubbo 配置提供管理使用的&#xff08;比如配置服务超时时间等)。不要尝试通过Value类似的方式从dubbo 配置中心(比如nacos、zookeeper、Apollo)来获取数据 https://github.com/apache/dubbo/issues/11200可以在application.yml中主要写注册中心的配置&#xf…
阅读更多...
【LeetCode刷题】滑动窗口思想解决：最大连续1的个数 III、将x减到0的最小操作数

【LeetCode刷题】滑动窗口思想解决：最大连续1的个数 III、将x减到0的最小操作数

【LeetCode刷题】Day 8 题目1&#xff1a;1004.最大连续1的个数 III思路分析&#xff1a;思路1&#xff1a;暴力枚举zero计数器思路2&#xff1a;滑动窗口zero计数器 题目2&#xff1a;1658. 将x减到0的最小操作数思路分析&#xff1a;思路1&#xff1a;暴力枚举思路2&#xff…
阅读更多...
前端中 dayjs 时间的插件使用(在vue 项目中)

前端中 dayjs 时间的插件使用(在vue 项目中)

Day.js中文网 这是dayjs的中文文档 里面包括了使用方法 下面我来详细介绍一下这个插件的使用 Day.js 可以运行在浏览器和 Node.js 中。 一般咱直接是 npm 安装 npm install dayjs 目前应该使用的是Es6 的语法 import dayjs from dayjs 当前时间 直接调用 dayjs() 将返回…
阅读更多...
CobaltStrike渗透框架进阶之扩展脚本和MSF联动

CobaltStrike渗透框架进阶之扩展脚本和MSF联动

CobaltStrike扩展脚本 扩展是Cobaltstrike一个极为重要的模块&#xff0c;它有效地丰盈了cobaltstrike的功能 选择菜单栏的CobaltStrike–>脚本管理器&#xff0c;点击load&#xff0c;然后选择cna扩展文件即可&#xff0c;旁边的unload为去除该扩展&#xff0c;&#xff…
阅读更多...
Octo 精武门？ ：开源的通用机器人模型

Octo 精武门？ ：开源的通用机器人模型

大模型技术论文不断&#xff0c;每个月总会新增上千篇。本专栏精选论文重点解读&#xff0c;主题还是围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调重新阅读。而最新科技&#xff08;Mamba,xLSTM,KAN&#xff09;则提供了大模型领域最新技…
阅读更多...
01主动安全系统

01主动安全系统

“安全”一直是车主对车辆考核的重要指标。车辆安全可以分为从主动安全和被动安全两个方面进行分类。今天就来说说汽车主动安全系统的那些事儿。 01.什么是主动安全系统&#xff1f; 主动安全是指尽量自如地操纵控制汽车的安全系统措施。无论是直线上的制动与加速还是左右打方…
阅读更多...
X2Doris使用指南：界面化数据迁移工具 - 轻松实现整库迁移至Doris

X2Doris使用指南：界面化数据迁移工具 - 轻松实现整库迁移至Doris

什么是X2Doris X2Doris 是 SelectDB 团队开发的&#xff0c;专门用于将各种离线数据迁移到 Apache Doris 中的核心工具&#xff0c;该工具集 自动建 Doris 表 和 数据迁移 为一体&#xff0c;目前支持了 Apache Doris/Hive/Kudu/StarRocks 数据库往 Doris 或 SelectDB Cloud 迁…
阅读更多...
AI预测福彩3D采取888=3策略+和值012路一缩定乾坤测试5月26日预测第2弹

AI预测福彩3D采取888=3策略+和值012路一缩定乾坤测试5月26日预测第2弹

昨天的8883大底成功命中&#xff0c;但是由于昨天杀了对子&#xff0c;结果昨天开了对子&#xff0c;导致最终与中奖号码擦肩而过。今天继续基于8883的大底&#xff0c;使用尽可能少的条件进行缩号&#xff0c;同时&#xff0c;今天将准备两套方案&#xff0c;一套是我自己的条…
阅读更多...
Dockerfile文件详细介绍

Dockerfile文件详细介绍

前言 Dockerfile是一个文本文件&#xff0c;包含了用于构建Docker镜像的所有命令和说明。它定义了容器的运行环境、依赖以及启动方式&#xff0c;是创建Docker镜像的核心部分。 由于制作镜像的过程中&#xff0c;需要逐层处理和打包&#xff0c;比较复杂&#xff0c;所以Docke…
阅读更多...
Day 3：1738. 找出第 K 大的异或坐标值

Day 3：1738. 找出第 K 大的异或坐标值

Leetcode 1738. 找出第 K 大的异或坐标值 给你一个二维矩阵 matrix 和一个整数 k &#xff0c;矩阵大小为 m x n 由非负整数组成。 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 < i < a < m 且 0 < j < b < n 的元素 matrix[i][j]&#xff08;下标从 0 开始计…
阅读更多...
SVN创建分支，分支合并，切换分支。通俗易懂

SVN创建分支，分支合并，切换分支。通俗易懂

1、首先在svnbucket.com远程仓库上创建项目&#xff0c;这里我创建了个测试demo&#xff1a; 2、先把svn仓库的项目检出到自己的文件夹&#xff0c;我这里是demo001文件夹&#xff0c;此时并没有创建truck, branches, tags这三个目录&#xff1a; 3、 在demo001文件夹里新建tru…
阅读更多...
电量计量芯片HLW8110的前端电路设计与误差分析校正.pdf 下载

电量计量芯片HLW8110的前端电路设计与误差分析校正.pdf 下载

电量计量芯片HLW8110的前端电路设计与误差分析校正.pdf 下载地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1vlCtC3LGFMzYpSUUDY-tEg 提取码&#xff1a;8110
阅读更多...
氢燃料电池汽车行业发展

氢燃料电池汽车行业发展

文章目录 前言 市场分布 整车销售 发动机配套 氢气供应 发展动能 参考文献 前言 见《氢燃料电池技术综述》 见《燃料电池工作原理详解》 见《燃料电池发电系统详解》 见《燃料电池电动汽车详解》 市场分布 纵观全球的燃料电池汽车市场&#xff0c;截至2022年底&#xff…
阅读更多...
微信小程序基础 --模板语法（4）

微信小程序基础 --模板语法（4）

模板语法 1、wxml视图结构 1.1 概述 开发文档&#xff1a;https://developers.weixin.qq.com/miniprogram/dev/framework/quickstart/code.html#WXML-%E6%A8%A1%E6%9D%BF 从事过网页编程的人知道&#xff0c;网页编程采用的是 HTML CSS JS 这样的组合&#xff0c;其中 HT…
阅读更多...
2010-2024年别克维修手册和电路图线路接线图资料更新

2010-2024年别克维修手册和电路图线路接线图资料更新

经过整理&#xff0c;2010-2024年别克汽车全系列已经更新至汽修帮手资料库内&#xff0c;覆盖市面上99%车型&#xff0c;包括维修手册、电路图、新车特征、车身钣金维修数据、全车拆装、扭力、发动机大修、发动机正时、保养、电路图、针脚定义、模块传感器、保险丝盒图解对照表…
阅读更多...
类的内存对齐位段位图布隆过滤器哈希切割一致性哈希

类的内存对齐位段位图布隆过滤器哈希切割一致性哈希

文章目录 一、类的内存对齐1.1规则1.2原因 二、位段2.1介绍2.2内存分配问题2.3跨平台问题2.4使用的注意事项 三、位图的应用3.1 给40亿个不重复的无符号整数&#xff0c;找给定的一个数。&#xff08;int的范围可以到达42亿多&#xff09;3.2 给定100亿个整数&#xff0c;设计算…
阅读更多...
Linux文件系统原理

Linux文件系统原理

Linux文件系统 冯诺依曼在1945年提出计算机的五大组成部分 运算器&#xff1a;CPU 控制器&#xff1a;CPU 存储器&#xff1a;内存和硬盘 输入设备&#xff1a;鼠标、硬盘 输出设备&#xff1a;显示器一、硬盘结构 机械硬盘结构 扇区&#xff1a;硬盘的最小存储单位&#xff…
阅读更多...
【JAVASE】抽象类

【JAVASE】抽象类

1、抽象类概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是用来描绘对象的&#xff0c;如果一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类。比如&#xff1a; 说明&a…
阅读更多...
基础IO用户缓冲区 、inode、硬软链接【Linux】

基础IO用户缓冲区 、inode、硬软链接【Linux】

文章目录 用户缓冲区磁盘磁盘分区EXT2文件系统的存储方案 inode软链接硬链接 用户缓冲区 代码一&#xff1a; 1 #include<stdio.h>2 #include<unistd.h>3 #include<string.h> 4 int main()5 {6 const char * fstr &…
阅读更多...
Linux下的调试器 ： gdb指令详解

Linux下的调试器 ： gdb指令详解

&#x1fa90;&#x1fa90;&#x1fa90;欢迎来到程序员餐厅&#x1f4ab;&#x1f4ab;&#x1f4ab; 主厨&#xff1a;邪王真眼 主厨的主页&#xff1a;Chef‘s blog 所属专栏&#xff1a;青果大战linux 总有光环在陨落&#xff0c;总有新星在闪烁 gdb是什么 gdn是linu…
阅读更多...
最新文章

Copyright @ 2022~2023