当前位置： 首页 > news >正文

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

news 2025/7/1 8:43:41

目录

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的结点称为叶结点； 如上图：B、C、H、I、P...等结点为叶结点。

(3)非终端结点或分支结点：度不为 0 的结点； 如上图： D 、 E 、 F 、 G...等结点为分支结点。
(4)双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点。
(5)孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
(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;
}

相关文章：

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堆…...

编程日记 2024/7/19 13:23:50

VScode：前端项目中yarn包的安装和使用

一、首先打开PowerShell-管理员身份运行ISE 输入命令&#xff1a; set-ExecutionPolicy RemoteSigned 选择“全是”&#xff0c;表示允许在本地计算机上运行由本地用户创建的脚本&#xff0c;没有报错就行了 二、接着打开VScode集成终端&#xff0c;安装yarn插件 输入 npm ins…...

编程日记 2024/7/19 13:22:49

cmake configure_package_config_file指令详解

在 CMake 中&#xff0c;configure_package_config_file 命令用于生成包配置文件&#xff08;Package Configuration File&#xff09;&#xff0c;这些文件用于指定如何使用和链接某个库或工具。通常情况下&#xff0c;这些文件用于支持 CMake 的 find_package 命令来查找和加…...

编程日记 2024/7/19 13:19:46

准备跳槽了（仍然底层为主，ue独立游戏为辅）

思考再三&#xff0c;准备跳槽了。 一、跳槽原因&#xff1a; 今年经济形势非常不好。那我为什么还要跳槽呢&#xff1f;因为干不下去了。公司是末位淘汰制&#xff0c;而我绩效垫底了。给我的整改措施中&#xff0c;部门经理让我三个月搞定60个bug&#xff0c;我觉得简直是送…...

编程日记 2024/7/19 13:15:43

汽车免拆诊断案例 | 卡罗拉急加速抖动故障排除

车型信息 2017年改款卡罗拉&#xff0c;排量1.2T&#xff0c;行驶里程48800公里。 故障现象 车辆不管在什么状态下&#xff0c;只要是平缓加速&#xff0c;都不会有抖动。车辆静止时&#xff0c;急加速时&#xff0c;也不会有抖动。但是车速达40公里/小时以上&#xff0c;急加…...

编程日记 2024/7/19 13:11:40

【JAVA】深入理解Hutool中的Pair、Triple和Tuple：组合数据的新方式，方法返回多个值，嘎嘎香，谁用谁知道，比原生好用更强大

Hutool 是一个开源的 Java 工具库&#xff0c;提供了丰富且实用的功能&#xff0c;旨在减少 Java 程序员在日常开发中重复造轮子的工作。在 Hutool 中&#xff0c;Pair、Triple 和 Tuple 是三种用于组合和存储不同数量相关联数据的类。以下是这三个类的简介&#xff1a; 1、添…...

编程日记 2024/7/19 13:08:37

modulepreload 对性能的影响

一、正面影响 减少加载时间&#xff1a; modulepreload 可以让浏览器提前下载模块脚本&#xff0c;减少页面加载时间&#xff0c;特别是对于依赖较多的复杂应用。这种预加载可以让浏览器在遇到 modulepreload 链接时立即开始下载&#xff0c;而不是等到实际需要时才下载提升用…...

编程日记 2024/7/19 13:07:35

问题：向上对齐对象的快捷键是: #学习方法#笔记

问题&#xff1a;向上对齐对象的快捷键是: A、T B、L C、R D、W 参考答案如图所示...

编程日记 2024/7/19 13:06:34

C# 4.List

comboBox使用的下拉框 Lsit 列表 1 创建List对象 List<string> list new List<string>(); 2 Add给list 添加元素 list.Add("吃饭"); list.Add("睡觉"); list.Add("打豆豆"); 3 删除一个元素 list.Remove("吃饭"); // 删…...

编程日记 2024/7/19 13:04:31

界面控件DevExpress Blazor UI v24.1 - 发布全新TreeList组件

DevExpress Blazor UI组件使用了C#为Blazor Server和Blazor WebAssembly创建高影响力的用户体验&#xff0c;这个UI自建库提供了一套全面的原生Blazor UI组件&#xff08;包括Pivot Grid、调度程序、图表、数据编辑器和报表等&#xff09;。 DevExpress Blazor控件目前已经升级…...

编程日记 2024/7/19 12:59:26

docker默认存储地址 var/lib/docker 满了，换个存储地址操作流程

