【数据结构初阶】链式二叉树接口实现超详解

文章目录

  • 1. 节点定义
  • 2. 前中后序遍历
    • 2. 1 遍历规则
    • 2. 2 遍历实现
    • 2. 3 结点个数
      • 2. 3. 1 二叉树节点个数
      • 2. 3. 2 二叉树叶子节点个数
      • 2. 3. 3 二叉树第k层节点个数
    • 2. 4 二叉树查找值为x的节点
    • 2. 5 二叉树层序遍历
    • 2. 6 判断二叉树是否是完全二叉树
  • 3. 二叉树性质


1. 节点定义

用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址,其基本结构如下:

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;				//数据
	struct BinaryTreeNode* left;	//左孩子
	struct BinaryTreeNode* right;	//右孩子
}BTNode;

链式二叉树的创建方式比较复杂,为了更好地对接口进行调试,我们先手动创建一棵链式二叉树进行测试:

//创建节点
BTNode* BuyBTNode(int val)
{
	BTNode * newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode * CreateTree()
{
	BTNode * n1 = BuyBTNode(1);
	BTNode * n2 = BuyBTNode(2);
	BTNode * n3 = BuyBTNode(3);
	BTNode * n4 = BuyBTNode(4);
	BTNode * n5 = BuyBTNode(5);
	BTNode * n6 = BuyBTNode(6);
	BTNode * n7 = BuyBTNode(7);
	//手动将他们连接起来成为一棵二叉树
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	n5->left = n7;
	
	return n1;
}

接下来就可以用这棵二叉树对接口进行测试。

2. 前中后序遍历

二叉树不同于之前的顺序结构,不能直接进行依次遍历,必须按照一定的规则进行遍历
注:堆也是一种二叉树,但是堆不能进行遍历,所以没有这方面的考虑。
另外二叉树的链式结构是一个递归的结构,几乎所有的接口实现都需要用到递归的思想。
1

2. 1 遍历规则

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

  1. 前序遍历(Preorder Traversal,亦称先序遍历):访问根结点的操作发生在遍历其左右子树之前
    访问顺序为:根结点、左子树、右子树
  2. 中序遍历(lnorder Traversal):访问根结点的操作发生在遍历其左右子树中间
    访问顺序为:左子树、根结点、右子树
  3. 后序遍历(Postorder Traversal):访问根结点的操作发生在遍历其左右子树之后
    访问顺序为:左子树、右子树、根结点

我们以前序遍历解释一下怎么遍历:
2
从根节点1开始遍历,先输出根节点数据1,然后来到左孩子2,输出2,来到2的左孩子3,输出3,来到3的左孩子NULL,回退至3,来到3的右孩子NULL,再回退,3节点遍历完毕,回退至2,来到2的右节点NULL,回退至2,2节点遍历完毕,回退至1,来到1的右孩子4,先输出4,再来到4的左孩子4,输出4,遍历左右俩孩子都为空,回退至上面的4,来到4的右孩子5,输出5后,俩孩子都为空,再最终回退至1,根节点遍历完成,该二叉树遍历完成。
前序遍历结果:123456
中序遍历结果:321546
后序遍历结果:315641

2. 2 遍历实现

在实现时,我们可以把每一个孩子都看成一个二叉树的根节点,以方便递归遍历。

//前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
	if (!root)
		return;
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
//后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (!root)
		return;
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%d ", root->data);
}
//中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (!root)
		return;
	BinaryTreePrevOrder(root->left);
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->right);
}

2

2. 3 结点个数

2. 3. 1 二叉树节点个数

int BinaryTreeSize(BTNode* root);

二叉树中只有结点,没有把数据个数存储起来,那么我们要怎么获取二叉树中元素的个数呢?
有两种思路,一个是创建全局变量,然后通过任意一种遍历方式遍历二叉树,每遍历一次都让这个变量++,那么就能得到节点的个数了,但是这样会带来两个问题:

  1. 全局变量每次都要归0,但是由于是递归进行遍历的,所以需要写一个子函数用于递归
  2. 在函数内部调用全部变量可能会存在危险,因为这个变量是任何函数都能访问并修改的

基于这样的原因,我们不采用这个方式。
而是通过计算这个节点本身+左子树节点的个数+右子树节点的个数的方式进行递归。

int BinaryTreeSize(BTNode* root)
{
	if (!root)
		return 0;
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);	//1就是该节点本身,再加上左右两棵子树
}

2. 3. 2 二叉树叶子节点个数

int BinaryTreeLeafSize(BTNode* root);

叶子节点的特点就是root->left == NULL && root->right == NULL,所以只要加上一个判断是否要+1,其他的就和计算节点个数的思路是一样的。

