初阶数据结构：二叉树（补充扩展）

目录

  • 1. 堆排序
    • 1.1补充：建堆的时间复杂度
    • 1.2 堆排序：升序与降序
  • 2. TopK问题
  • 3. 二叉树的链式结构及其遍历方式
    • 3.1 二叉树的链式结构
    • 3.2 二叉树的前序遍历
    • 2.2 二叉树的中序遍历
    • 2.3 后序遍历
    • 2.4 层序遍历
  • 4. 二叉树OJ练习
    • 4.1 单值二叉树
    • 4.2 判断两棵二叉树是否相等
    • 4.3 判断对称二叉树
    • 4.4 另一棵二叉树的子树
    • 4.5 二叉树的构建与销毁
    • 4.6 判断二叉树是否为完全二叉树
    • 4.7 补充练习
      • 4.7.1 二叉树的节点数
      • 4.7.2 二叉树的叶子节点数
      • 4.7.3 二叉树的第K层结点数
      • 4.7.4 查找二叉树中为x值的结点

1. 堆排序

1.1补充：建堆的时间复杂度

这里使用满二叉树近似计算，向下调整法建堆的时间复杂度：

在这里插入图片描述

等比数列求和，得需调整n - log(n + 1)，时间复杂度为O(n)

1.2 堆排序：升序与降序

思路：我们先建堆，然后将堆顶（堆顶元素总是为最大或最小）的元素与尾部元素交换，size–，然后向下调整，直至堆为空。

  1. 排升序，建大堆（大堆的父亲结点都大于小堆）
  2. 排降序，建小堆

代码实现如下：

void HeapAdjustDown(int* arr, int n, int parent)
{
	//n为元素个数
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}

		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int arr[] = { 27,15,18,28,34,65,49,25,37 };
//向下调整建堆
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	HeapAdjustDown(arr, n, i);
}

ArrPrint(arr, n);

//交换首尾元素，size--，再向下调整
int size = n;
while (size)
{
	swap(&arr[0], &arr[size - 1]);
	size--;
	HeapAdjustDown(arr, size, 0);
}

2. TopK问题

当数据量很大时，且为乱序，数据无法一下全部加载到内存中，所以整体排序无法得出最大或最小的前K个数，那么，如何快速得出前K个最大/最小数。

思路：
先于数据首部建一个大小为K的

  1. 得出最大，建小堆
  2. 得出最小，建大堆

然后，再将剩余的N- K个数据与堆顶元素比较

  1. 当需要最大的数时，若比较元素大于堆顶元素，则交换二者再进行向下调整。
  2. 当需要最小的数时，若比较元素小于堆顶元素，则交换二者再进行向下调整。
void HeapAdjustDown2(int* arr, int n, int parent)
{
	//n为元素个数
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}

		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void TopK(int* arr, int k, int n)
{
	//筛选k个最大的数
	//在数据顶部建一个大小为k的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		HeapAdjustDown2(arr, k, i);
	}

	//若遍历到大于堆顶的元素，交换并向下调整
	for (int j = k; j < n; j++)
	{
		if (arr[j] > arr[0])
		{
			swap(&arr[j], &arr[0]);
			HeapAdjustDown2(arr, k, 0);
		}
	}
}

3. 二叉树的链式结构及其遍历方式

3.1 二叉树的链式结构

在前面的学习中，我们已经了解到，二叉树的结构由三部分组成根，左子树，右子树。

在这里插入图片描述

当我们使用链式存储的方式构建二叉树时，其结点的结构定义如下：

typedef struct TreeNode
{
	int val;
	//左子树指针
	struct TreeNode* left;
	//右子树指针
	struct TreeNode* right;
}

根据逻辑遍历的方式顺序不同，二叉树的遍历方式分为四种：前序，中序，后序，层序

3.2 二叉树的前序遍历

  1. 遍历逻辑顺序：根结点，左子树，右子树（根左右）
  2. 题目链接：
    前序遍历
void preorder_part(struct TreeNode* root, int* arr, int* size)
{
    if(root == NULL)
    {
        return;
    }

    arr[*size] = root->val;
    (*size)++;
    preorder_part(root->left, arr, size);
    preorder_part(root->right, arr, size);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //根左右
    //为空树时，不反回空指针
    //返回数组
    
    *returnSize = 0;
    int* arr = (int*)malloc(100 * sizeof(int));
    preorder_part(root, arr, returnSize);

    return arr;
}