1. 查看docker 存储地址 docker info如下 var/lib/docker2、查看内存大小 按需执行 df -h 找超过100M的大文件 find / -type f -size 100M -exec ls -lh {} \; df -Th /var/lib/docker 查找这个文件的容量 df -h 查找所有挂载点 du -hs /home/syy_temp/*1、df -h 2、sud…...

编程日记 2024/7/19 12:58:25

SpringMVC的底层工作原理？

1.用户发送请求至前端控制器DispatcherServlet. 2.DispatcherServlet 收到请求调用 HandlerMapping 处理器映射器 3.HandlerMapping找到具体的处理器(可以根据 xml 配置、注解进行查找&#xff09;&#xff0c;生成处理器及处理器拦截器(如果有则生成)一并返回给DispatcherSe…...

编程日记 2024/7/19 12:57:25

PyTorch 深度学习实践-处理多维特征的输入

视频指路 参考博客笔记 参考笔记二 通过多个线性模型来模拟非线性的空间变换&#xff0c;矩阵计算就是不同维度之间的空间转换 说明&#xff1a;1、乘的权重(w)都一样&#xff0c;加的偏置(b)也一样。b变成矩阵时使用广播机制。神经网络的参数w和b是网络需要学习的&#xff0c…...

编程日记 2024/7/19 12:55:23

常见逻辑漏洞举例

文章目录 简介用户名可枚举验证码可绕过/验证码回传越权访问任意密码修改验证码回传订单金额任意修改URL跳转漏洞短信轰炸找回密码还有很多逻辑漏洞&#xff0c;其实并没有什么技巧&#xff0c;要分析清楚他的业务逻辑&#xff0c;可能很多正常的流程中就存在着逻辑漏洞。 简介…...

编程日记 2024/7/19 12:52:20

FastAPI 学习之路（五十九）封装统一的json返回处理工具

在本篇文章之前的接口&#xff0c;我们每个接口异常返回的数据格式都不一样&#xff0c;处理起来也没有那么方便&#xff0c;因此我们可以封装一个统一的json。 from fastapi import status from fastapi.responses import JSONResponse, Response from typing import Unionde…...

编程日记 2024/7/19 12:50:17

tg小程序前端-dogs前端源码分析

tg小程序前端-dogs前端源码分析 前端源码 index.html <!DOCTYPE html> <html lang="en"><head><script src="https://telegram.org/js/telegram-web-app.js" onload="window.Telegram.WebApp.expand(); window.Telegram.WebA…...

编程日记 2024/7/19 12:48:15

Linux——多路复用之select

目录 前言 一、select的认识 二、select的接口 三、select的使用 四、select的优缺点 前言 在前面&#xff0c;我们学习了五种IO模型&#xff0c;对IO有了基本的认识&#xff0c;知道了select效率很高&#xff0c;可以等待多个文件描述符&#xff0c;那他是如何等待的呢&a…...

编程日记 2024/7/19 12:45:12

探索.NET内存之海：垃圾回收的艺术与实践

简述 在.NET的广阔天地中&#xff0c;内存管理如同航海中的罗盘&#xff0c;指引着程序的稳健运行和性能的极致优化。作为软件工程师&#xff0c;我们时常在代码的海洋中航行&#xff0c;而内存管理则是确保航程顺畅的关键。本文将带您深入.NET的内存管理世界&#xff0c;一探垃…...

编程日记 2024/7/19 12:42:09

路由数据获取及封装方法

数据库设计 自联表 定义tree字段 public class LabelValue{public int label { get; set; }public string? value { get; set; }public List<LabelValue> children { get; set; }}获取路由方法 public Response<object> getMenuList() {Response<object>…...

编程日记 2024/7/19 12:40:07

Visual Studio Code 实现远程开发

Background 远程开发是指开发人员在本地计算机上进行编码、调试和测试&#xff0c;但实际的开发环境、代码库或应用程序运行在远程服务器上。远程开发的实现方式多种多样&#xff0c;包括通过SSH连接到远程服务器、使用远程桌面软件、或者利用云开发环境等。这里我们是使用VSCo…...

编程日记 2024/7/19 12:39:06

Linux 文件类型，目录与路径，文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

编程新知 2025/6/30 8:13:12

脑机新手指南（八）：OpenBCI_GUI：从环境搭建到数据可视化（下）

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

编程新知 2025/6/21 17:27:56

令牌桶 滑动窗口-＞限流 分布式信号量-＞限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

编程新知 2025/6/25 15:50:42

相机Camera日志分析之三十一：高通Camx HAL十种流程基础分析关键字汇总（后续持续更新中）

【关注我，后续持续新增专题博文，谢谢！！！】 上一篇我们讲了：有对最普通的场景进行各个日志注释讲解，但相机场景太多，日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志，通过下列分类关键字搜索，即可清晰的分析不同场景的相机运行流程差异…...

编程新知 2025/6/15 13:22:13

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

编程新知 2025/6/24 0:45:23

Linux离线（zip方式）安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

编程新知 2025/6/16 16:58:04

MinIO Docker 部署：仅开放一个端口

MinIO Docker 部署：仅开放一个端口 在实际的服务器部署中，出于安全和管理的考虑，我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务，支持 Docker 部署，但默认情况下它需要两个端口：一个是 API 端口（用于存储和访问数据），另一个是控制台端口（用于管理界面…...

编程新知 2025/6/21 15:09:46

STM32---外部32.768K晶振（LSE）无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

编程新知 2025/6/26 3:05:43

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步：前置条件，启用 OLE 自动化方式 1：使用 SQL 实现启用 OLE 自动化方式 2：Sql Server 2005启动OLE自动化方式 3：Sql Server 2008启动OLE自动化第 2 步：创建存储过程第 3 步：创建触发器扩展 - 如何调试？第 1 步：登录 SQL Server 2008第 2 步…...

编程新知 2025/6/21 2:10:03

论文阅读：Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

编程新知 2025/6/30 4:20:10