int BinaryTreeLeafSize(BTNode* root)
{
	//如果是叶子节点,就没必要继续向下传递了,直接回归就可以了
	if (!root)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2. 3. 3 二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k);

在传递时增加一个参数k,来判断递归到哪一层了,如果是目标层数,就+1回归,其他与计算二叉树叶子节点个数思路一致。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//同理,到目标层数之后就不需要继续向下传递了
	if (!root)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

2. 4 二叉树查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

在二叉树中遍历并对比数据,如果找到了就返回这个节点的指针,没找到就返回NULL

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->data == x)
		return root;
	//需要分别判断左右子树中有没有这个数据
	//左
	BTNode* leftfind = BinaryTreeFind(root->left,x);
	if (leftfind)
		return leftfind;
	//右
	BTNode* rightfind = BinaryTreeFind(root->right,x);
	if (rightfind)
		return rightfind;
	//没找到,返回空
	return NULL;
}

2. 5 二叉树层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历
设二叉树的根结点所在层数为1,层序遍历就是从所在二叉树的根结点出发,首先访问第一层的根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
实现层序遍历需要额外借助队列这一数据结构。
1
层序遍历就是一层一层地从左到右地进行遍历,比如上面这棵二叉树的层序遍历就是:1 2 3 4 5 6 7

大致思路为:创建一个数据类型为BTNode*的队列,先将根节点入队列,然后分别将它的左右孩子入队列,接着出队列一次。然后把队头的左右孩子(如果不为NULL)入队列,再出队列一次,每次出队列前都要把它的值打印出来,循环以上过程直到队列为空。

注:这里的队列不再实现,可以看这篇博客。

void BinaryTreeLevelOrder(BTNode* root)
{
	//二叉树判空
	if (!root)
		printf("null\n");
	//创建队列并初始化
	Queue qu;
	QueueInit(&qu);
	//把根节点入队列
	QueuePush(&qu,  root);
	while (!QueueEmpty(&qu))
	{
		//将队头的左右子树入队列,并将队头数据打印,再出队列一次
		BTNode* tmp = QueueFront(&qu);
		QueuePop(&qu);
		printf("%d ", tmp->data);
		if (tmp->left)
			QueuePush(&qu, tmp->left);
		if (tmp->right)
			QueuePush(&qu, tmp->right);
	}
	//销毁队列
	QueueDestroy(&qu);
	printf("\n");
}

2. 6 判断二叉树是否是完全二叉树

bool BinaryTreeComplete(BTNode* root);

完全二叉树的特点是第X层没有完全放满时,X+1层不能有节点,且没有满的层的节点必须是从左往右排布的。

我们可以借助层序遍历来判断二叉树是不是完全二叉树。
步骤为:就算节点为空也要入队列,直到出队列时遇到了空节点时,开始连续出队列,如果队列中剩下的元素中有非空的节点,就说明不是完全二叉树

我们以这棵二叉树为例:
2
当轮到4的左孩子(尽管不存在,但先这么理解一下)出队列时,开始不再入队列,只出队列并判断是否为空,这时队列中还有4的右节点7,那就判断出来了二叉树不是完全二叉树。

如果在第一次出队列的为空节点的之后的节点都是空节点(比如上面这个二叉树没有节点7),那就是完全二叉树。

bool BinaryTreeComplete(BTNode* root)
{
	assert(root);
	Queue qu;
	QueueInit(&qu);
	QueuePush(&qu, root);
	while (!QueueEmpty(&qu))
	{
		BTNode* tmp = QueueFront(&qu);
		//如果出队列的是空节点,就停止这个循环
		if (!tmp)
			break;
		QueuePop(&qu);
		QueuePush(&qu, tmp->left);
		QueuePush(&qu, tmp->right);
	}
	//这个循环只出不入
	while (!QueueEmpty(&qu))
	{
		//如果队列中还有空节点,就说明不是完全二叉树
		if (QueueFront(&qu))
		{
			QueueDestroy(&qu);
			return false;
		}
		QueuePop(&qu);
	}
	QueueDestroy(&qu);
	return true;
}

3. 二叉树性质

  1. 对任何一棵二叉树,如果度为 0 的叶结点个数为n0,度为 2 的分支结点个数为n2 ,则有
    n0 = n2+1
    2
    证明:
    假设一个二叉树有 a 个度为 2 的节点,b 个度为 1 的节点,c 个叶节点,则这个二叉树的边数是 2a+b
    另一方面,由于共有 a+b+c 个节点,所以边数等于 a+b+c-1
    结合上面两个公式:
    即 2a+b = a+b+c-1,即 a=c-1

