【数据结构】链式结构实现:二叉树

二叉树

  • 一.快速创建一颗二叉树
  • 二.二叉树的遍历
    • 1.前序、中序、后序遍历(深度优先遍历DFS)
    • 2.层序遍历(广度优先遍历BFS)
  • 三.二叉树节点的个数
  • 四.二叉树叶子节点的个数
  • 五.二叉树的高度
  • 六.二叉树第k层节点个数
  • 七.二叉树查找值为x的节点
  • 八.判断二叉树是否是完全二叉树
  • 九.二叉树的递归创建
  • 十.二叉树的销毁
  • 十一.二叉树必做OJ题
  • 十二.了解高级树

一.快速创建一颗二叉树

  1. 回顾⼆叉树的概念,⼆叉树分为空树和非空⼆叉树,非空⼆叉树由根结点、根结点的左子树、根结点的右子树组成的

  2. 根结点的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的,因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。
    在这里插入图片描述

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");return;}node->data = x;node->left = node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{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 = CreatBinaryTree();return 0;
}

二.二叉树的遍历

1.前序、中序、后序遍历(深度优先遍历DFS)

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

  1. 前序遍历:访问根结点的操作发生在遍历其左右子树之前;访问顺序为:根结点、左子树、右子树

  2. 中序遍历:访问根结点的操作发生在遍历其左右子树中间;访问顺序为:左子树、根结点、右子树

  3. 后序遍历:访问根结点的操作发生在遍历其左右子树之后;访问顺序为:左子树、右子树、根结点

参考如下:

在这里插入图片描述
代码如下:

//前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//后序遍历
void PosOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}int main()
{BTNode* root = CreatBinaryTree();PrevOrder(root);printf("\n");InOrder(root);printf("\n");PosOrder(root);printf("\n");return 0;
}

在这里插入图片描述

前序遍历递归图解:
在这里插入图片描述

在这里插入图片描述

注意:已知二叉树的前序和中序后序和中序就可以推导出二叉树的形状,但是只知道前序和后序则无法推导出二叉树的形状。

在这里插入图片描述

2.层序遍历(广度优先遍历BFS)

  层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1,层序遍历就是从所在二叉树的根结点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

在这里插入图片描述

实现层序遍历需要用到队列,拷贝Queue.h与Queue.c文件到本地。

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->val);// NULL无需入队列if(front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestory(&q);
}

三.二叉树节点的个数

错误写法:

在这里插入图片描述

改进方法:

在这里插入图片描述

在这里插入图片描述

最好的方法:分治法(大问题化为多个小问题、小问题再化为多个小问题…直到不能再分为止)

  1. 空:0个
  2. 非空:左子树+右子树+1
int TreeSize(BTNode* root)
{if (root == NULL)return 0;return TreeSize(root->left) + TreeSize(root->right) + 1;
}

四.二叉树叶子节点的个数

  1. 空:0个
  2. 非空:若左子树和右子树同时为空返回1,否则左子树叶子节点+右子树叶子节点
int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

五.二叉树的高度

  1. 空:0个
  2. 非空:MAX {左子树高度,右子树高度} + 1
//未记录高度导致重复大量的递归效率极低
//int TreeHeight1(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//
//	return TreeHeight(root->left) > TreeHeight(root->right) ?
//		TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
//}int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->left);return leftHeight > rightHeight ?leftHeight + 1 : rightHeight + 1;
}

六.二叉树第k层节点个数

  1. 空:0个
  2. 非空且k==1:返回1
  3. 非空且k>1:左子树的k-1层节点个数+右子树的k-1层节点个数
int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

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

  1. 空:返回NULL
  2. 非空且data==x:返回root
  3. 非空且data!=x:递归左子树+递归右子树,注意:要保存递归的结果层层返回
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = TreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

八.判断二叉树是否是完全二叉树

注意:满二叉树可以利用树的高度,和节点的个数判断,但是完全二叉树前k-1层是满二叉树,最后一层不是满的,该方法就不行了。

可以利用层序遍历解决,方法如下:

在这里插入图片描述

bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到第一个空,开始判断if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//队列中还有非空节点,就不是完全二叉树if (front){QueueDestory(&q);return false;}	}//队列中没有非空节点,就是完全二叉树QueueDestory(&q);return true;
}

九.二叉树的递归创建

题目:已知前序遍历结果:abc##de#g##f###(其中#是NULL)
输出:中序遍历的结果(不包含NULL)

在这里插入图片描述

