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

数据结构之《二叉树》(下)

在二叉树(中)了解了堆的相关概念后还实现了堆,并且还实现了堆排序,以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构,会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树,接下来就开始本篇的学习吧!
 


1.链式二叉树的结构

要实现链式结构的二叉树,首先就要将二叉树的结构设计好,也就是要将二叉树结点的结构设计好;要将各结点关联起来通常的方法是链表中每个结点由三个域组成数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 ,其结构如下:

typedef int BTDataType;
// 二叉树链式结构
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;}BTNode;

在实现链式结构的二叉树的程序中是将程序的文件分为以下三个文件

 

2.二叉树的创建

由于在实现链式结构的二叉树中不同于堆一样都是完全二叉树,因此这就使得二叉树的结构较为多样,这时我们就不再去像前面顺序结构的二叉树一样实现插入删除等功能,直接手动的创建一个二叉树,该函数的返回值就为二叉树的根结点

BTNode* CreateTree()
{BTNode* node1 = NewNode(1);BTNode* node2 = NewNode(2);BTNode* node3 = NewNode(3);BTNode* node4 = NewNode(4);BTNode* node5 = NewNode(5);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;return node1;
}

3. 前中后序遍历

在实现了链式二叉树的结构后接下来就可以来实现二叉树的前中后序遍历,在此之前先来了解前中后序遍历的概念

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
(1)前序遍历(Preorder Traversal 亦称先序遍历):访问根结点的操作发生在遍历其左右树之前

访问顺序为:根结点、左子树、右子树
(2)中序遍历(Inorder Traversal):访问根结点的操作发生在遍历其左右子树之中(间)
访问顺序为:左子树、根结点、右子树
(3)后序遍历(Postorder Traversal):访问根结点的操作发生在遍历其左右子树之后
访问顺序为:左子树、右子树、根结点

来通过以下的二叉树示例来进一步理解以上的遍历规则
前序遍历: 
在以上图示的二叉树中,若要进行前序遍历则先要访问跟结点A,之后再访问A的左结点B,之后访问B的左结点D,再访问D的左节点再访问D的右结点,因为D的左节点和右结点都为NULL所以返回去访问B的右结点,因为B的右结点为NULL所以返回去访问A的右结点C,之后访问C的左结点E,再访问E的左节点再访问E的右结点,因为E的左节点和右结点都为NULL所以返回去访问F结点

因此通过以上分析就可以得出前序遍历结果为: A  B  D  C  E  F

中序遍历:
在以上图示的二叉树中,若要进行中序遍历则先要访问跟结点D的左结点,但因为D的左右结点都为NULL,所以先访问结点D,之后访问D的跟结点B,因为B的右结点为NULL,再访问B的跟结点A,之后因为E的左右结点都为NULL,所以先访问结点E,再访问E的跟节点C,之后访问C的右结点F

 因此通过以上分析就可以得出中序遍历结果为:D  B  A  E  C  F

后序遍历:
在以上图示的二叉树中,若要进行后序遍历则先要访问跟结点D的左结点,但因为D的左结点为NULL,之后再访问D的右结点,但因为D的右结点为NULL所以先访问结点D,之后访问B的右结点,但因为B的右结点为NULL,所以之后访问结点B,之后因为E的左右结点都为NULL,所以先访问结点E,之后再访问C的右节点F,再访问节点C,最后再访问C的跟结点A

因此通过以上分析就可以得出中序遍历结果为:D  B  E  F  C  A

完成了以上二叉树的示例的分析接下来我们就来试着实现前中后序遍历的代码


3.1前序遍历

先是在Tree.h文件内完成前序遍历函数的声明

//前序遍历
void PreOrder(BTNode* root);

将该函数命名为PreOrder函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义

以下前序遍历函数是一个递归函数递归的结束的结束条件是当访问的结点值为NULL时
使用printf将结点内的值打印出

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}
图解遍历

我们来通过以下示例将前序遍历的的递归过程完整的展示一遍