2.2 二叉树的中序遍历

  1. 遍历逻辑顺序：左根右
  2. 题目链接：
    中序遍历
void inorder_part(struct TreeNode* root, int* arr, int* size)
{
    if(root == NULL)
    {
        return;
    }

    inorder_part(root->left, arr, size);
    arr[*size] = root->val;
    (*size)++;
    inorder_part(root->right, arr, size);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{
    *returnSize = 0;
    int* arr = (int*)malloc(100 * sizeof(int));
    inorder_part(root, arr, returnSize);

    return arr;    
}

2.3 后序遍历

  1. 遍历逻辑顺序：左右根
  2. 题目链接：
    后序遍历
void postorder_part(struct TreeNode* root, int* arr, int* size)
{
    if(root == NULL)
    {
        return;
    }

    postorder_part(root->left, arr, size);
    postorder_part(root->right, arr, size);
    arr[*size] = root->val;
    (*size)++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{
    *returnSize = 0;
    int* arr = (int*)malloc(100 * sizeof(int));
    postorder_part(root, arr, returnSize);

    return arr;        
}

2.4 层序遍历

遍历逻辑：依次按层进行遍历（利用队列存储子节点）

void LevelOrder(TreeNode* root)
{
	Queue q1;
	QueueInit(&q1);
	QueuePush(&q1, root);

	TreeNode* top = QueueFront(&q1);
	
	while (!QueueEmpty(&q1))
	{
		if (top)
		{
			QueuePush(&q1, top->left);
			QueuePush(&q1, top->right);
		}
		
		if (top)
		{
			printf("%c ", top->val);
		}
		else
		{
			printf("NULL ");
		}

		QueuePop(&q1);
		if (!QueueEmpty(&q1))
		{
			top = QueueFront(&q1);
		}
	}
}

4. 二叉树OJ练习

4.1 单值二叉树

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    单值二叉树
  3. 思路：任选一种遍历方式遍历整个二叉树，同时判断左右孩子结点的值等于父亲结点的值
bool isUnivalTree(struct TreeNode* root) 
{
    if(root == NULL)
    {
        return true;
    }

    if(root->left && root->val != root->left->val)
    {
        return false;
    }

    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    
    return isUnivalTree(root->left) && isUnivalTree(root->right);    
}

4.2 判断两棵二叉树是否相等

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    判断两颗二叉树是否相等
    3 . 思路：按同样顺序遍历两棵树，同时判断
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //调整逻辑顺序，不出现越界情况
    //二者都为NULL
    if(p == NULL && q == NULL)
    {
        return true;
    }

    //有一个为NULL
    if(p && q == NULL)
    {
        return false;
    }

    if(q && p == NULL)
    {
        return false;
    }

    //都不为NULL
    if(p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

4.3 判断对称二叉树

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    对称二叉树
  3. 思路：按照对称的遍历方式，遍历判断二叉树的左右子树
bool order_part(struct TreeNode* left, struct TreeNode* right)
{
    if(left == NULL && right == NULL)
    {
        return true;
    }

    if(left && right == NULL)
    {
        return false;
    }

    if(right && left == NULL)
    {
        return false;
    }

    if(left->val != right->val)
    {
        return false;
    }

    return order_part(left->left, right->right) && order_part(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) 
{
    
    return order_part(root->left, root->right);
}

4.4 另一棵二叉树的子树

1.题目信息：
在这里插入图片描述
2. 题目链接：
另一颗树的子树
3. 思路：遇到与配对子树的根节点相同的结点即开始配对，直至遍历完整个树。
4. 注：将逻辑，语言转换（翻译）为代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //调整逻辑顺序，不出现越界情况
    //二者都为NULL
    if(p == NULL && q == NULL)
    {
        return true;
    }

    //有一个为NULL
    if(p && q == NULL)
    {
        return false;
    }

    if(q && p == NULL)
    {
        return false;
    }

    //都不为NULL
    if(p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root == NULL)
    {
        return false;
    }

    if(root->val == subRoot->val && isSameTree(root, subRoot))
    {
        return true;
    }

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

4.5 二叉树的构建与销毁

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接：
    二叉树的构建与遍历
  3. 先创建根结点，再依次创建左子树，右子树
typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

void inorder_part(struct TreeNode* root, char* arr, int* size)
{
	if (root == NULL)
	{
		return;
	}

	inorder_part(root->left, arr, size);
	arr[*size] = root->val;
	(*size)++;
	inorder_part(root->right, arr, size);
}

char* inorderTraversal(struct TreeNode* root, int* returnSize)
{
	//根左右
	//为空树时，不反回空指针
	//返回数组

	*returnSize = 0;
	char* arr = (char*)malloc(100 * sizeof(int));
	inorder_part(root, arr, returnSize);

	return arr;
}

TreeNode* BuyTreeNode(char val)
{
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	
	newnode->val = val;
	newnode->left = newnode->right = NULL;

	return newnode;
}

TreeNode* BinaryTreeCreate(char* a, int n, int* pi)
{
	TreeNode* root = NULL;

	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	if (a[*pi] != '#')
	{
		root = BuyTreeNode(a[*pi]);
	}
	(*pi)++;

	root->left = BinaryTreeCreate(a, n, pi);
	root->right = BinaryTreeCreate(a, n, pi);

	return root;
}

int main()
{
	char* a = (char*)malloc(100 * sizeof(char));
    char str;
    int count = 0;
    while(scanf("%c", &str) != EOF)
    {
        a[count++] = str;
    }

	int i = 0;
	TreeNode* root = BinaryTreeCreate(a, strlen(a), &i);
	
	int returnSize = 0;
	char* ret = inorderTraversal(root, &returnSize);

	for (int j = 0; j < returnSize; j++)
	{
		printf("%c ", ret[j]);
	}

    return 0;
}

二叉树的销毁：

void BinaryTreeDestory(TreeNode* root)
{
	//后序遍历
	if (root == NULL)
	{
		return;
	}

	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

4.6 判断二叉树是否为完全二叉树

思路：使用层序遍历，如果出现NULL后，又出现非NULL指针，那么此树就不是完全二叉树，反之，则是。

int BinaryTreeComplete(TreeNode* root)
{
	//层序遍历判断是否为完全二叉树
	Queue q1;
	QueueInit(&q1);
	QueuePush(&q1, root);

	TreeNode* top = QueueFront(&q1);
	//标志有NULL指针出现
	int count = 0;

	while (!QueueEmpty(&q1))
	{
		if (top)
		{
			QueuePush(&q1, top->left);
			QueuePush(&q1, top->right);
		}
		
		if (top == NULL)
		{
			count++;
		}

		if (count && top)
		{
			return 0;
		}

		QueuePop(&q1);
		if (!QueueEmpty(&q1))
		{
			top = QueueFront(&q1);
		}
	}

	return 1;
}

4.7 补充练习

4.7.1 二叉树的节点数

// 二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{
	//根结点 + 左子树结点 + 右子树结点

	if (root == NULL)
	{
		return 0;
	}

	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

4.7.2 二叉树的叶子节点数

// 二叉树叶子节点个数
int BinaryTreeLeafSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

4.7.3 二叉树的第K层结点数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(TreeNode* root, int k)
{
	if (k == 0)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

4.7.4 查找二叉树中为x值的结点

// 二叉树查找值为x的节点
TreeNode* BinaryTreeFind(TreeNode* root, char x)
{
	//没找到
	if (root == NULL)
	{
		return NULL;
	}
	
	//找到了
	if (root->val == x)
	{
		return root;
	}
	
	//在左侧找
	TreeNode* left = BinaryTreeFind(root->left, x);
	//在右侧找
	TreeNode* right = BinaryTreeFind(root->right, x);
	
	if (left)
	{
		return left;
	}

	return right;
}

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

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

相关文章

three.js如何实现简易3D机房?(一)基础准备-上

three.js如何实现简易3D机房?(一)基础准备-上

目录 一、tips 二、功能说明 1.模型初始化 2.功能交互 三、初始化准备 1.目录结构 2.创建三要素 3.创建轨道控制器 4.初始化灯光 5.适配 6.循环渲染 一、tips 1.three.js入门的相关基础性知识就不在此过多赘述了&#xff0c;可以自行提前了解 three.js docs&…
阅读更多...
PyTorch深度学习实战（38）——StyleGAN详解与实现

PyTorch深度学习实战（38）——StyleGAN详解与实现

PyTorch深度学习实战&#xff08;38&#xff09;——StyleGAN详解与实现 0. 前言1. StyleGAN1.1 模型介绍1.2 模型策略分析 2. 实现 StyleGAN2.1 生成图像2.2 风格迁移 小结系列链接 0. 前言 StyleGAN (Style-Generative Adversarial Networks) 是生成对抗网络 (Generative Ad…
阅读更多...
基于Docker部署本地ChatGPT环境

基于Docker部署本地ChatGPT环境

基于Docker部署本地ChatGPT环境 一、拉取镜像 docker pull pengzhile/pandora二、运行镜像 docker run -e PANDORA_CLOUDcloud -e PANDORA_SERVER0.0.0.0:8899 -p 8899:8899 -d pengzhile/pandora三、查看容器是否启动成功 docker ps四、登录 http://IP:8899 这里有两种方…
阅读更多...
原始手写helloworld并打jar包允许

原始手写helloworld并打jar包允许

1.创建文件夹test统一在其中操作 2.创建hello.java文件 【hello.txt改属性为hello.java】并在里面添加代码 public class hello {public static void main(String[] args) {System.out.println("hello world");} } 注意&#xff1a;类名与文件名一致 然后运行…
阅读更多...
使用AI创建令人惊叹的3D模型

使用AI创建令人惊叹的3D模型

老子云平台《《《《《 使内容创作者能够在一分钟内毫不费力地将文本和图像转换为引人入胜的 3D 资产。 文本转 3D 我们的文本转 3D 工具使创作者&#xff08;包括那些没有 3D 经验的创作者&#xff09;能够使用文本输入在短短一分钟内生成 3D 模型。 一句话生成3D模型 老子…
阅读更多...
FPGA-VGA成像原理与时序

FPGA-VGA成像原理与时序

什么是VGA: VGA, Video Graphics Array。即视频图形阵列,具有分辨率高、显示速率快、颜色丰富等优点。VGA接口不但是CRT显示设备的标准接口,同样也是LCD液晶显示设备的标准接口,具有广泛的应用范围。在FGPA中,常广泛用于图像处理等领域。 VGA 显示器成像原理 在 VGA 标准刚兴…
阅读更多...
Material UI 5 学习02-其它按钮组件

Material UI 5 学习02-其它按钮组件

Material UI 5 学习02-其它按钮组件 一、IconButton按钮二、 ButtonGroup按钮组1、最基本的实例2、垂直按钮组 一、IconButton按钮 图标按钮通常适用于切换按钮&#xff0c;允许选择或选择单个选项 取消选择&#xff0c;例如在项目中添加或删除星号。 <IconButton aria-lab…
阅读更多...
docker pull 拉取失败，设置docker国内镜像

docker pull 拉取失败，设置docker国内镜像

遇到的问题 最近在拉取nginx时&#xff0c;显示如下错误&#xff1a;Error response from daemon: Get “https://registry-1.docker.io/v2/”: net/http: request canceled (Client.Timeout exceeded while awaiting headers)。 这个的问题是拉取镜像超时&#xff0c;通过检索…
阅读更多...
RISC-V特权架构 - 机器模式下的异常处理

RISC-V特权架构 - 机器模式下的异常处理

RISC-V特权架构 - 机器模式下的异常处理 1 进入异常1.1 从mtvec 定义的PC 地址开始执行1.2 更新CSR 寄存器mcause1.3 更新CSR 寄存器mepc1.4 更新CSR 寄存器mtval1.5 更新CSR 寄存器mstatus 2 退出异常2.1 从mepc 定义的PC 地址开始执行2.2 更新CSR 寄存器mstatus 3 异常服务程…
阅读更多...
Docker Protainer可视化平台，忘记登录密码，重置密码。

Docker Protainer可视化平台，忘记登录密码，重置密码。

由于好久没有登录portainer系统&#xff0c;导致忘记了登录密码&#xff0c;试了好多常用的密码都不对&#xff0c;无奈只能重置密码。 一、停止protainer 容器 查看容器ID和COMMAND 用于停止容器 docker ps -a停止容器 docker stop portainer二、查找volume data 宿主机所在…
阅读更多...
脉冲电阻器负载、功率和电压降额，选型分析

脉冲电阻器负载、功率和电压降额，选型分析

本文讨论了关键的电阻脉冲负载、功率和电压降额参数&#xff0c;这些参数对于正确选择指南和可靠运行这些无源元件非常重要。 EAK脉冲负载 在许多应用中&#xff0c;电阻器将承受脉冲负载。我们区分周期性/重复性负载和脉冲序列;一方面&#xff0c;脉冲以一定频率重复&#xff…
阅读更多...
Spring中最常用的11个扩展点

Spring中最常用的11个扩展点

前言 我们一说到spring&#xff0c;可能第一个想到的是 IOC&#xff08;控制反转&#xff09; 和 AOP&#xff08;面向切面编程&#xff09;。 没错&#xff0c;它们是spring的基石&#xff0c;得益于它们的优秀设计&#xff0c;使得spring能够从众多优秀框架中脱颖而出。 除…
阅读更多...
Thingsboard本地源码部署教程

Thingsboard本地源码部署教程

本章将介绍ThingsBoard的本地环境搭建&#xff0c;以及源码的编译安装。本机环境&#xff1a;jdk11、maven 3.6.2、node v12.18.2、idea 2023.1、redis 6.2 环境安装 开发环境要求&#xff1a; Jdk 11 版本 &#xff1b;Postgresql 9 以上&#xff1b;Maven 3.6 以上&#xf…
阅读更多...
PaddleOCR CPU 文本文字识别 docker部署

PaddleOCR CPU 文本文字识别 docker部署

需求&#xff1a; 需要把所有滑块图片的数据文字提取出来 启动服务 mkdir paddle cd paddle docker run -itd --name ppocr -v $PWD:/paddle --networkhost -it registry.baidubce.com/paddlepaddle/paddle:2.1.3-gpu-cuda10.2-cudnn7 /bin/bash docker exec -it ppocr bash …
阅读更多...
深入理解Tomcat

深入理解Tomcat

目录&#xff1a; TomcatTomcat简介如何下载tomcatTomcat工作原理Tomcat架构图Tomcat组件Server组件Service组件Connector组件Engine组件Host组件Context组件 配置虚拟主机(Host)配置Context Tomcat Tomcat简介 Tomcat服务器是Apache的一个开源免费的Web容器。它实现了JavaEE…
阅读更多...
mysql学习笔记7——数据库查询深入

mysql学习笔记7——数据库查询深入

.sql文件 在实际使用数据库时&#xff0c;常常要对数据库文件进行备份&#xff0c;以便在数据库遭到入侵或者非人为因素导致损坏后&#xff0c;快速恢复数据 .sql文件便提供了这种功能&#xff0c;首先.sql文件是由一串串mysql指令组成的&#xff0c;我们插入.sql文件实际相当…
阅读更多...
5G工业智能网关保障煤矿安全生产

5G工业智能网关保障煤矿安全生产

随着物联网技术发展与煤矿需求的持续激增&#xff0c;矿山矿井的分布范围广泛、户外环境恶劣等管理问题急需解决&#xff0c;而物联网网关工业级设计能够无惧恶劣环境干扰&#xff0c;轻松解决户外网络部署问题。 工业网关通过采集矿井内的各类传感器数据对矿井进行远程监控&a…
阅读更多...
[C#]winform部署yolov9的onnx模型

[C#]winform部署yolov9的onnx模型

C# WinForms 部署 YOLOv9 ONNX 模型简介 在当今的计算机视觉领域&#xff0c;目标检测是不可或缺的一项技术。YOLO&#xff08;You Only Look Once&#xff09;系列模型以其高效和准确的特点受到了广泛关注。随着YOLOv9的发布&#xff0c;其性能进一步提升&#xff0c;为实际应…
阅读更多...
在全志V853平台上成功部署深度学习步态识别算法

在全志V853平台上成功部署深度学习步态识别算法

北理工通信课题组辛喆同学在本科毕业设计《基于嵌入式系统的步态识别的研究》中&#xff0c;成功将深度步态识别算法GaitSet移植到全志V853开发板上。本研究在CASIA-B数据集上进行测试&#xff0c;正常行走状态下该系统的步态识别准确率达到了94.9%&#xff0c;背包行走和穿外套…
阅读更多...
C++输入输出（I\O）

C++输入输出（I\O）

我们知道C是由C语言发展而来的&#xff0c;几乎完全兼容C语言&#xff0c;换句话说&#xff0c;你可以在C里面编译C语言代码。如下图: C语言是面向过程的语言&#xff0c;C在C语言之上增加了面向对象以及泛型编程机制&#xff0c;因此C更适合中大型程序的开发&#xff0c;然而C…
阅读更多...
最新文章

Copyright @ 2022~2023