C语言实现二叉树以及二叉树的详细介绍

目录

1.树概念及结构

1.1树的概念

1.2树的相关概念

1.3树的表示

2.二叉树概念及结构

2.1二叉树的概念

2.2特殊的二叉树

2.3二叉树的性质 

2.4二叉树的存储结构

3.二叉树顺序结构--特殊的二叉树--堆及其实现

3.1堆的概念及结构

3.2堆的实现 

3.2.1堆的结构

3.2.2堆的创建

3.2.2.1向上调整算法

3.2.2.2向下调整算法

 3.2.2.2.1向下建堆的时间复杂度

 3.2.3堆的插入

 3.2.4堆的删除

 3.2.5堆实现的参考代码

 3.2.6堆的应用

3.2.6.1堆排序

3.2.6.2 TOP-K问题

4.二叉树链式结构及实现

4.1链式二叉树的结构

4.2前置说明

4.3二叉树的遍历 

4.3.1前序、中序以及后序遍历

4.3.2层序遍历

4.4二叉树的节点个数以及高度等功能

4. 4.1二叉树节点个数

4.4.2二叉树叶子节点个数

4.4.3二叉树第K层节点个数

4.4.4 二叉树查找值为x的节点

4.4.5 二叉树的高度

4.5二叉树的构建、销毁及判断是否是完全二叉树

4.5.1通过前序遍历数组构建二叉树

4.5.2二叉树的销毁

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

4.6参考代码


1.树概念及结构

1.1树的概念

        树不同于之前的线性表,树是一种非线性的数据结构,由n(n>=0)个有限节点组成一个具有层次关系的集合。有一个特殊的节点称为根节点,根节点没有前驱节点。除了根节点外,其余节点被分成M(M>0)个互不相交的集合,其中每个集合又是一颗结构与树类似的子树。没一棵子树的根节点有且只有一个前驱结点,但是可以有0个或多个后继节点,因此树是递归定义的。

        注:子树之间不能有交集。 

1.2树的相关概念

(1) 结点的度:一个结点含有的子树的个数称为该结点的度; 如上图:A的为6.

(2)叶结点或终端结点:度为0的结点称为叶结点; 如上图:BCHI、P...等结点为叶结点。

(3)非终端结点或分支结点:度不为 0 的结点; 如上图: D E F G...等结点为分支结点。
(4)双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:AB的父结点。
(5)孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:BA的孩子结点
(6)兄弟结点 :具有相同父结点的结点互称为兄弟结点; 如上图: B C 是兄弟结点
(7)树的度:一棵树中,最大的结点的度称为树的度; 如上图:树的度为6
(8)结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
(9)树的高度或深度:树中结点的最大层次; 如上图:树的高度为4
(10)堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图: H I 互为兄弟结点
(11)结点的祖先:从根到该结点所经分支上的所有结点;如上图: A 是所有结点的祖先
(12)子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是 A 的子孙
(13)森林:由 m m>0 )棵互不相交的树的集合称为森林;
上列概念需要熟记:(1)(2)(4)(5)(7)(8)(9).

1.3树的表示

        树的节点结构,既要存储值,也要保存节点和节点之间的关系实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};

2.二叉树概念及结构

2.1二叉树的概念

        一棵二叉树是节点的一个有限集合,该集合:(1)可能为空(2)由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

        二叉树的特点:(1)二叉树不存在度大于2的节点(2)二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。

        注:对于任意的二叉树都是由以下几种情况复合而成的: 

2.2特殊的二叉树

(1). 满二叉树 :一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K ,且结点总数是2^{k}-1,则它就是满二叉树。
(2). 完全二叉树 :完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为 K的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.3二叉树的性质 

(1). 若规定根结点的层数为 1 ,则一棵非空二叉树的 i 层上最多有2^{(i-1)}个节点。
(2). 若规定根结点的层数为 1 ,则 深度为 h 的二叉树的最大结点数是2^{h}-1 个节点。
(3). 对任何一棵二叉树 , 如果度为 0的 叶结点个数为 n_{0} , 度为 2 的分支结点个数为 n_{2},则有 n_{0}n_{2}+1.
/*
* 假设二叉树有N个结点
* 从总结点数角度考虑:N = n0 + n1 + n2 ①
* 
* 从边的角度考虑,N个结点的任意二叉树,总共有N-1条边
* 因为二叉树中每个结点都有双亲,根结点没有双亲,每个节点向上与其双亲之间存在一条边
* 因此N个结点的二叉树总共有N-1条边
* 
* 因为度为0的结点没有孩子,故度为0的结点不产生边; 度为1的结点只有一个孩子,故每个度为1的结
点* * 产生一条边; 度为2的结点有2个孩子,故每个度为2的结点产生两条边,所以总边数为:
n1+2*n2 
* 故从边的角度考虑:N-1 = n1 + 2*n2 ②
* 结合① 和 ②得:n0 + n1 + n2 = n1 + 2*n2 - 1
* 即:n0 = n2 + 1
*/

(4)若规定根节点的层数为1,具有n个节点的满二叉树的深度为h=log_{2}(n+1)