以下就是该二叉树在前序遍历函数中的函数递归栈帧图,在这当中红色的线表示递推过程,绿色的线表示回归的过程 

 3.2中序遍历

先是在Tree.h文件内完成中序遍历函数的声明

//中序遍历
void InOrder(BTNode* root);

将该函数命名为InOrder函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义
以下中序遍历函数是一个递归函数
递归的结束的结束条件是当访问的结点值为NULL时
使用printf将结点内的值打印出

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}

图解遍历

我们来通过以下示例将中序遍历的的递归过程完整的展示一遍

以下就是该二叉树在中序遍历函数中的函数递归栈帧图,在这当中红色的线表示递推过程,绿色的线表示回归的过程 

 

3.3后序遍历 

先是在Tree.h文件内完成后序遍历函数的声明

//后序遍历
void PostOrder(BTNode* root);

将该函数命名为PostOrder函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义
以下后序遍历函数是一个递归函数
递归的结束的结束条件是当访问的结点值为NULL时
使用printf将结点内的值打印出

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

图解遍历

我们来通过以下示例将后序遍历的的递归过程完整的展示一遍

以下就是该二叉树在后序遍历函数中的函数递归栈帧图,在这当中红色的线表示递推过程,绿色的线表示回归的过程 

4.结点个数以及高度等

在实现了链式二叉树的结构和前中后序遍历后接下来我们来试着实现一些求二叉树结点,层次等的函数


4.1二叉树结点个数

先是在Tree.h文件内完成二叉树结点个数函数的声明

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

 将该函数命名为BinaryTreeSize,函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义

在求二叉树的函数中你可能会想到用一个变量size来作结点个数的计数变量,那么我们就试着使用这种方法来实现二叉树结点个数的个数

int BinaryTreeLeafSize(BTNode* root,int size)
{if (root == 0){return 0;}size++;BinaryTreeLeafSize(root->left,size) ;BinaryTreeLeafSize(root->right,size);return size;
}

以上就是按照这种想法来实现的函数,但其实以上的函数是存在非常明显的问题的,你能观察出问题吗?

问题就是以上的函数使用传size的值这就会让函数在递归过程中在各个函数栈帧中size的改变不会影响到其兄弟结点的size值,因此就需要对以上函数做出改变

int BinaryTreeLeafSize(BTNode* root,int* psize)
{if (root == 0){return 0;}(*psize)++;BinaryTreeLeafSize(root->left,psize) ;BinaryTreeLeafSize(root->right,psize);return *psize;
}

以上就是改变后的函数,将计数的变量size传值改为传址,这样就可以让每个函数栈帧内*psize的改变影响到其兄弟结点的函数栈帧。

但以上这种算法需要在调用函数前创建一个用于计数的变量,而且在每次调用完函数BinaryTreeLeafSize后还需要将用于计数的变量重新赋值为0,否则就会使得下一次调用函数得到的结点个数还会包含上一次调用函数得到的结点个数因此这种算法是不太好的,我们需要在思考其他的算法

以下就是就是不使用计数的方法来实现的函数,是将二叉树的结点直接返回
函数递归的结束条件就是当结点为NULL时


// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

以上函数在以下示例中就会如下形式递归

4.2 二叉树叶子结点个数 

要实现求二叉树中的叶子结点个数函数首先来复习一下什么是叶子结点

我们知道度为0的结点称为叶结点,叶子结点的特征就是无孩子结点也就是其链式结构当中结点内两个指针都指向NULL,例如在以下示例的叶子节点就是结点3、结点5、结点6

复习了叶子结点的概念接下来就可以来实现函数代码了
 

先是在Tree.h文件内完成二叉树叶子结点个数函数的声明

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

 将该函数命名为BinaryTreeLeafSize,函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义 

以下函数也是通过函数递归的方式来实现的,递归的结束条件是当结点为NULL时,此时就返回0
当结点的左孩子和右孩子都为NULL就返回1

// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right==NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);}

4.3二叉树第k层结点个数 

首先先来通过一个示例来复习第k层节点数的概念,例如以下示例二叉树中第三层节点数就为3

 

 要实现函数先是在Tree.h文件内完成二叉树第k层结点个数函数的声明

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

 将该函数命名为BinaryTreeLeafSize,函数的参数有两个,第一个是指向二叉树结点的结构体指针,第二个是想要得到的二叉树节点数的层序号

之后就是在Tree.c内完成函数的定义 
以下函数也是通过函数递归的方式来实现的,递归的结束条件是当结点为NULL时,此时就返回0
在函数中当调用该函数时k值都减1,当k值为1是就表明该1结点是在第k层就返回1

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}

4.4二叉树的深度/高度 

在实现二叉树的高度/深度函数前先来复习一下高度/深度的概念,树的高度或深度就表示树中结点的最大层次

例如以下示例二叉树中深度就为3

 要实现函数先是在Tree.h文件内完成二叉树的深度函数的声明

//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

将该函数命名为BinaryTreeDepth,函数的参数是指向二叉树结点的结构体指针

之后就是在Tree.c内完成函数的定义 
在二叉树中的深度就为左子树的深度或者右子树的深度再加上1,在这当中取左右子树中深度大的一边,以下代码中使用三目操作符 ?:来实现

//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int L = BinaryTreeDepth(root->left);int R = BinaryTreeDepth(root->right);return L> R ? 1 + L : 1 +R;
}

4.5二叉树查找值为x的结点 

先是在Tree.h文件内完成查找值为x的结点函数的声明

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

将该函数命名为BinaryTreeFind函数的参数有两个,第一个是指向二叉树结点的结构体指针,第二个是要查找的数据

之后就是在Tree.c内完成函数的定义 
在以下函数中如果找到了值为x的结点也就是当root->val等于x时就返回这个结点的指针,并且在函数在左子树中找到就不会再去右结点中查找

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->val == x){return root;}BTNode* tmp1=BinaryTreeFind(root->left,x);if (tmp1 != NULL){return tmp1;}BTNode*tmp2=BinaryTreeFind(root->right, x);if (tmp2 != NULL){return tmp2;}return NULL;
}

4.6二叉树的销毁 

先是在Tree.h文件内完成二叉树的销毁函数的声明

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

将该函数命名为BinaryDestory函数的的参数为指向结点的结构体指针的地址
由于要在释放结点空间后将指针置为NULL,因此函数的参数为二级指针,这样就可以使得形参的改变影响实参,不用再手动置指针为NULL

之后就是在Tree.c内完成函数的定义 
在此函数中是使用后序遍历的方式使得能找到结点的孩子结点,在此之后再释放结点

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

5.层序遍历 

在本篇开始我们实现了前中后序遍历,接下来我们接着来实现层序遍历,先来了解层序遍历的概念
 

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

在层序遍历中由于要将二叉树中的结点按照层序来遍历,这就使得我们不能再像之前的遍历一样使用函数递归的方法来实现,这时就要再思考其他的方法

在此我们实现层序遍历需要额外借助数据结构:队列 

在此使用队列是来完成以下操作:
先将二叉树中的根结点入队列,之后读取对头元素后出队列,若结点的左、右孩子结点存在,就将孩子结点入队列,之后重复以上操作直到队列为空

注:在实现层序遍历的代码前先要将之前实现的队列文件Queue.c和Queue.h添加到程序当中

 并且要将之前的队列当中定义队列的结构的结构体中的数据类型改为指针类型BinaryTreeNode*

//队列结构的定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType data;//节点内的数据struct QueueNode* next;//指向下一个节点的指针}QueueNode;

完成以上操作就可以来实现层序遍历的代码了

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//将二叉树根节点入队QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头BTNode* tmp=QueueFront(&q);printf("%d ", tmp->val);//出队QueuePop(&q);if (tmp->left){QueuePush(&q, tmp->left);}if (tmp->right){QueuePush(&q, tmp->right);}}QueueDestory(&q);//销毁队列}

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