题目练习

  1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
    A 不存在这样的二叉树
    B 200
    C 198
    D 199
    有199个度为2的节点,那么在二叉树中,度为0的节点有199+1也就是200个,选B。

  2. 在具有 2n 个结点的完全二叉树中,叶子结点个数为()
    A n
    B n+1
    C n-1
    D n/2
    设叶子节点有x个,那么度为2的节点为x-1个。有2n个节点,所以度为1的节点有2n-2x+1条,而完全二叉树中度为1的节点只有0或1个,但是这个二叉树的结点个数为偶数(由于根节点有1个,而其他的除了最后一层的结点个数都是偶数),所以度为1的结点个数为1。解方程2n-2x+1=1就可以得出x=n。选A。

  3. 一棵完全二叉树的结点数位为531个,那么这棵树的高度为()
    A 11
    B 10
    C 8
    D 12
    完全二叉树每一层的节点个数为2n-1个,那么根据等比数列的求和公式,完全二叉树前n层的节点个数为2n-1,解方程2n-1>=531可得,n为10,选B。

  4. 一个具有767个结点的完全二叉树,其叶子结点个数为()
    A 383
    B 384
    C 385
    D 386
    设叶子节点有x个,那么度为2的节点为x-1个,度为1的节点为768-2x个,通过第2题的分析我们可知度为1的节点为0个,就可以算出x=384,选B。

数据结构初阶的二叉树就到这里,想必你会发现这个二叉树我们没有实现插入删除的接口,因为二叉树的插入删除使用C语言实现过于复杂,会在高阶数据结构中讲解。

谢谢你的阅读,喜欢的话来个点赞收藏评论关注吧!
我会持续更新更多优质文章

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=10p1y5y691zy4

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

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

相关文章

推荐一款开源的Redis桌面客户端

TinyRDM 是一个现代化的、轻量级的跨平台 Redis 桌面客户端,能在 Mac、Windows 和 Linux 系统上使用。它有着现代化的设计风格,界面既简洁又清晰,操作起来方便又高效。不管是刚开始接触的新手,还是经验丰富的开发者,都…

软考(9.22)

1 在浏览器的地址栏中输入xxxyftp.abc.can.cn,在该URL中( )是要访问的主机名。 A.xxxyftp B.abc C.can D.cn 协议://主机名.域名.域名后缀或IP地址(:端口号)/目录/文件名。 本题xxxyftp是主机名,选择A选项。 2 假设磁盘块与缓冲区大小相同,…

WPF 的TreeView的TreeViewItem下动态生成TreeViewItem

树形结构仅部分需要动态生成TreeViewItem的可以参考本文。 xaml页面 <TreeView MinWidth"220" ><TreeViewItem Header"功能列表" ItemsSource"{Binding Functions}"><TreeViewItem.ItemTemplate><HierarchicalDataTempla…

一.python入门

gyp的读研日记&#xff0c;哈哈哈哈&#xff0c;&#x1f642;&#xff0c;从复习python开始&#xff0c; 目录 1.python入门 1.1 Python说明书 1.2 Python具备的功能 1.3 学习前提 1.4 何为Python 1.5 编程语言 2.Python环境搭建 2.1 开发环境概述 2.2 Python的安装与…

C++: unordered系列关联式容器

目录 1. unordered系列关联式容器1.1 unordered_map1.2 unordered_set 2. 哈希概念3. 哈希冲突4. 闭散列5. 开散列 博客主页: 酷酷学 感谢关注!!! 正文开始 1. unordered系列关联式容器 在C98中&#xff0c;STL提供了底层为红黑树结构的一系列关联式容器&#xff0c;在查询时…

【论文阅读】Grounding Language with Visual Affordances over Unstructured Data

Abstract 最近的研究表明&#xff0c;大型语言模型&#xff08;llms&#xff09;可以应用于将自然语言应用于各种各样的机器人技能。然而&#xff0c;在实践中&#xff0c;学习多任务、语言条件机器人技能通常需要大规模的数据收集和频繁的人为干预来重置环境或帮助纠正当前的…

Pyspark dataframe基本内置方法(5)

文章目录 Pyspark sql DataFrame相关文章toDF 设置新列名toJSON row对象转换json字符串toLocallterator 获取迭代器toPandas 转换python dataframetransform dataframe转换union unionALL 并集不去重&#xff08;按列顺序&#xff09;unionByName 并集不去重&#xff08;按列名…

力扣234 回文链表 Java版本

文章目录 题目描述代码 题目描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为 回文链表 。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true 示例 2&…

Mac电脑上最简单安装Python的方式