(5)对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有结点从0开始编号,则对于序号为i的结点有:

        (a). i>0 i 位置结点的双亲序号: (i-1)/2 i=0 i 为根结点编号,无双亲结点
        (b). 2i+1<n ,左孩子序号: 2i+1 2i+1>=n 否则无左孩子
        (c).若 2i+2<n ,右孩子序号: 2i+2 2i+2>=n 否则无右孩子

2.4二叉树的存储结构

        二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

1.顺序存储

        顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

2.链式存储

        二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们一般都是二叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* parent; // 指向当前结点的父亲节点struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
};

3.二叉树顺序结构--特殊的二叉树--堆及其实现

3.1堆的概念及结构

        堆分为小堆和大堆,小堆的概念就是:把一个集合的所以元素按完全二叉树的顺序存储方式存储在一个一维数组中,满足任意一个节点的子节点的值都大于该节点的值。大堆则相反。

        堆的性质:(1)堆中某个节点的值总是不大于或者不小于其父亲节点。(2)堆总是一棵完全二叉树。

3.2堆的实现 

3.2.1堆的结构

        用数组实现堆:

typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}HP;

3.2.2堆的创建

3.2.2.1向上调整算法

        给出一个数组,逻辑上可以看作一棵完全二叉树,但是还不是一个堆,通过向上调整算法把这个堆调整成一个小堆。

        向上调整算法:依次插入一个元素在最后,然后和它的父节点比较,如果小于父节点,则交换元素,再和父节点的父节点比较。终止条件:(1)大于父节点。(2)调整到根节点。

	int arr[] = { 9,2,3,1,8,7,0,4,5,6 };
#include <stdio.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(int* a, int child) //child就是最后一个叶子节点的下标
{int parent = (child - 1) / 2;//建小堆:终止条件,父节点小于子节点或者调整到根节点while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
void test()
{int arr[] = { 9,2,3,1,8,7,0,4,5,6 };int sz = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < sz; i++){AdjustUp(arr, i);}for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}
}int main()
{test();return 0;
}

3.2.2.2向下调整算法

         给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

         根结点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子结点的子树开始调整,一直调整到根结点的树,就可以调整成堆。

int a[] = {1,5,3,8,7,6};

        将上述数组调整为大堆:

        其中的第三步调整时,左右子树都是大堆,就和上述讲到的从根节点向下调整一样。 