之前我们了解了完全二叉树相关的概念和性质,那么如果要写一个函数来判断是否为完全二叉树该如何来实现呢?

 接下来就来看看完全二叉树和非完全二叉树层序遍历的有什么不同,来看以下示例

以上为非完全二叉树,层序遍历结果为A B C D NULL E F NULL NULL NULL NULL NULL NULL 

而在以上完全二叉树中,层序遍历结果就为A B C D F E NULL NULL NULL NULL NULL NULL NULL

通过以上两个二叉树的示例就可以得出如果一个二叉树是完全二叉树则在层序遍历时当遍历到NULL时二叉树二叉树所有有效结点都已经遍历完,而如果是非完全二叉树就会在层序遍历中遍历到NULL后二叉树可能还有有效结点没有遍

接下来就来实现判断是否是完全二叉树的代码,以下函数和层序遍历一样也是用到队列,但和层序遍历中有所不同,无论结点的孩子结点为不为空都入队列。当取出的队头元素为NULL时就跳出第一个while循环,之后的while循环用来判断队列剩下的是否还有有效元素,有则说明该二叉树不是完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp == NULL){break;}QueuePush(&q,tmp->left);QueuePush(&q, tmp->right);}while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp != NULL){QueueDestory(&q);//销毁队列return false;}}QueueDestory(&q);//销毁队列return true;}

 

 7.完整代码

Tree.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef int BTDataType;
// 二叉树链式结构
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;}BTNode;//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//层序遍历
void LevelOrder(BTNode* root);// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

Tree.c

#include"Tree.h"
#include"Queue.h"//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//将二叉树根节点入队QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头BTNode* tmp=QueueFront(&q);printf("%d ", tmp->val);//出队QueuePop(&q);if (tmp->left){QueuePush(&q, tmp->left);}if (tmp->right){QueuePush(&q, tmp->right);}}QueueDestory(&q);}// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right==NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);}// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int L = BinaryTreeDepth(root->left);int R = BinaryTreeDepth(root->right);return L> R ? 1 + L : 1 +R;
}// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->val == x){return root;}BTNode* tmp1=BinaryTreeFind(root->left,x);if (tmp1 != NULL){return tmp1;}BTNode*tmp2=BinaryTreeFind(root->right, x);if (tmp2 != NULL){return tmp2;}return NULL;
}// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;}

 test.c

#include"Tree.h"BTNode* NewNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}BTNode* CreateTree()
{BTNode* node1 = NewNode(1);BTNode* node2 = NewNode(2);BTNode* node3 = NewNode(3);BTNode* node4 = NewNode(4);BTNode* node5 = NewNode(5);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;return node1;
}void testTree()
{BTNode* node1=CreateTree();PreOrder(node1);printf("\n");InOrder(node1);printf("\n");PostOrder(node1);printf("结点个数:%d\n",BinaryTreeSize(node1));printf("叶子结点个数:%d\n", BinaryTreeLeafSize(node1));printf("第k层结点个数:%d\n", BinaryTreeLevelKSize(node1,3));printf("深度:%d\n", BinaryTreeDepth(node1));BTNode* find=BinaryTreeFind(node1,13);printf("%s", find== NULL ? "找不到!" : "找到了");LevelOrder(node1);bool d=BinaryTreeComplete(node1);printf("%s", d == true ? "是完全二叉树" : "不是完全二叉树");BinaryTreeDestory(&node1);
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//队列结构的定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType data;//节点内的数据struct QueueNode* next;//指向下一个节点的指针}QueueNode;typedef struct Queue
{struct QueueNode* phead;//指向第一个节点的指针struct QueueNode* ptail;//指向尾节点的指针int size;//节点的个数}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队列头数据
QDataType QueueFront(Queue* pq);
//取队列尾数据
QDataType QueueBack(Queue* pq);
//队列有效数据个数
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* Next = pcur->next;free(pcur);pcur = Next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* Next = pq->phead->next;free(pq->phead);pq->phead = Next;}pq->size--;}//取队列头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队列尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;}//队列有效数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

 

 

 