背景 最近换了一台新的 MacBook Air 电脑&#xff0c;所有的开发软件都没有了&#xff0c;需要重新配环境&#xff0c;而我现在最常用的开发程序就是Python。这篇文章记录一下我新Mac电脑安装Python的全过程&#xff0c;也给大家一些思路上的提醒。 以下是我新电脑的配置&…

初识模版!!

初识模版 1.泛型编程1.1 如何实现一个交换函数呢&#xff08;使得所有数据都可以交换&#xff09;&#xff1f;1.2 那可以不可以让编译器根据不同的类型利用该模子来生成代码呢&#xff1f; 2.模版类型2.1 模版概念2.2 函数模版的原理2.3 函数模板的实例化2.4 模板参数的匹配原…

如何在openEuler上安装和配置openGauss数据库

本文将详细介绍如何在openEuler 22.03 LTS SP1上安装和配置openGauss数据库&#xff0c;包括数据库的启动、停止、远程连接配置等关键步骤。 1、安装 使用OpenEuler-22.03-LTS-SP1-x64版本的系统&#xff0c;通过命令行安装openGauss数据库。 1.1、确保系统软件包索引是最新…

2024最受欢迎的3款|数据库管理和开发|工具

1.SQLynx&#xff08;原SQL Studio&#xff09; 概述&#xff1a; SQLynx是一个原生基于Web的SQL编辑器&#xff0c;由北京麦聪软件有限公司开发。它最初被称为SQL Studio&#xff0c;后改名为SQLynx&#xff0c;支持企业的桌面和Web数据库管理。SQLynx支持所有流行的数据库&a…

lettuce引起的Redis command timeout异常

项目使用Lettuce&#xff0c;在自己的环境下跑是没有问题的。在给客户做售前压测时&#xff0c;因为客户端环境比较恶劣&#xff0c;service服务和中间件服务不在同一机房。服务启动后不一会就会出现Redis command timeout异常。 经过差不多两周的追查&#xff0c;最后没办法把…

Fyne ( go跨平台GUI )中文文档-Fyne总览(二)

本文档注意参考官网(developer.fyne.io/) 编写, 只保留基本用法 go代码展示为Go 1.16 及更高版本, ide为goland2021.2​​​​​​​ 这是一个系列文章&#xff1a; Fyne ( go跨平台GUI )中文文档-入门(一)-CSDN博客 Fyne ( go跨平台GUI )中文文档-Fyne总览(二)-CSDN博客 Fyne…

本地生活商城开发搭建 同城O2O线上线下推广

同城本地化商城目前如火如荼&#xff0c;不少朋友咨询本地生活同城平台怎么开发&#xff0c;今天商淘云与大家分享同城O2O线上商城的设计和开发。 本地生活商城一般会涉及到区域以及频道类&#xff0c;一般下单需要支持用户定位、商家定位&#xff0c;这样利于用户可以快速找到…

Leetcode 反转链表

使用递归 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class S…

音频3A——初步了解音频3A

文章目录 前言一、3A使用的场景和原理1.AEC2.AGC3.ANS/ANR4.硬件3A和软件3A的区别1&#xff09;层级不同2&#xff09;处理顺序不同3&#xff09;优缺点 5.处理过程 二、3A带来的问题三、开源3A算法总结 前言 在日常的音视频通话过程中&#xff0c;说话的双端往往会面对比较复…

Davinci 大数据可视化分析

Davinci 大数据可视化分析 一、Davinci 架构设计1.1 Davinci定义1.2 Davinci 应用场景 二、Davinci 安装部署2.1 部署规划2.2 前置环境准备2.3 Davinci部署2.3.1 物料准备2.3.2 安装配置 2.4 环境变量配置2.5 初始化数据库2.5.1 创建数据库及用户 2.5.2 建表2.6 初始化配置 三、…

Java反射机制入门:解锁运行时类信息的秘密

反射技术&#xff1a; 其实就是对类进行解剖的技术 类中有什么&#xff1f;构造方法 成员方法成员变量 结论&#xff1a;反射技术就是把一个类进行了解剖&#xff0c;然后获取到 构造方法、成员变量、成员方法 反射技术的应用案例&#xff1a; idea框架技术&#xff1a;Spr…

网络安全-ssrf

目录 一、环境 二、漏洞讲解 三、靶场讲解 四、可利用协议 4.1 dict协议 4.2 file协议 4.3 gopher协议 五、看一道ctf题吧&#xff08;长亭的比赛&#xff09; 5.1环境 5.2开始测试 ​编辑 一、环境 pikachu&#xff0c;这里我直接docker拉取的&#xff0c;我只写原…