#include <stdio.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整的前提是,左右子树是大堆
void AdjustDown(int* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小,则将child指向右孩子,反之,不交换int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在,调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] > a[child])//child + 1 < n表示右孩子存在{++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void test()
{//使用向下调整算法对数组进行建堆int a[] = { 1,5,3,8,7,6 };//先找到最后一个非叶子节点,即为最后一个节点的父亲节点int sz2 = sizeof(a) / sizeof(a[0]);for (int i = ((sz2 - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, sz2, i);}for (int i = 0; i < sz2; i++){printf("%d ", a[i]);}}int main()
{test();return 0;
}

        注:向上调整算法和向下调整算法建小堆和建大堆思路上是一样的,如果要交换,把其中父亲节点和子节点比较的大小于符号交换即可。  

 3.2.2.2.1向下建堆的时间复杂度
        因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明( 时间复杂度本来看的就是近似值,多几个结点不影响最终结果)

 

 3.2.3堆的插入

        堆的插入其实就是通过向上调整算法一个一个插入,先插入到最后一个位置然后向上调整。

void HeapPush(HP* hp, HPDataType x)
{assert(hp);//判断是否需要扩容if (hp->_size == hp->_capacity){int newcapacity = hp->_a == 0 ? 4 : hp->_capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("malloc fail!\n");exit(1);}hp->_a = tmp;hp->_capacity = newcapacity;}//先插入到最后一个位置然后在向上调整hp->_a[hp->_size] = x;hp->_size++;//向上调整AdjustUp(hp->_a, hp->_size - 1);
}

 3.2.4堆的删除

        删除堆是删除堆顶的数据,将堆顶的数据和最后一个数据交换,然后删除数组最后一个数据,再将堆顶数据进行向下调整。

void HeapPop(HP* hp)
{assert(hp);assert(hp->_size > 0);Swap(&(hp->_a[0]), &(hp->_a[hp->_size - 1]));//交换堆顶和最后一个位置的数据hp->_size--;//向下调整AdjustDown(hp->_a, hp->_size, 0);
}

 3.2.5堆实现的参考代码

//Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}HP;
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//初始化
void HeapInit(HP* hp);
// 堆的销毁
void HeapDestory(HP* hp);
// 堆的插入
void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* hp, HPDataType x);
// 堆的删除
void AdjustDown(HPDataType* a, int n, int parent);
void HeapPop(HP* hp);
// 取堆顶的数据
HPDataType HeapTop(HP* hp);
// 堆的数据个数
int HeapSize(HP* hp);
// 堆的判空
int HeapEmpty(HP* hp);
//Heap.c#include "Heap.h"void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//初始化
void HeapInit(HP* hp)
{assert(hp);hp->_a = NULL;hp->_size = 0;hp->_capacity = 0;
}// 堆的销毁
void HeapDestory(HP* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_size = hp->_capacity = 0;
}// 向上调整算法
void AdjustUp(HPDataType* a, int child) //child就是最后一个叶子节点的下标
{int parent = (child - 1) / 2;//建小堆:终止条件,父节点小于子节点或者调整到根节点while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//堆的插入
void HeapPush(HP* hp, HPDataType x)
{assert(hp);//判断是否需要扩容if (hp->_size == hp->_capacity){int newcapacity = hp->_a == 0 ? 4 : hp->_capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("malloc fail!\n");exit(1);}hp->_a = tmp;hp->_capacity = newcapacity;}//先插入到最后一个位置然后在向上调整hp->_a[hp->_size] = x;hp->_size++;//向上调整AdjustUp(hp->_a, hp->_size - 1);
}//向下调整的前提是:左右子树是堆
void AdjustDown(HPDataType* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小,则将child指向右孩子,反之,不交换int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在,调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child])//child + 1 < n表示右孩子存在{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆的删除--删除堆顶元素,然后重新排列堆
void HeapPop(HP* hp)
{assert(hp);assert(hp->_size > 0);Swap(&(hp->_a[0]), &(hp->_a[hp->_size - 1]));hp->_size--;//向下调整AdjustDown(hp->_a, hp->_size, 0);
}// 取堆顶的数据
HPDataType HeapTop(HP* hp)
{assert(hp);assert(hp->_size > 0); //堆不能为空return hp->_a[0];
}// 堆的数据个数
int HeapSize(HP* hp)
{assert(hp);return hp->_size;
}// 堆的判空
int HeapEmpty(HP* hp)
{assert(hp);if (hp->_size == 0){return 1; //如果为空,返回一个非0的数字}else{return 0;}
}

3.2.6堆的应用

3.2.6.1堆排序

        堆排序就是利用堆排序的思想进行排序,总共分为两个步骤:
(1)建堆:(a)排升序,建大堆(b)排降序:建小堆

(2)利用堆删除思想来进行排序:例如排升序,先将数组建成一个大堆,然后将堆顶数据和最后一个位置的数据交换,删除最后一个位置的数据,然后向下调整再次调整为大堆,这样被删除的那个元素就是最大的一个元素,放在数组的最后一个位子,然后再将倒数第二个数据和堆顶数据交换重复上述操作,重复到不可交换为止,既可以将数组排列为升序。 

#include <stdio.h>//向下调整建大堆
#include <stdio.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整的前提是,左右子树是大堆
void AdjustDown(int* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小,则将child指向右孩子,反之,不交换int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在,调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] > a[child])//child + 1 < n表示右孩子存在{++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void test()
{//使用向下调整算法对数组进行建成大堆int a[] = { 20, 17, 4, 16, 5, 3 };//先找到最后一个非叶子节点,即为最后一个节点的父亲节点int sz2 = sizeof(a) / sizeof(a[0]);for (int i = ((sz2 - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, sz2, i);}for (int i = 0; i < sz2; i++){printf("%d ", a[i]);}printf("\n");//利用堆删除的思想排升序for (int i = sz2 - 1; i > 0; i--) //每次减少一个元素就相当于删除一个元素{Swap(&a[0], &a[i]);AdjustDown(a, i, 0);}for (int i = 0; i < sz2; i++){printf("%d ", a[i]);}printf("\n");
}int main()
{test();return 0;
}
3.2.6.2 TOP-K问题
TOP-K问题:即求数据结合中前 K 个最大的元素或者最小的元素,一般情况下数据量都比较大。对于TOP-K问题能想到的最简单直接的方式就是排序,但是如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
(1)用数据集中前K个元素来建堆:(a)前K个最大的元素,建小堆。(2)前K个最小的元素,建大堆。
(2)用剩余的N-K个元素依次和堆顶元素进行比较,不满足则替换堆顶元素。以找前K个最大的元素为例:用前K个元素建小堆,然后用剩余的依次比较,如果小于堆顶元素,则不和堆顶元素交换,如果大于堆顶元素,则和堆顶元素交换然后再调整为小堆。
#include <stdio.h>//向下调整建大堆
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整的前提是,左右子树是小堆
void AdjustDown(int* a, int n, int parent) //n是size
{//假设法//先假设左孩子小//然后左孩子和右孩子进行一个比较//如果右孩子比左孩子小,则将child指向右孩子,反之,不交换int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在,调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child])//child + 1 < n表示右孩子存在{++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void PrintTopK(int* a, int n, int k)
{//1.建小堆--找a中前K大的元素for (int i = ((k - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}//2.将剩下n-k个元素依次与堆顶元素进行比较,大于堆顶元素则交换,然后再次调整为小堆for (int i = k; i < n; i++){if (a[i] > a[0]){Swap(&a[i], &a[0]);AdjustDown(a, k, 0);}}//打印前K个元素for (int i = 0; i < k; i++){printf("%d ", a[i]);}
}
void test()
{int arr[] = { 2,6,3,1,7,9,23,57,59,23,46,5,47,96,46,39,86,46 };int sz = sizeof(arr) / sizeof(arr[0]);PrintTopK(arr, sz, 4);
}int main()
{test();return 0;
}

4.二叉树链式结构及实现

4.1链式二叉树的结构

typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;

4.2前置说明

        此处手动快速创建一棵简单的二叉树,快速进入二叉树操作,后面再来研究二叉树真正的创建方式。

BTNode* BuyNode(BTDataType x)
{BTNode* ret = (BTNode*)malloc(sizeof(BTNode));if (ret == NULL){perror("malloc fail!\n");exit(1);}ret->_data = x;ret->_left = NULL;ret->_right = NULL;return ret;
}BTNode* CreateBinaryTree()
{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;
}

        创建的二叉树如下:

        注:下列方法的实现,都是通过这个例子来说明的 。

4.3二叉树的遍历 

4.3.1前序、中序以及后序遍历

        所谓二叉树的遍历是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作依次。访问节点所做的操作依赖于具体的应用问题。比如二叉树的销毁就会用到后序遍历。

        按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历,这三种遍历方式都属于深度优先遍历,后面介绍的层序遍历属于一直广度优先遍历,前序/中序/后序的区别是对节点的访问顺序不同:

(1)前序遍历:根  左子树  右子树

(2)中序遍历:左子树 根   右子树

(3)后序遍历:左子树  右子树  根

        由于被访问的节点必是某子树的根,所以N(Node),L(Left subtree),R(Right subtree)又可解释为根,根的左子树,根的右子树。NLP,LNP,LRN分别称为先根遍历,中根遍历和后根遍历。下列是三种遍历方法的代码实现,其实区别就是遍历的顺序不同,下列的代码在遇到空节点的时候打印'N'。

        注:下列功能的实现都在BinaryTree.c文件中,声明在BinaryTree.h中,测试代码在test.c文件中。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("N ");return ;}BinaryTreeInOrder(root->_left);printf("%d ", root->_data);BinaryTreeInOrder(root->_right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N ");return ;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%d ", root->_data);
}

        测试代码: 