以上就是二叉树(下)的全部内容了,本篇之后我们就学习完了二叉树的所有基本知识,接下来将会在之后的篇章中写一些二叉树相关的算法题,未完待续……

相关文章:

数据结构之《二叉树》(下)

在二叉树(中)了解了堆的相关概念后还实现了堆&#xff0c;并且还实现了堆排序&#xff0c;以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构&#xff0c;会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树&#xff0c;接下来就开始本篇的学习吧&…...

用Python打造精彩动画与视频,9.3 项目案例分享与反思

第九章&#xff1a;综合项目 9.3 项目案例分享与反思 在本节中&#xff0c;我们将分享几个成功的项目案例&#xff0c;并进行反思总结。这些案例将展示如何将前面所学的Python技术运用于实际项目中&#xff0c;同时我们将讨论项目中的挑战和解决方案&#xff0c;以及从中得到…...

分布式主键 详解

文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题 问题出现 使用ShardingSphere框架自带的雪花算法生成分布式主…...

synchronzed为什么要升级为重量级锁,轻量级锁不好吗?

轻量级锁和重量级锁各有其适用场景和优缺点。轻量级锁旨在减少在无竞争情况下的同步开销&#xff0c;而重量级锁则在竞争激烈的情况下确保线程的同步。以下是为什么在某些情况下需要将轻量级锁升级为重量级锁的原因&#xff0c;以及轻量级锁的不足之处&#xff1a; 为什么需要…...

.NET 项目中发送电子邮件异步处理和错误机制的解决方案

在 .NET 中处理电子邮件&#xff0c;可以使用多种技术和库来实现高效的电子邮件发送、接收和管理。以下是一些常见的解决方案和最佳实践&#xff1a; 目录 1. 使用 SMTP 发送电子邮件 2. 使用 IMAP/POP3 接收电子邮件 3. 异步处理电子邮件 4. 处理大型邮件队列 5. 错误处…...

如何在银河麒麟操作系统上搭建 Electron (含 Electron 打包指南)

本次教程所用版本 Eletron版本&#xff1a;31.3.1 Electron-packager版本&#xff1a;17.1.2 VScode版本&#xff1a;1.92.0 Node版本&#xff1a;18.19.0 npm版本&#xff1a;10.2.3 前言&#xff1a; 随着跨平台应用开发的需求日益增长&#xff0c;Electron 和 Qt 成为…...

小怡分享之数据结构基础知识准备

前言&#xff1a; &#x1f308;✨之前小怡给大家分享了JavaSE的知识&#xff0c;今天小怡要给大家分享一下数据结构基础知识。 一、初识集合框架 1.什么是集合框架 Java集合框架Java Collection Framework&#xff0c; 又称为容器container&#xff0c;是定义在Java.util 包…...

Linux安全与高级应用(三)深入探索MySQL数据库:安装、管理与安全实践

文章目录 深入探索MySQL数据库&#xff1a;安装、管理与安全实践MySQL数据库简介MySQL的安装与配置编译安装MySQL配置MySQL服务 MySQL数据库的基本操作数据库的创建与删除表的创建与管理数据记录的增删改查 MySQL用户管理与权限设置MySQL数据库的备份与恢复数据库备份数据库恢复…...

基于jsp的宠物领养与服务管理系统(源码+论文+部署讲解等)

博主介绍&#xff1a;✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍&#xff1a;我是程序员阿龙&#xff…...

基于STM32F407+NBIOT+华为云IOT平台设计的环境检测系统

基于STM32F407NBIOT华为云IOT平台设计的环境检测系统实现的功能&#xff1a; 【1】能够采集本地环境的温度、湿度、烟雾浓度&#xff0c;火光信息&#xff0c;在OLED显示屏上显示。 如果检测到烟雾、温度、火光超过阀值会触发蜂鸣器报警。 【2】能够通过NBIOT将本地设备采集的信…...