#include <stdio.h>
#include<stdlib.h>typedef struct BinaryTreeNode
{char val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* CreateTree(char* a, int* pi)
{//遇到#返回NULLif(a[*pi] == '#'){(*pi)++;return NULL;}//创建根节点BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = a[(*pi)++];//递归构建左子树root->left = CreateTree(a, pi);//递归构建右子树root->right = CreateTree(a, pi);//返回根节点return root;
}void InOrder(BTNode* root)
{if(root == NULL)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main() {char a[100];scanf("%s", a);int i = 0;BTNode* root = CreateTree(a, &i); //注意:要传入地址InOrder(root);
}

十.二叉树的销毁

  1. 空:返回NULL
  2. 非空:后序遍历销毁节点
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}

十一.二叉树必做OJ题

  1. 单值二叉树
  2. 相同的树
  3. 对称二叉树
  4. 二叉树的前序遍历
  5. 二叉树的中序遍历
  6. 二叉树的后序遍历
  7. 另一棵树的子树
  8. 二叉树遍历

十二.了解高级树

在这里插入图片描述

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

什么是机器人快换盘?

机器人快换盘&#xff0c;行业内也称作工具快换盘、换枪盘、快换工具盘、快速更换器、快换器、 快换夹具、治具快换等。是末端执行器快速更换装置&#xff08;End-Of-Arm Tooling&#xff0c;简称EOAT&#xff09;&#xff0c;是工业自动化领域中用于机器人手臂上的一种重要设备…

MiniCPM-V: A GPT-4V Level MLLM on Your Phone论文阅读

大模型的趋势&#xff1a;模型性能越来越好&#xff0c;模型参数变小&#xff0c;端边设备计算能力变强。 MiniCPM-V优点 结果好、OCR能力突出、多分辨率、多语言、易于部署 模型结构 图片encoder适用vit。输入整体以及切片。切片使用自适应算法&#xff0c;通过计算分数&am…

人机环境系统智能已经超越了传统的空间智能和物理世界的概念

人机环境系统智能已经超越了传统的空间智能和物理世界的概念&#xff0c;进入了更为复杂的层次。在人机环境系统中&#xff0c;智能不仅涉及对物理世界的感知和理解&#xff0c;还包括对人类语言、情感、意图等的理解和生成。人工智能技术的应用&#xff0c;如自然语言处理、机…

C++静态数组的用法

每日诗词&#xff1a; 疏影横斜水清浅&#xff0c;暗香浮动月黄昏。 ——《山园小梅其一》林逋 目录 数组的基础操作&#xff1a; 数组元素的增加&#xff1a; 演示&#xff1a; 数组元素的删除&#xff1a; 演示&#xff1a; 数组元素的访问和修改&#xff1a; 演示&am…

WLAN射频调优

射频调优的基本原则 信道优化的基本原则 2.4G射频在非高密部署场景中推荐采用1、6、11这种3个不重叠的信道进行规划&#xff0c;同理也可以选用2、7、12或3、8、13的组合方式&#xff1b;在高密部署场景中则推荐采用1、5、9、13共4个信道组合进行规划。5G射频推荐采用36、40、…

HQChart使用教程101-创建内置键盘精灵

HQChart使用教程101-创建内置键盘精灵 键盘精灵步骤1. 创建键盘精灵实例2. 设置事件回调3. 初始化键盘精灵4. 设置码表数据5. 监听"keydown","mousedown" 交流QQ群HQChart代码地址键盘精灵源码 完整实例 键盘精灵 键盘精灵是一种便捷操作软件的功能工具&a…

【人工智能】Python融合机器学习、深度学习和微服务的创新之路

1. &#x1f680; 引言1.1 &#x1f680; 人工智能的现状与发展趋势1.2 &#x1f4dc; 机器学习、深度学习和神经网络的基本概念1.3 &#x1f3c6; 微服务架构在人工智能中的作用 2. &#x1f50d; 机器学习的演变与创新2.1 &#x1f31f; 机器学习的历史回顾2.2 &#x1f9e0;…

UE----IPA 安装 在手机上后 显示 不受信任的开发者

进入设置 ----》 点击 通用 ----》点击 VPN与设备管理 点击信任 然后 再打开开发者模式即可 在隐私与安全性里 下滑 最底部 即可看到开发者模式

JavaScript学习笔记(十二):JS Web API

1、Web API - 简介 Web API 是开发人员的梦想。 它可以扩展浏览器的功能它可以极大简化复杂的功能它可以为复杂的代码提供简单的语法 1.1 什么是 Web API&#xff1f; API 指的是应用程序编程接口&#xff08;Application Programming Interface&#xff09;。 Web API 是 …

机器学习第十四章-概率图模型

目录 14.1 隐马尔可夫模型 14.2马尔科夫随机场 14.3条件随机场 14.4学习与推断 14.4.1变量消去 14.4.2信念传播 14.5近似推断 14.5.1 MCMC采样 14.5.2 变分推断 14.6 话题模型 14.1 隐马尔可夫模型 概率围棋型是一类用图来表达变量相关关系的概率模型.它以图为表示工具…

Python入门级[ 基础语法 函数... ] 笔记 例题较多

本文是刚学习Python的笔记&#xff0c;当时使用的编辑器是交互式编程&#xff0c;所以很多代码可能在你们的编译器上面不能运行&#xff0c;我用快引用引起来了&#xff0c;还需要大家自己动手试一试。 内容涉及的比较简单&#xff0c;主要还是Python的语法部分&#xff1a;三…

短链接系统设计方案

背景 需要设计一个短链接系统&#xff0c;主要功能主要有如下几点&#xff1a; ToB&#xff1a; 输入一个长链接&#xff0c;转换成短链接。这个短链接有时效性&#xff0c;可以设定指定过期时间。这个系统的每天会生成千万级别的短链接。数据具备可分析功能。 ToC&#xf…

借助Vercel 十分钟搭建属于自己的AI应用站点

轻松依托 Vercel,快速构建 Nexior AI 平台 Nexior 是一个令人惊叹的开源项目&#xff0c;托管于 GitHub。通过它&#xff0c;您能够一键便捷地部署专属的 AI 应用站点&#xff0c;包括 AI 问答、Midjourney 绘画、知识库问答、艺术二维码等&#xff0c;完全不需要自己去开发 A…

springBoot+ druid配置多数据源

springBoot druid配置多数据源 1.在yml加&#xff1a; spring:#1.JDBC数据源datasource:druid:first:username: PYpassword: ral2024url: jdbc:mysql://localhost:3306/mysql?serverTimezoneUTC&characterEncodingutf8&useUnicodetrue&useSSLfalsedriver-class-n…

前端进行分页Vue3+Setup写法

当后端不方便提供数据分页查询接口时&#xff0c;就需要前端来自己分割进行分页操作 在有可能的情况下还是建议用分页查询接口&#xff0c;减少网络数据传输 首先el-table绑定数组 分页组件&#xff0c;变量自己定义防止报错 <el-paginationlayout"->, total, siz…

HTML中的<fieldset>标签元素框的使用

HTML 提供的 <fieldset> 标签用于在表单中分组相关元素。 <fieldset> 标签会在相关元素周围绘制一个框。 <legend> 标签为 fieldset 元素定义标题。 语法如下&#xff1a; <fieldset><legend>标题</legend><!-- 元素内容... -->…

qt-17不规则窗体

不规则窗体 知识点shape.hshape.cppmain.cpp运行图 知识点 感觉这个就是在图片背景 贴了白色 shape.h #ifndef SHAPE_H #define SHAPE_H#include <QWidget>class Shape : public QWidget {Q_OBJECTpublic:Shape(QWidget *parent nullptr);~Shape(); protected:void m…

最新图像修复论文汇总(2024年以来)(三)

汇总了自2024年以来新提出的高质量图像修复工作&#xff0c;包含扩散模型、transformer、mamba、sam等最前沿的技术&#xff0c;其中一些是ICLR、ICML、CVPR、ECCV、ACM MM 2024年的新作。 这里是第三部分&#xff0c;还有两部分请参阅。 最新图像修复论文汇总&#xff08;20…

【Python快速入门和实践013】Python常用脚本-目标检测之按照类别数量划分数据集

一、功能介绍 这段代码实现了从给定的图像和标签文件夹中分割数据集为训练集、验证集和测试集的功能。以下是代码功能的总结&#xff1a; 创建目标文件夹结构&#xff1a; 在指定的根目录&#xff08;dataset_root&#xff09;下创建images和labels两个文件夹。在这两个文件夹下…

瑞友科技项目经理认证负责人杨文娟受邀为第四届中国项目经理大会演讲嘉宾︱PMO评论

全国项目经理专业人士年度盛会 北京瑞友科技股份有限公司项目经理认证负责人杨文娟女士受邀为PMO评论主办的全国项目经理专业人士年度盛会——2024第四届中国项目经理大会演讲嘉宾&#xff0c;演讲议题为“瑞友科技项目经理人才培养体系落地实践”。大会将于10月26-27日在北京举…