#include "BinaryTree" //二叉树功能的实现声明在我自己创建的这个文件中,这个文件还包含了功能实现所需                //的头文件
void test()
{//先手搓一个二叉树BTNode* node1 = CreateBinaryTree();//进行遍历    BinaryTreePrevOrder(node1);printf("\n");BinaryTreeInOrder(node1);printf("\n");BinaryTreePostOrder(node1);printf("\n");}int main()
{test();return 0;
}

输出结果是:

前序遍历结果: 1 2 3 4 5 6
中序遍历结果: 3 2 1 5 4 6
后序遍历结果: 3 2 5 6 4 1

4.3.2层序遍历

        设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第二层上的节点,接着是第三层的节点,以此类推,从上至下,从左至右逐层访问树的节点的过程就是层序遍历。

        层序遍历的实现是通过之前学习的队列这个数据结构来实现的,具体队列的实现可以看C语言实现队列 。这里我们直接用实现好的功能即可。

        主要的步骤:先把根节点放入队列里面,访问队头元素(此时为根节点)之后取出,然后把根节点的左子节点和右子节点依次放入队列中,然后再访问队头元素(此时为根节点的左子节点)之后取出,把左子节点的左子节点和右子节点依次放入队列中,然后再访问队头元素(此时为根节点的右子节点)之后取出,把右子节点的左子节点和右子节点依次放入队列中,依次类推,直到队列为空结束层序遍历。

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{//用队列来实现层序遍历//从根节点开始存,存入根节点时把左右子节点存入,Queue q; //创建一个队列QueueInit(&q);  //对队列进行初始化if (root)  //如果不为空树,则把根节点放入队列{QueuePush(&q, root);}while (!QueueEmpty(&q)) //循环进行层序遍历{BTNode* tmp = QueueFront(&q);QueuePop(&q);printf("%d ", tmp->_data);if (tmp->_left){QueuePush(&q, tmp->_left);}if (tmp->_right){QueuePush(&q, tmp->_right);}}QueueDestroy(&q);
}

        测试代码:

#include "BinaryTree.h"void test()
{//先手搓一个二叉树BTNode* node1 = CreateBinaryTree();BinaryTreeLevelOrder(node1);
}int main()
{test();return 0;
}

4.4二叉树的节点个数以及高度等功能

        接下来的几个功能都是通过递归的方法来实现的,学好二叉树和的前提是要学好递归。

4. 4.1二叉树节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);

        通过递归实现的方法最主要的是弄清楚返回值和递归终止条件,以二叉树节点个数为例:

        情况1:根节点为空,返回0.

        情况2:左右子树为空,返回1

        情况3:其他情况返回左子树节点个数+右子树节点个数+1。这个1代表加上这层递归栈帧中的根节点。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{//情况1:根节点为空,返回0//情况2:左右子树为空,返回1//情况3:其他情况返回左子树加右子树加1if (root == NULL){return 0;}if (root->_left == NULL && root->_right == NULL){return 1;}int leftTreeNode = BinaryTreeSize(root->_left);int rightTreeNode = BinaryTreeSize(root->_right);return leftTreeNode + rightTreeNode + 1;
}

        测试代码: 