工具方法 - 如何表扬小孩子

赞扬小朋友的表现可以通过多种方法来进行&#xff0c;以鼓励他们的积极行为和努力&#xff0c;增强他们的自信心和动力。以下是一些有效的赞扬方法&#xff1a; 1. 具体表扬&#xff1a;指出具体的行为或成就&#xff0c;而不是泛泛地说“你很棒”。例如&#xff0c;“你今天很…...

【扒模块】DySample

逐行注释 import torch import torch.nn as nn import torch.nn.functional as F import warnings# 忽略警告信息&#xff0c;这通常用于开发过程中&#xff0c;避免警告干扰输出结果 warnings.filterwarnings(ignore)# 定义一个函数&#xff0c;用于对神经网络模块的权重进行…...

数学建模之数据分析【四】:变量及其分析

文章目录 一、单变量数据1.1 单变量数据1.2 单变量分析的要点&#xff1a; 二、双变量数据2.1 双变量数据2.2 双变量分析的要点 三、多元数据3.1 多元数据3.2 多元分析的要点 四、单变量&#xff0c;双变量和多变量数据之间的区别 公众号/小红书: 快乐数模 CSDN: 清上尘 本文&a…...

iOS ------ UIKit相关

UIView和CALayer UIView UIView表示屏幕上的一块矩形区域&#xff0c;它是基本上iOS中所有可视化控件的父类。UIView可以管理矩形区域里的内容&#xff0c;处理矩形区域的事件&#xff0c;包括子视图的管理以及动画的实现。 UIKit相关类的继承关系 UIView继承自UIResponde…...

24/8/9算法笔记 随机森林

"极限森林"&#xff08;Extremely Randomized Trees&#xff0c;简称ERT&#xff09;是一种集成学习方法&#xff0c;它属于决策树的变体&#xff0c;通常被归类为随机森林&#xff08;Random Forest&#xff09;的一种。极限森林的核心思想是在构建决策树时引入极端…...

如何在前后端分离项目中,使用Spring Security

使用 WebSecurityConfigurationAdapter 在前后端分离的架构中&#xff0c;通常使用 Token 进行认证和授权是一种常见的做法。Token 可以是 JSON Web Token&#xff08;JWT&#xff09;&#xff0c;用于在客户端和服务器之间传递身份信息和访问控制信息。下面我将详细介绍如何在…...

c#怎么折叠代码快捷

在C#中&#xff0c;‌你可以使用快捷键来折叠或展开代码&#xff0c;‌以便更好地管理和浏览代码。‌以下是一些常用的快捷键&#xff1a;‌ 折叠所有方法&#xff1a;‌使用Ctrl M O。‌折叠或展开当前方法&#xff1a;‌使用Ctrl M M。‌展开所有方法&#xff1a;‌使用…...

数据库篇--八股文学习第十七天| 什么是慢查询?原因是什么?可以怎么优化?;undo log、redo log、binlog 有什么用?

1、什么是慢查询&#xff1f;原因是什么&#xff1f;可以怎么优化&#xff1f; 答&#xff1a; 数据库查询的执行时间超过指定的超时时间时&#xff0c;就被称为慢查询。 原因&#xff1a; 查询语句比较复杂&#xff1a;查询涉及多个表&#xff0c;包含复杂的连接和子查询&…...

插件、cookie存储,json,ajax详解

1.插件 下载地址&#xff1a;http://github.com/carhartl/jquery-cookie/zipball/v1.4.1 使用文档&#xff1a;jquery-cookie(github.com) 2.存储 初学前端用的是localStorage和sessionStorage&#xff0c;后来又引入了cookie进行存储。 localStorage使用如下 sessionStor…...

快速上手Spring Boot

快速上手Spring Boot (qq.com)...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...