#include "BinaryTree.h"void test()
{//先手搓一个二叉树BTNode* node1 = CreateBinaryTree();//二叉树节点个数int ret = BinaryTreeSize(node1);printf("%d\n", ret);
}int main()
{test();return 0;
}

        这里通过递归展开图来详细描述该方法的递归过程: 

        上述图的代码就是该函数实现的代码。 

4.4.2二叉树叶子节点个数

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

        情况1:根节点为空,返回0.

        情况2:叶子节点没有左右子树,左子树和右子树为空,返回1.

        情况3:其他情况返回的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{//根节点为空返回0if (root == NULL){return 0;}//叶子节点没有左右子树,返回1if (root->_left == NULL && root->_right == NULL){return 1;}//叶子节点的个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

        4.4.3二叉树第K层节点个数

        根节点可以设为第一层也可以设为第0层,这里我们设为第一层,求第K层的节点个数,就是相对于第二层来说,求第K-1层的节点个数,相对于第三层来说就是求第K-2层节点个数,依次类推,到了第K层,对于第K层来说就是求第一层的节点个数,这是就返回一个(这一个代表这个根节点)。

        情况1:根节点为空,返回0。

        情况2:根节点不为空且K==1,返回1。

        情况3:根节点不为空且K>1,返回左子树的第K-1层节点个数+右子树的第K-1层节点个数。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//求第K层的节点个数//第一层的第K层节点个数,对于第二层来说,就是第二层的k-1层节点个数,就是第三层的k-2层节点个数//情况1:如果根节点为空,返回0//情况2:如果根节点不为空且k == 1, 返回1//情况3:如果根节点不为空且k > 1, 返回左子树的第k-1层节点个数+右子树的第k-1层节点个数if (root == NULL){return 0;}if (root && k == 1){return 1;}int leftTreeNode = BinaryTreeLevelKSize(root->_left, k - 1);int rightTreeNode = BinaryTreeLevelKSize(root->_right, k - 1);return leftTreeNode + rightTreeNode;
}

        测试代码:

//test.c
#define _CRT_SECURE_NO_WARNINGS
#include "BinaryTree.h"void test()
{//先手搓一个二叉树BTNode* node1 = CreateBinaryTree();int ret = BinaryTreeLevelKSize(node1, 2);printf("%d\n", ret);
}int main()
{test();return 0;
}

4.4.4 二叉树查找值为x的节点

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

        这个函数与前面的不同是返回的是一个节点, 所以每次递归都需要接收返回值,通过返回值的判断看是否返回上一层。

        情况1:根节点为空,返回NULL。

        情况2:根节点不为空但值不等于x,返回NULL。

        情况3:根节点不为空值等于x,返回该节点的指针。

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->_data == 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
#include "BinaryTree.h"void test()
{//先手搓一个二叉树BTNode* node1 = CreateBinaryTree();BTNode* ret = BinaryTreeFind(node1, 3);printf("%d ", ret->_data);}int main()
{test();return 0;
}

4.4.5 二叉树的高度

//二叉树的高度
int BinaryTreeHeight(BTNode* root);

        情况1:根节点为空0,返回0.

        情况2:根节点不为空,返回左右子树高度大的那个+1.(这个+1表示加上该层栈帧根节点的高度)。

        如果不用临时遍历存储会有效率问题,我写在了代码中。

//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{//情况1:如果根节点为空,返回0//情况2:如果根节点不为空,返回左右子树高度大的那个加1if (root == NULL){return 0;}//这里不用临时变量存储会有效率问题,//return BinaryTreeHeight(root->_left) > BinaryTreeHeight(root->_right) ? //		BinaryTreeHeight(root->_left) + 1 : BinaryTreeHeight(root->_right) + 1;//没有用变量存储的话,比较调用一次,高度高的在返回时又要向下递归重新求一次int LeftTreeHeight = BinaryTreeHeight(root->_left);int RightTreeHeght = BinaryTreeHeight(root->_right);return LeftTreeHeight > RightTreeHeght ? LeftTreeHeight + 1 : RightTreeHeght + 1;
}

        测试代码:

//test.c
#define _CRT_SECURE_NO_WARNINGS
#include "BinaryTree.h"void test()
{//先手搓一个二叉树BTNode* node1 = CreateBinaryTree();int ret = BinaryTreeHeight(node1);printf("%d\n", ret);
}int main()
{test();return 0;
}

4.5二叉树的构建、销毁及判断是否是完全二叉树

4.5.1通过前序遍历数组构建二叉树

        这里先给出一个数组"ABD##E#H##CF##G##",通过遍历该数组构建二叉树,用中序遍历打印出来,用中序遍历打印时需要先把打印的格式换为输出字符的形式,即把%d换为%c,不然打印出来的是字符的ASCLL码值。这里先给出这个数组对应的二叉树形状:

// 通过前序遍历的数组构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi < n) //判断下边是否未超过元素个数,未超过进行前序遍历,其实可以不写,这里是不会越界的{if (a[*pi] == '#') //如果为'#'返回NULL{(*pi)++;return NULL;}//不为'#',创建一个节点然后连接到二叉树中BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail!\n");exit(1);}root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, n, pi);root->_right = BinaryTreeCreate(a, n, pi);;return root;}else{perror("越界访问!\n");return NULL;}
}

        这里的参数a是待遍历的数组,n为数组中元素的个数,pi是数组下标的指针。因为在函数中要改变下标i,所以这里传指针pi。 

        测试代码:

#include "BinaryTree.h"int main()
{BTDataType arr[] = "ABD##E#H##CF##G##";int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;BTNode* ret = BinaryTreeCreate(arr, sz, &i);BinaryTreeInOrder(ret);return 0;
}

4.5.2二叉树的销毁

        二叉树的销毁使用的是后序遍历,因为如果使用前序遍历,先销毁了根节点,就找不到它的左右子树了,所以使用后序遍历,先销毁左右子树,最后销毁根节点。

        情况1:根为空,不需要销毁,直接返回。

        情况2:根不为空,递归左右子树,如果都返回则销毁该节点。

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{//三个部分的销毁:根 左子树 右子树//用后序:左子树 右子树 根if (root == NULL){return;}BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free(root);
}

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

        判断二叉树是否为完全二叉树还是用的层序遍历的思想,遍历一个节点,从队列中取出来,把它的子节点放入队列,如果子节点为空则把NULL指针放入队列,当取出的数据是第一个NULL指针是,判断队列中是否还有非空的指针,如果有,则不为完全二叉树,如果没有,则为完全二叉树。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp == NULL) //tmp是已经出队列的节点{//判断剩余元素中是否有非空元素//如果有则不为完全二叉树返回false//遍历队列元素QNode* cur = q.phead; //此时的队头元素就是tmp的下一个元素while (cur != q.ptail) {if (q.phead->val != NULL){return false;}cur = cur->next;}return true; //遍历完队列都没有非空指针,则为完全二叉树}if (tmp->_left){QueuePush(&q, tmp->_left);}else{QueuePush(&q, NULL);}if (tmp->_right){QueuePush(&q, tmp->_right);}else{QueuePush(&q, NULL);}}QueueDestroy(&q);
}

        测试用例和代码:

int main()
{BTNode* node1 = CreateBinaryTree();bool ret = BinaryTreeComplete(node1);if (ret == true){printf("完全二叉树!\n");}else{printf("非完全二叉树!\n");}return 0;
}

        这个测试用例的代码也一样,只是把创建二叉树函数中节点的连接改一下就行了。 

4.6参考代码

//BinaryTree.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;//手动创建二叉树
BTNode* BuyNode(BTDataType x);
BTNode* CreateBinaryTree();// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
int TreeSize(BTNode* root);
BTDataType* preorderTraversal(BTNode* root, BTDataType* returnSize);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//二叉树的高度
int BinaryTreeHeight(BTNode* root);

 

//BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS
#include "BinaryTree.h"
#include "Queue.h"BTNode* BuyNode(BTDataType x)
{BTNode* ret = (BTNode*)malloc(sizeof(BTNode));if (ret == NULL){perror("malloc fail!\n");exit(1);}ret->_data = x;ret->_left = NULL;ret->_right = NULL;return ret;
}BTNode* CreateBinaryTree()
{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;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi < n){if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail!\n");exit(1);}root->_data = a[(*pi)++];root->_left = BinaryTreeCreate(a, n, pi);root->_right = BinaryTreeCreate(a, n, pi);;return root;}else{perror("越界访问!\n");return NULL;}}// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{//三个部分的销毁:根 左子树 右子树//用后序:左子树 右子树 根if (root == NULL){return;}BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free(root);
}// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{//等于左子树节点个数加上右子树节点个数加上1//情况1:根节点为空,返回0//情况2:根节点不为空,返回左子树节点个数加上右子树节点个数+1//方法1//return root == NULL ? 0 ://	BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;//方法2//情况1:根节点为空,返回0//情况2:左右子树为空,返回1//情况3:其他情况返回左子树加右子树加1if (root == NULL){return 0;}if (root->_left == NULL && root->_right == NULL){return 1;}int leftTreeNode = BinaryTreeSize(root->_left);int rightTreeNode = BinaryTreeSize(root->_right);return leftTreeNode + rightTreeNode + 1;
}// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}//叶子节点没有左右子树if (root->_left == NULL && root->_right == NULL){return 1;}//叶子节点的个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数//int leftTreeNode = BinaryTreeLeafSize(root->_left);//int rightTreeNode = BinaryTreeLeafSize(root->_right);//return leftTreeNode + rightTreeNode;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//求第K层的节点个数//第一层的第K层节点个数,对于第二层来说,就是第二层的k-1层节点个数,就是第三层的k-2层节点个数//情况1:如果根节点为空,返回0//情况2:如果根节点不为空且k == 1, 返回1//情况3:如果根节点不为空且k > 1, 返回左子树的第k-1层节点个数+右子树的第k-1层节点个数if (root == NULL){return 0;}if (root && k == 1){return 1;}int leftTreeNode = BinaryTreeLevelKSize(root->_left, k - 1);int rightTreeNode = BinaryTreeLevelKSize(root->_right, k - 1);return leftTreeNode + rightTreeNode;
}// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->_data == 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;
}// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}//前序遍历,把返回的值存入一个数组中
int TreeSize(BTNode* root) //返回节点的个数
{return root == NULL ? 0 : TreeSize(root->_left) + TreeSize(root->_right) + 1;
}void preOrder(BTNode* root, BTDataType* a, int* pi)
{if (root == NULL){return;}a[(*pi)++] = root->_data;preOrder(root->_left, a, pi);preOrder(root->_right, a, pi);}BTDataType* preorderTraversal(BTNode* root, BTDataType* returnSize)
{//如果返回一个数组,必须要告诉返回数组的大小,returnSize表示返回数组的大小*returnSize = TreeSize(root);BTDataType* a = (BTDataType*)malloc(sizeof(BTDataType) * (*returnSize));int i = 0;preOrder(root, a, &i);return a;
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("N ");return ;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N ");return ;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%d ", root->_data);
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{//用队列来实现层序遍历//从根节点开始存,存入根节点时把左右子节点存入,Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);printf("%d ", tmp->_data);if (tmp->_left){QueuePush(&q, tmp->_left);}if (tmp->_right){QueuePush(&q, tmp->_right);}}QueueDestroy(&q);
}// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp == NULL) //tmp是已经出队列的节点{//判断剩余元素中是否有非空元素//如果有则不为完全二叉树返回false//遍历队列元素QNode* cur = q.phead;while (cur != q.ptail) {if (q.phead->val != NULL){return false;}cur = cur->next;}return true;}if (tmp->_left){QueuePush(&q, tmp->_left);}else{QueuePush(&q, NULL);}if (tmp->_right){QueuePush(&q, tmp->_right);}else{QueuePush(&q, NULL);}}QueueDestroy(&q);
}//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{//情况1:如果根节点为空,返回0//情况2:如果根节点不为空,返回左右子树高度大的那个加1if (root == NULL){return 0;}//这里不用临时变量存储会有效率问题,//return BinaryTreeHeight(root->_left) > BinaryTreeHeight(root->_right) ? //		BinaryTreeHeight(root->_left) + 1 : BinaryTreeHeight(root->_right) + 1;//没有用变量存储的话,比较调用一次,高度高的在返回时又要向下递归重新求一次int LeftTreeHeight = BinaryTreeHeight(root->_left);int RightTreeHeght = BinaryTreeHeight(root->_right);return LeftTreeHeight > RightTreeHeght ? LeftTreeHeight + 1 : RightTreeHeght + 1;
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

《昇思25天学习打卡营第25天|第22天》

今天是学习的第22天&#xff0c;今天学的是应用实践的自然语言处理的RNN实现情感分类。 从情感分类开始学习&#xff0c;数据准备、数据下载模块、加载IMDB数据集、加载预训练词向量、数据集预处理、模型构建、Embedding、RNN(循环神经网络)、Dense、损失函数与优化器、训练逻…

Github狂揽2.8k stars,可一键生成绘画全过程,却引发全球骂战

大家好&#xff0c;我是程序员X小鹿&#xff0c;前互联网大厂程序员&#xff0c;自由职业2年&#xff0c;也一名 AIGC 爱好者&#xff0c;持续分享更多前沿的「AI 工具」和「AI副业玩法」&#xff0c;欢迎一起交流~ 这项 AI 技术刚一上线&#xff0c;就在 Github 狂揽 1k stars…

数据库理论基础

1.什么是数据库 1.1数据 描述事物的符号记录&#xff0c; 可以是数字、 文字、图形、图像、声音、语言等&#xff0c;数据有多种形式&#xff0c;它们都可以经过数字化后存入计算机。 1.2数据库 存储数据的仓库&#xff0c;是长期存放在计算机内、有组织、可共享的大量数据…

C++初学者指南-5.标准库(第一部分)--标准库最小/最大算法

C初学者指南-5.标准库(第一部分)–标准库min/max算法 文章目录 C初学者指南-5.标准库(第一部分)--标准库min/max算法minmaxminmaxclamp (C17)min_elementmax_elementminmax_element相关内容 C标准库算法是一块新领域&#xff1f;⇒简短介绍 min min(a, b) → a 如果 a < b则…

全国产服务器主板:搭载飞腾FT2000+/64处理器的高性能加固服务器

近期很多朋友咨询全国产化的服务器主板。搭载的是飞腾FT-2000/64的全国产化服务器主板。他的主要特点是&#xff1a;①丰富的PCIe、千兆以太网、SATA接口&#xff0c;可用作数据处理、存储、通信服务器&#xff1b;②​​​​​​​板载独立显示芯片&#xff0c;对外HDMI/VGA/L…

C语言第5天作业 7月16日

目录 1.求1000以内所有的质数。 2.有1、2、3、4个数字&#xff0c;能组成多少个互不相同且无重复数字的三位数&#xff1f;都是多少&#xff1f; 3.猴子吃桃问题 4.判断最大值 1.求1000以内所有的质数。 质数&#xff1a;只能够1和它本身整除 #include <stdio.h> in…

Java 快速入门学习 -- Day 2

Java 快速入门 Ⅱ 学习视频maven&#xff08;图书管理员&#xff09;IDEA使用 maven框架MyBatis① MyBatis 是持久层框架② MyBatis 是 ORM 框架③ 搭建第一个 MyBatis 框架1、创建数据库表&#xff08;wy数据库 t_book 表&#xff09;2、创建maven 项目3、添加依赖4、创建 My…

万界星空科技MES系统生产计划管理的功能

MES系统&#xff08;Manufacturing Execution System&#xff0c;制造执行系统&#xff09;的生产计划管理功能是其核心功能之一&#xff0c;旨在将企业的生产计划转化为实际的生产操作&#xff0c;并通过实时监控和调整来确保生产活动的顺利进行。以下是MES系统生产计划管理功…

关于 Qt输入法在arm特定的某些weston下出现调用崩溃 的解决方法

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140423667 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…

算法篇 滑动窗口 leetCode 水果成篮

水果成蓝 1.题目描述2.图形分析2.1原理解释2.2 怎么想出使用滑动窗口2.3 图形分析 3.代码演示 1.题目描述 2.图形分析 2.1原理解释 2.2 怎么想出使用滑动窗口 2.3 图形分析 3.代码演示

C语言数组进阶探索

1、数组名含义 在C语言程序中&#xff0c;数组的出现有两种可能的含义&#xff1a; &#xff08;1&#xff09;代表整个数组 &#xff08;2&#xff09;代表其首元素的地址 当出现以下情形时&#xff0c;数组代表的是整个数组&#xff1a; &#xff08;1&#xff09;在数组定义…

Zabbix × openGauss完成兼容 | 信创路上,得其法则事半功倍

在当今快速发展的信息技术领域&#xff0c;数据库作为核心组件之一&#xff0c;其性能、可靠性和兼容性一直是企业和开发者关注的焦点。 近期&#xff0c;Zabbix与openGauss完成了兼容性认证&#xff0c;经过严格联合测试&#xff0c;双方产品实现完全兼容&#xff0c;整体运行…

搭建个人智能家居 7 - 空气颗粒物检测

搭建个人智能家居 7 - 空气颗粒物检测 前言说明PMS5003ESPHomeHomeAssistant结束 前言 到目前为止&#xff0c;我们这个智能家居系统添加了4个外设&#xff0c;分别是&#xff1a;LED灯、RGB灯、DHT11温度传感器和SGP30。今天继续添加环境测量类传感器“PMS5003空气颗粒物检测…

前端JS特效第45集:js实现图片放大和拖拽特效

js实现图片放大和拖拽特效&#xff0c;先来看看效果&#xff1a; 部分核心的代码如下(全部代码在文章末尾)&#xff1a; <!DOCTYPE html> <html> <head><meta charset"utf-8"><title>js实现图片放大和拖拽特效</title><meta…

开放式耳机哪个品牌最好?2024年度首发推荐榜单来了!

在很多专业运动人士中&#xff0c;开放式耳机正变得越来越受欢迎。无论是享受纯净的音质、沉浸式的听觉体验&#xff0c;还是舒适度和通透感方面的追求&#xff0c;开放式耳机都展现出了独特的魅力。本文将带您深入探索开放式耳机的世界&#xff0c;揭示其不可忽视的优点和无限…

拒绝废话:computed、watch和methods的区分和使用场景

computed、watch和methods是用于处理数据和响应数据变化的不同方式&#xff0c;三者之间有什么不同呢&#xff0c;贝格前端工场作为10年前端老司机&#xff0c;用浅显的语言给大家分享一下。 computed&#xff1a; computed属性是用来定义一个基于依赖的响应式属性。它会根据…

CVPR2024论文解读|对齐人类审美!MPS让图像生成评估更“懂你”

导读 当人类从不同角度评估不同类型的图像时&#xff0c;偏好结果会有所不同。因此&#xff0c;为了学习多维的人类偏好&#xff0c;我们提出人类多元偏好模型&#xff08;MPS&#xff09;&#xff0c;这是第一个评估文本生成图像的多维评分模型。MPS在3个公开数据集上表现出色…

医疗设备安全、可靠,国产大功率医疗电源功不可没,旭之源医疗电源拥有高可靠性、优异EMC性能、满足医疗认证等优势!

我国作为人口大国&#xff0c;人均医疗资源相较于发达国家仍有不足&#xff0c;医疗健康产业还有很大提升空间。卡脖子的现象在医疗器械中十分明显&#xff0c;这也是医疗产业重点需要解决的。“国产化”便是有效的解决方案。 受益于医疗行业对产品自主可控意识的提升&#xff…

MySQL----初始数据类型

前言 一、tinyint 范围&#xff1a;-128-----127 在MySQL中&#xff0c;整型可以指定是有符号的和无符号的&#xff0c;默认是有符号的。可以通过UNSIGNED来说明某个字段是无符号的。如果我们向mysqlt特定的类型中插入不合法的数据&#xff0c;Mysq一般会直接拦截&#xff0c…

【python】Python高阶函数--map函数的详细语法分析与应用实战

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…