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

数据结构:二叉树的链式结构

文章目录

    • 一.前言
    • 二.二叉树遍历
    • 2.1前序遍历/先根遍历
    • 2.2中序遍历/中根遍历
    • 2.3后序遍历/后根遍历
    • 2.4层序遍历
    • 2.5二叉树的销毁
    • 三.二叉树节点个数
    • 四.二叉树叶子节点的个数
    • 五.二叉树的高度
    • 六.二叉树第K层的节点个数
    • 七.找二叉树的节点
    • 八.题目
    • 8.1判断单值二叉树
    • 8.2相同的树
    • 8.3另一棵子树
    • 8.4二叉树的创建与遍历
    • 8.5判断是否为完全二叉树
    • 8.6前序遍历的题目
    • 8.7对称二叉树
    • 8.8根据前/后序和中序重建树

一.前言

对二叉树不是很熟悉的可以看看这篇文章:二叉树基础。

我们先看看二叉树结构的图片:
在这里插入图片描述
可以发现二叉树表达起来起始非常简单,定义一个有三个成员的结构体,一个成员存数据,另外两个存当前节点的左孩子和右孩子的地址。

但是接下来要学习的不是二叉树的增删查改,你们可能在学习顺序表,链表那些数据结构的时候可能先了解一下它们然后直接上手写这些数据结构的增删查改的函数接口。但是二叉树不一样,二叉树的这种结构本身就不适合这样写,而且增删查改对它也没有意义,如果你需要,完全可以用顺序表,链表它们,而不是用二叉树这种麻烦的结构。链式二叉树的这种结构虽然此时可能没什么用,但学习它可以为后面在学搜索二叉树,红黑树这些打下坚实的基础。

二.二叉树遍历

2.1前序遍历/先根遍历

在这里插入图片描述
前序遍历是,先找到根节点,然后找根节点的左子树,找到左子树之后再找右子树。

首先先将这棵树整体看作三个部分:根,左子树,右子树
在这里插入图片描述

前序遍历是先遍历根所以此时把1找出来。紧接着我们遍历左子树,此时我们要把左子树当成一棵独立的数,也就是跟刚才遍历的思想一样把此时的数也看成三个部分:
在这里插入图片描述

虽然此时2没有右子树,我们仍然当这个空树当成一个整体。此时先遍历根也就是2这个节点,在遍历2的左子树,右子树。现在先遍历2的左子树:
在这里插入图片描述

同理把2的左子树当成一个树,先遍历根也就是3这个节点,在遍历3的左子树,右子树。发现3的左子树,右子树都为空说明3的左子树,右子树都遍历完了。现在3这个节点的根,左子树,右子树都遍历完了,也就是说明2的左子树遍历完了,此时我们要开始遍历2的右子树,但是2的右子树是个空树,所以直接返回,也就是说2这颗树的根,左子树,右子树都遍历完了,也可以认为1这个根的左子树全部遍历完了。
自此我们遍历1这棵树的顺序就是:
1,2,3,NULL,NULL,NULL。
这里NULL的意思是说,我们此时访问到的是个空树。

1的左子树遍历完了,接下来我们要遍历1的右数,一样的将这棵树划分成根,左子树,右子树:
在这里插入图片描述

因为是前序遍历,所以先找到的是4这个根,紧接着访问4的左树:
在这里插入图片描述

同理先访问根节点5,在访问5的左子树,右子树。但是左子树,右子树都为空,直接算访问结束,所以5这颗树就全部访问完成了,也就是说4这棵树的左子树访问结束了,现在开始访问4的右子树。同样:
在这里插入图片描述

现在先访问根节点6在访问6的左子树,右子树,因为两个都是空所以直接返回,现在4的左子树,右子树都访问完成了,也就是说最终1的右子树访问结束了。现在整棵树的根节点,左子树,右子树就全部访问结束了。

这个前序遍历看上去十分复杂,其实就是用了一种分治的思想,我们不是一下子就访问整棵树,而是将问题一步一步划分成子问题。然后得出结果。

接下来我们用代码来实现:

//浅浅的建一个二叉树,这个树的样子就是刚才画的那张图typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;void test2()
{//简单建立一个二叉树BTNode n1;BTNode n2;BTNode n3;BTNode n4;BTNode n5;BTNode n6;n1.data = 1;n2.data = 2;n3.data = 3;n4.data = 4;n5.data = 5;n6.data = 6;n1.left = &n2;n1.right = &n4;n2.left = &n3;n2.right = NULL;n3.left = n3.right = NULL;n4.left = &n5;n4.right = &n6;n5.left = n5.right = NULL;n6.left = n6.right = NULL;
}

现在开始尝试着写一下前序遍历的代码,因为访问的顺序是根左子树,右子树。我们把访问到根节点的时候把这个根节点里面的数据打印出来:

//前序遍历
void PrevOrder(BTNode* root)
{//访问根节点printf("%d ", root->data);
}

随后我们要访问此时根节点的左子树,方法很简单,用递归的思想,把此时跟的左孩子当成一新的棵的节点来看:

//前序遍历
void PrevOrder(BTNode* root)
{printf("%d ", root->data);PrevOrder(root->left);
}

这样就把左子树访问完了,紧接着访问这棵树的右子树:

//前序遍历
void PrevOrder(BTNode* root)
{printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

这样就很好的把这颗树的节点都访问完了,但是还没有完。我们现在考虑一下,这个函数一直走一直走,走到空的时候怎么办?也很容易,此时是个空树的话就直接返回就行,说明这棵树已经访问完了,所以我们在给函数加一个结束条件:

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

注意一定要加在函数的的开头,这样每次在递归的时候先判断一下是否为空,是的话就返回,否则继续向下走。

看一下打印出来的结果:
在这里插入图片描述

这和上面分析的一模一样。有些人可能会疑惑,几行代码就解决了吗?当然,这就是递归的妙用,将一个大的问题转化成很多相似问题的小问题。如果你觉得不可思议的话,我再来话一个递归的流程图,来帮助理解:
在这里插入图片描述

刚开始是1这个节点因为它不是空,走到printf函数这里,然后继续往下走,此时开始递归调用走1的左子树,先打印2这个节点然后继续找2的左子树:

在这里插入图片描述

然后继续往下走先打印3这个节点,然后继续向下走:
在这里插入图片描述

但是3的左子树是空,所以直接返回顺便打印一下NULL。紧接着开始走3的右子树:
在这里插入图片描述

但是右子树同样是空,打印一个NULL然后返回。这样3这个节点所在的函数就走完了。
在这里插入图片描述

做到这里也就是说2的左子树全部走完了,换句话说2所在的这个函数的PrevOrder(root->left);这个函数完成了,继续往后走,最终1这个节点在遍历左子树是的步骤就是下面这些:
在这里插入图片描述

这样1的左子树就全部完成了。右子树我在这里就不去画了。

2.2中序遍历/中根遍历

中序遍历:先遍历左树,在遍历根,最后在遍历右数。

顺序虽然和前序遍历不同,但是思想大致一样:
在这里插入图片描述

这里仍然把整体当作一棵完整的数,但是我们先不打印1这个节点,直接去遍历1的左子树:
在这里插入图片描述

同样先不打印2这个节点,先找2的左子树:
在这里插入图片描述

到这里仍然是一样的先不看3这个节点,先看3的左子树,但是左子树是空所以打印一个NULL就返回,现在再找3这个根节点,最后再找3的右子树,因为也是空所以打印一个NULL返回。这样打印的顺序就是NULL,3,NULL。现在3这棵树就找完了,随后回过头找2这个节点把2也打印出来,再找2的右子树,因为这棵树是个空所以打印个NULL就直接返回。这样1的左子树就全部找完了,此时在打印1这个节点,继续找1的右子树…

右子树的过程也一样,这里就不再赘述,现在直接看代码实现:

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

变化也很简单,既然是中序遍历,就先找此时节点的左子树就行,找完了在打印节点,然后再找右子树。

在看打印结果:
在这里插入图片描述

2.3后序遍历/后根遍历

后序遍历是:先遍历左子树,在遍历右子树,最后遍历这个根节点

经过上面两个遍历的学习,后序遍历应该不会这么难理解。

在这里插入图片描述

遇到1这个节点的时候先不管它,直接去找它的左子树,找一圈找完之后返回来,仍然不管它,继续找右子树,全部找完之后在打印根节点。

直接看代码:

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

再来看结果:
在这里插入图片描述

2.4层序遍历

层序遍历和刚才那三种情况不一样,它是一层一层遍历,像这棵树:
在这里插入图片描述

实际打印出的结果是1,2,4,3,5,6

层序需要用到队列来辅助完成遍历,具体步骤大约是:
在这里插入图片描述

开始先将1这个节点插入到队列中,然后将此时的数据打印出来。然后再把1取出来,顺便把1的两个孩子:左孩子,右孩子插入进去,注意这里队列里存放的是一个节点,而不是这个节点里的数据,因为只是存数据的话,就找不到这个节点的两个孩子了:
在这里插入图片描述

然后再把结点2取出来顺便打印这个节点的数据,再把2的两个孩子插入进去,如果孩子为空就不插入:
在这里插入图片描述

继续把4这个节点取出来打印,并且将4的两个孩子插入进去:
在这里插入图片描述

因为为空就不插入了,所以最后将3,5,6一个一个取出来,当列表为空的时候结束。

这是层序遍历的大致思路。现在用代码来实现,但是我目前还没学C++,只能把C语言自己写的关于队列的函数拿过来用

//二叉树节点的定义
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
/*************************************///队列结构的定义
typedef BTNode* QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//删除
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//入对列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueuePush");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//取出队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//取出队列头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//队列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

层序遍历

//层序遍历
void LevelOrder(BTNode* root)
{//定义一个队列并初始化Queue pq;QueueInit(&pq);//入队列,将根节点放到队列中QueuePush(&pq, root);while(!QueueEmpty(&pq)){//出队列,然后将这个节点的两个孩子传进去QDataType tmp = QueueFront(&pq);QueuePop(&pq);//出队列后顺便把这个节点的值打印出来printf("%c ", tmp->data);//如果某个孩子为空就不放到队列里了if (tmp->left){QueuePush(&pq, tmp->left);}if (tmp->right){QueuePush(&pq, tmp->right);}}QueueDestroy(&pq);
}

最后看看结果:
在这里插入图片描述
在这里插入图片描述

顺序确实是一行一行打印的。

这样确实可以打印出来,现在加个条件,一行一行的打印,像这样:
在这里插入图片描述

这怎么做呢?其实很简单,定义一个新的变量size即可,size代表当前层数的节点个数。
在这里插入图片描述

当1这个节点进到队列之后,可以认为此时的size为1,所以可以在代码里添加这几行代码:
在这里插入图片描述

然后1出去,把1的左右孩子节点进到队列中,但是我们现在希望只把1这个节点出出去,之前写的代码,没有这个概念,代码在出1这个节点后立马就把后面的2节点删除出去了,所以现在我们把出队列的代码在放到一个循环中:
在这里插入图片描述

这时候1这个节点出去并打印之后,就跳出循环,并且换个行,此时我们更新一下size的值,因为当前节点只是第二层的,size自然而然就设置成了第二层的节点个数。

在回到循环也是一样因为size为2,里面嵌套的循环只会循环两次,只是把第二层节点弹出并打印…这样就可以做到把树的节点一层一层的打印

//层序遍历
void LevelOrder(BTNode* root)
{Queue pq;QueueInit(&pq);int size = 0;//入队列QueuePush(&pq, root);size = 1;while(!QueueEmpty(&pq)){while(size--){//出队列,然后将这个节点的两个孩子传进去QDataType tmp = QueueFront(&pq);QueuePop(&pq);printf("%d ", tmp->data);if (tmp->left){QueuePush(&pq, tmp->left);}if (tmp->right){QueuePush(&pq, tmp->right);}}printf("\n");size = QueueSize(&pq);}QueueDestroy(&pq);
}

2.5二叉树的销毁

因为一般情况二叉树创建的节点都是用malloc创建的,在用完应该记得用free销毁,销毁的过程也要用到递归。同样将销毁分成简单的子问题,这里一定要注意一个顺序,要先销毁当前节点的左右子树,最后在销毁当前节点,如果反过来,先把节点销毁完了,你就找不到它的左右子树的位置了:

//二叉树销毁
void TreeDestory(BTNode* root)
{TreeDestory(root->left);TreeDestory(root->right);free(root);
}

最后在考虑终止条件:

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

如果是空就代表是空树,不用销毁,直接返回就行。其实这里可以传一个二级指针过来的,因为你虽然把root这个根节点销毁了,但是你没有把这个root置空,但不写也不要紧,这个函数调用完自己想起来把它置空也行。

三.二叉树节点个数

现在有一棵树,希望通过遍历能求出这棵树的节点个数:
在这里插入图片描述
这里我们同样用递归来写,将一个复杂的问题,分解成一个一个简单的子问题。这棵树的所有节点我们可以看成:根节点的个数+左子树节点个数+右子树节点个数。

//二叉树节点个数
int TreeSize(BTNode* root)
{return TreeSize(root->left) + TreeSize(root->right) + 1;
}

因为根节点不可能有很多,只有1个,所以结果就是左子树的个数和右子树个数之和在加1.

现在子问题的思路已经写出来了,现在还需要一个停止条件,不能让递归这样无限递归下去,也就是大思路已经写出来了,假设我们一直递归下去现在走到了3这个节点,然后我们再来计算3的左子树和右子树:
在这里插入图片描述

我们发现3的左右子树都是NULL,所以现在我们需要多加一个树是空的条件,这样就能保证我们的程序正常运行:

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

因为空树不算节点,所以直接返回0.

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

这个比刚才求总节点的稍微难一点,但技巧找到了也不是什么难事:
在这里插入图片描述

同样用递归,用分治的思想,整棵树的叶子节点个数就相当于左子树叶子节点个数加右子树叶子节点个数。所以我们把两个子树的叶子节点个数加起来直接返回即可:

//二叉树叶子节点个数
int TreeLeafSize(BTNode* root)
{return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

但是我们得再次之前先判断一下是不是叶子节点,是的话就返回1,否则就不返回。如果不加这些东西的话,直接返回就返回了一个寂寞,肯定是行不通的:

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

这里判断,如果当前节点的两个孩子都是空,就说明它是叶子节点。

现在每个子问题就基本写完了,我们同样考虑一下如果函数一直递归下去会怎么样:
但是我们发现每次函数走到叶子节点的时候就直接返回1了,根本走不到return TreeLeafSize(root->left) + TreeLeafSize(root->right);这一步,但是这样就能说成功了吗?当然还需要考虑一些其它情况像下面的2这个节点:
在这里插入图片描述

它的右子树是空的,但是没达到叶子节点的要求,函数下一次递归时root就会变成空指针,此时在函数里对空指针解引用就会发生错误,所以我们还要加一个限制条件:

//二叉树叶子节点个数
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:
在这里插入图片描述

所以我们可以这样写:

//二叉树高度
int TreeHight(BTNode* root)
{int left = TreeHight(root->left);int right = TreeHight(root->right);return left > right ? left + 1 : right + 1;
}

先将左右两棵树的结果保存下来,然后在判断把最高的那棵树的值留下来+1在返回。

现在在考虑结束条件,如果我们一直递归,一直到最后的叶子节点时:
在这里插入图片描述

发现如果此时的root是空的话,直接返回0就行。这样3这棵树左子树高度是0,右子树高度是0,所以返回0+1也就是1,这样就把3这棵树的高度返回了。

//二叉树高度
int TreeHight(BTNode* root)
{if (root == NULL)return 0;int left = TreeHight(root->left);int right = TreeHight(root->right);return left > right ? left + 1 : right + 1;
}

六.二叉树第K层的节点个数

到这里难度又提高了不少,同样将这个问题分解:
在这里插入图片描述

现在我们求这棵树第四层的节点个数,是不是可以看成左子树第3层节点个数+右子树第3层节点个数,然后继续划分…

直到这些我们就可以这样写:

//二叉树第K层节点
int TreeLevelKSize(BTNode* root, int k)
{return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

然后像这样一直递归,一直递归直到K为1的时候是不是就找到了我们希望找到的那一层?所以我们在此基础上加一个限制条件:

//二叉树第K层节点
int TreeLevelKSize(BTNode* root, int k)
{if (k == 1)return 1;return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

但是这就完了吗?当然不是,如果此时root是空,并且K还没到1的时候,下面对NULL解引用就会出错,而且此时K==1时刚好这个树是空,就说明此时不应该返回而是0,所以我们最后还要加一个限制条件:

//二叉树第K层节点
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);
}

七.找二叉树的节点

这个也比较复杂,意思就是找下面这个二叉树的一个指定的节点,并且把这个节点的地址返回出来,这个我们假如要找7这个节点:
在这里插入图片描述

经过前面几道题的磨练,思路应该能想出来一个大概:递归遍历嘛,如果一直递归最后是空的时候就返回空,然后用if判断,如果找到了就返回此时节点的地址,如果没找到就递归找左树,右树:

//查找x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;TreeFind(root->left, x);TreeFind(root->right, x);
}

但是这样写只写对了一半,现在我来画一下递归展开图来看看哪些地方需要改进:
在这里插入图片描述

首先递归一直到3这个节点的位置,因为是叶子节点,左右两个孩子都为空,然后返回空,一直到这里都很正常,但是这两个函数都走完了然后返回什么呢?(就是上面黑色线的那个地方)。这里第一个问题就找到了,我们要在这个地方加一个返回值,说明目前走的这条路径没有找到需要的值:

//查找x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);BTNode* ret2 = TreeFind(root->right, x);return NULL;
}

然后我们继续画图:
在这里插入图片描述

这里发现虽然找到了需要找的地址,也确实成功返回了,但是返回后的地址没有用任何东西接收,也就是说你确实找到了,但是找完之和立马又丢掉了。因为这种原因,现在还要在改一下代码:

//查找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;
}

这里我们拿ret1,ret2分别接收左右两个子树里找到的地址,但这里不是两个地址都接收完在返回,而是先找左边,如果左边找到了就不用找右边了。如果左右两棵子树都没找到就返回NULL。

八.题目

8.1判断单值二叉树

原题传送门:力扣
题目:
在这里插入图片描述

题目的大概意思是给你一个二叉树,如果这个二叉树的节点的值都相同则返回true,只要有一个不相同就返回false.

这个题目可以将问题拆分成一个一个的小问题:
先判断根节点的值和它的左右两个子节点的值是否相等,如果都相等就说明目前是没有问题的,然后继续递归用同样的办法找左子树和右子树。

bool isUnivalTree(struct TreeNode* root){if(root->val != root->left->val)return false;if(root->val != root->right->val)return false;
}

这里我们如果发现有一个判断不相等就返回false,记住这里判断的是不相等,而不是相等,因为只要直到有一个是不相等,它的最终结果肯定是false,但是现在三个值相等不代表下面的值也相等。判断相等不能拿到结果,所以这里判断不相等。

如果两个if判断完之后发现都相等,此时就应该开始写递归循环了,判断当前节点的左子树和右子树:

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

一直递归下去,因为返回的是bool值,所以这里不需要定义变量来接收返回值,因为当前节点的左右两个子树返回的值都为真,最终结果才是真,所以这里用的是&&符号。

大致思路已经写好了,现在在考虑一下一直递归到最后会怎样,也就是此时的节点是NULL的情况:

bool isUnivalTree(struct TreeNode* root){if(root == NULL)return true;if(root->val != root->left->val)return false;if(root->val != root->right->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

如果是空的话直接返回true就行,总不能因为你是空树,我就当你这个值和root不相等吧,这样的话就不管什么树都不是单值二叉树了,因为不管什么树都会有空树。

但是写到这里还没有结束,因为这个代码还有一个致命的问题,就是两个if那里,如果当前的节点是个叶子节点,它的左右两个孩子节点都是空树,而对空树解引用取它的值就会出错,所以还需要在做改进:

bool isUnivalTree(struct TreeNode* root){if(root == NULL)return true;if(root->left && root->val != root->left->val)return false;if(root->right && root->val != root->right->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

8.2相同的树

原题传送门:力扣
题目:
在这里插入图片描述

这一题可以先判断两棵树的根节点是否相同,如果不同就返回false,如果相同就继续向下判断,这里就要用到递归,把这个问题化做成一个一个子问题,现在就是判断两棵树的左子树是否相等和右子树是否相等。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

这里判断的是不相等,道理和第一题一样,只有不相等你才能真正的拿到最终结果,如果相等就不管,直接向下走就行。

这里把递归的大思路写出来了,现在来找递归的终止条件也可以认为,递归到不能递归的时候的样子:
在程序运行到最后时,应该要判断两棵树是空树的情况。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){//当p,q都为空的时候if(p == NULL && q == NULL)return true;//当p和q只有一个为空if(p == NULL || q == NULL)return false;//当p和q都不为空if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

空树也要分两种情况,就是两棵树同时为空的时候,这里可以把它当成是相同的,但是只有一个是空树,就肯定是错的,像下面这个:
在这里插入图片描述

这里左边的树虽然不是空树,但是右边的树是空树,根据这种情况,要返回false.

8.3另一棵子树

原题传送门:力扣

题目:在这里插入图片描述

这题和上一题有一些些关系,因为这里要用到上一题写的代码。可以直接比较两棵树是否相同,如果相同就直接返回true,但是不相同的话,就分割成子问题,判断左/右子树与subroot是否相同:

//判断两棵树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q){//当p,q都为空的时候if(p == NULL && q == NULL)return true;//当p和q只有一个为空if(p == NULL || q == NULL)return false;//当p和q都不为空if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(isSameTree(root, subRoot))return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

注意了,这里判断的是相同则返回,虽然和前几题返回的情况不一样,但是思路一样,因为只要判断成功就说明结果一定是正确的,如果当前的树和subroot不相等,不代表后面的子树也不想等。

还有最后的返回值是而不是且,因为左右两棵子树只要找到一棵与subroot相等即可,只有两棵子树都找不到才返回false.

最后递归到不能递归的时候也就是树为空的时候,但是题目里说过了subroot不可能是空树:
在这里插入图片描述

也就是说root一直递归到空树的时候肯定找不到与subroot相同的树了,此时直接返回false.

bool isSameTree(struct TreeNode* p, struct TreeNode* q){//当p,q都为空的时候if(p == NULL && q == NULL)return true;//当p和q只有一个为空if(p == NULL || q == NULL)return false;//当p和q都不为空if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root == NULL)return false;if(isSameTree(root, subRoot))return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

8.4二叉树的创建与遍历

原题传送门:牛客

题目:
在这里插入图片描述

这题是输入一个字符串,字符串中把#当成空树,题目要求是需要你把这个字符串自己构建成一个树然后中序打印出来。中序打印应该不难,我在前面已经将过了。这题的核心是如何将一个字符串变成一棵树。

现在先反着分析一波,一个树是怎么通过前序遍历变成一个字符串的:
在这里插入图片描述

前序遍历第一个找到的应该是根节点a,然后找它的左子树,把节点b当成左子树的根节点,现在第二个找到的是b,继续找b的左子树,现在把d当成子树的根节点,此时找到的就是d,目前找的顺序就是a->b->d然后找d的左子树,发现是NULL,按照题目的意思,如果是空的话应该打印#,找到第一个#的时候就可以返回了,继续找d的右子树,同样打印一个#。现在b的左子树全部找到了,开始找b的右子树,也是空同样打印#,现在的顺序是a->b->d->#->#->#.b的左右子树找完后返回,开始找a的右子树,现在把a的有孩子c当成右子树的根节点,所以先找的是c,c找完就找它的左右子树因为都是空所以返回#.
在这里插入图片描述

最后结果应该是:
在这里插入图片描述

现在开始反着推导,将一个字符串变成一棵树
这里设置一个下标i用来遍历这个字符串:
在这里插入图片描述

把a节点建好之后,i向后挪动一个位置,因为经过刚才通过树构建字符串来看,只有走到空树的时候才打印#然后返回,这就说明字符串指针只要没有直到#这个字符,就一直构建左节点:
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

走到这里的时候就不能继续向下走了,遍历到字符串的#时说明此时为空树节点的左子树已经全部找完该返回了。那现在要构建的就是d的右子树:
在这里插入图片描述

在这里插入图片描述

同样继续返回。

然后i继续向下走,当走到不是一个#的时候说明,这是一个新节点,因为之前遇到#就返回,现在这个新节点肯定是链接到a的右边:
在这里插入图片描述

最后两个#这里就不画了,肯定是链接在c的左右子树:
在这里插入图片描述

等到c的左右两个子树都返回,然后最终一直返回到a这个根节点,最后在返回这个根节点,我们就把树创建好并且把数的地址传出来。

理论这里大概讲完了,现在用代码来实践一下:

//定义树的节点
struct TreeNode
{char val;struct TreeNode* left;struct TreeNode* right;
};//创建树
struct TreeNode* TreeCreat (char* str, int* i)
{if(str[*i] == '#'){(*i)++;return NULL;}//新节点struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = str[(*i)++];root->left = TreeCreat(str, i);root->right = TreeCreat(str, i);return root;
}

刚开始判断是不是#,如果是,说明此时是空树。跟之前学到的递归一样,但如果不是#,说明此时应该创建一个新的节点,这里用malloc开辟。然后把字符串里的值传进去,然后继续向左和右递归。因为这里的函数的作用是创建一棵数嘛,这里把函数的返回值连接到当前节点的左,右两个指针上就行了。

像这样一直递归,一直递归,找到#就返回,最终返回根节点的地址。根据一个字符串构建一棵树就完成了。

这里还要注意一个点,就是i这个变量,注意看我这里传进来的是一个指针,有人可能会问,i这个变量不是代表着数组下标吗,这个下标的类型为什么是个指针?其实是因为如果你只是简简单单的传个整型变量的话,函数一直递归在返回的时候,可能i指向字符串的位置就不是我们希望的那个位置了,这里我画个图简单了解一下:
在这里插入图片描述

此时一直向下递归着走,没往后走一步i都会++,现在看还是一点问题都没有的,但是找到#应该要返回,但是返回的时候就要出问题了:
在这里插入图片描述

看上面这图,在返回到b这个节点然后找b的右子树时,现在字符串下标i应该向后走一步,也就是说b右边的这个#应该对应的下标是3的位置,但是我们因为没有真正改变i的值,此时i的值应该是当前函数i的值加1,而当前i的值上面已经标出来是1了。这样就出问题了。虽然这里i的值2,3都是#,但不代表后面不会出错。

所以这里传进来的是i这个值的指针,你每向后走一步,都能保证+的都是同一个i。

创建二叉树已经写完了,现在我在通过画图的方式加深一下理解:
在这里插入图片描述

现在通过向下递归,已经创建好了三个节点,但是现在还没把这些节点连起来,继续:
在这里插入图片描述

通过上图发现继续向下走已经到空节点了,这样就返回一个空并且把这两个空都叫给当前节点也就是d的左右两边,像这样:
在这里插入图片描述

然后我们继续向下走:
在这里插入图片描述

返回到d这个节点的时候,节点是d的这个函数该返回了,返回的值就是d这个节点的地址,而返回的位置恰好是b这个节点的左指针指向的位置,这样我们是不是把b的左数全部创建好并连接起来了?像这样:
在这里插入图片描述

后面的图就不好了,基本情况在这里我已经画好了,根据图可以看到,通过向下递归,把需要创建的节点创建好,然后返回的时候再一个一个连起来,这样一棵树就建完了。

再回到题目这里来,后面的就没什么难度了,直接看代码:

#include <stdio.h>
#include <stdlib.h>struct TreeNode
{char val;struct TreeNode* left;struct TreeNode* right;
};//创建树
struct TreeNode* TreeCreat (char* str, int* i)
{if(str[*i] == '#'){(*i)++;return NULL;}//如果不是空就创建一个新节点struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = str[(*i)++];root->left = TreeCreat(str, i);root->right = TreeCreat(str, i);return root;
}//中序遍历
void MidOrder(struct TreeNode* root)
{if(root == NULL)return;MidOrder(root->left);printf("%c ", root->val);MidOrder(root->right);
}int main() {char str[101];scanf("%s", str);int i = 0;//创建树struct TreeNode* root = TreeCreat(str, &i);//中序遍历MidOrder(root);return 0;
}

8.5判断是否为完全二叉树

这里需要用到之前讲过的层序遍历,现在我通过画图大致讲一下思路,先提供一棵树,判断这个树是不是完全二叉树:
在这里插入图片描述

首先上面这图可以当成一个完全二叉树,根据之前讲的层序遍历来走,只是稍微变化了一些,层序遍历是一个节点出队列,它的两个孩子不是空就入队列,这里不一样,不管你是不是空都入队列,先入a:
在这里插入图片描述

然后a出来把b,c在放进去:
在这里插入图片描述

b出来,d,e进去:
在这里插入图片描述

c出来,进去两个空:
在这里插入图片描述

后面也一样,d,e出来把NULL放进去:
在这里插入图片描述

现在就进入到这道题的核心了,首先NULL代表什么?就是空吧说明此时队列里存的内容什么都没有,看我调试的结果:
在这里插入图片描述

这里的size是6,头,尾两个指针都是空。
好,现在先看目前写出来的代码:

//判断是否为完全二叉树
bool TreeComplete(BTNode* root)
{Queue pq;QueueInit(&pq);//入队列QueuePush(&pq, root);while (!QueueEmpty(&pq)){//出队列,然后将这个节点的两个孩子传进去QDataType tmp = QueueFront(&pq);if (tmp){QueuePop(&pq);QueuePush(&pq, tmp->left);QueuePush(&pq, tmp->right);}elsebreak;}QueueDestroy(&pq);
}

等到取出的队列为空的时候,我们直接break跳出来。

等程序走到这一步的时候就可以判断:如果当前队列的头指针是空的话,我们来进行一个判断,具体怎么判断呢?我们来对比一下完全二叉树,非完全二叉树在遇到第一个空后队列里的内容:
在这里插入图片描述

我们发现完全二叉树后面什么都没有了,而非完全二叉树里面还有一个节点。这样我们在出队列出到一个空的时候跳出来,跳出来做一个判断:将队列此时里面的内容一直出,直到队列为空的时候停止。判断的代码可以这样写:

	while (!QueueEmpty(&pq)){QDataType tmp = QueueFront(&pq);QueuePop(&pq);if (tmp != NULL){QueueDestroy(&pq);return false;}}

像这样先看看队列是不是空,如果不是就进来判断,取出一个节点看它是不是NULL,如果是就继续往后找,如果突然遇到一个节点它不是NULL,就说明这个树不是完全二叉树,此时就不用往后找了,直接返回false.如果队列都为空了,还没找到一个不是NULL的节点,说明它是一个完全二叉树,循环结束就返回true就可以了:

//判断是否为完全二叉树
bool TreeComplete(BTNode* root)
{Queue pq;QueueInit(&pq);//入队列QueuePush(&pq, root);while (!QueueEmpty(&pq)){//出队列,然后将这个节点的两个孩子传进去QDataType tmp = QueueFront(&pq);if (tmp){QueuePop(&pq);QueuePush(&pq, tmp->left);QueuePush(&pq, tmp->right);}elsebreak;}while (!QueueEmpty(&pq)){QDataType tmp = QueueFront(&pq);QueuePop(&pq);if (tmp != NULL){QueueDestroy(&pq);return false;}}QueueDestroy(&pq);return true;
}

8.6前序遍历的题目

原题传送门:力扣

题目:
在这里插入图片描述

这题就是普通的前序遍历,但是我要通过这题给你们讲一些关于力扣的小细节,先看看题目给你的函数调用接口:

int* preorderTraversal(struct TreeNode* root, int* returnSize){
}

发现函数调用的参数除了树的根节点的地址,还多了一个returnSize的指针变量。这是因为题目本身不知道给你的这棵树的节点是多少,需要你自己求出来,但是不需要返回,就是说,你在函数内部假如已经求好了节点的大小,直接将returnSize解引用并将求出的大小赋值过去即可。这种写法跟8.4的写法差不多,你可以理解为,力扣在调用你写的函数之后,通过你在函数内对returnSize的值的改变,来得到当前调用的树的大小。所以在你的题目写完后要保证参数returnSize解引用的值是树的节点个数,否则会报错。

接下来看看代码:

//前序遍历
void PrevOrder(struct TreeNode* root, int* i, int* ret)
{if(root == NULL)return 0;ret[*i] = root->val;(*i)++;PrevOrder(root->left, i, ret);PrevOrder(root->right, i, ret);
}//求树的节点个数
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize){int size = TreeSize(root);//为返回的数组开辟一块空间int* ret = (int*)malloc(sizeof(int) * size);//这里将returnSize实际的值改成树的节点个数*returnSize = size;int i = 0;//遍历PrevOrder(root, &i, ret);return ret;
}

8.7对称二叉树

原题传送门:对称二叉树

题目:
在这里插入图片描述

这题和判断是不是相同的树这一题有着相似的点,就是把节点的左子树和左子树相比变成了左子树和右子树相比,另一个也是一样都反过来比就行了。但是这里注意的一个小问题是之前那道题有两棵树,这里只有一棵树。但是不要紧,我们把这棵树的左右两棵子树当成两棵不同的树去比就行:

bool ComTree(struct TreeNode* root, struct TreeNode* root1)
{//两个都为空if(!root && !root1)return true;//只有一个为空if(!root || !root1)return false;//两个都不为空if(root->val != root1->val)return false;return ComTree(root->left, root1->right) &&ComTree(root->right, root1->left);
}bool isSymmetric(struct TreeNode* root){return ComTree(root->left, root->right);
}

因为题目没说这棵树会不会为空树,如果想把代码写全一点,也可以加个判断:

bool isSymmetric(struct TreeNode* root){if(root == NULL){return true;}return ComTree(root->left, root->right);
}

8.8根据前/后序和中序重建树

先看一个树的前,中序遍历有什么特点,比如下面这棵树:
在这里插入图片描述

它的前序遍历:1,2,3,4,5,6
它的中序遍历:3,2,1,5,4,6

把写的遍历和树的图对照着看:
在这里插入图片描述

可以发现,根据前序遍历,我们能找到这个树的根,再根据中序遍历根的位置,可以把树化成三部分:左树,根,右树
在这里插入图片描述

然后继续看前序遍历的下一个位置:
在这里插入图片描述

前序遍历找第二个根的位置,因为是前序遍历,2这个节点必然是左树的根,再看中序遍历,中序遍历的顺序是左树,根,右树,而2这个节点是根也就意味着3是2这个节点的左树:
在这里插入图片描述

现在再回到中序遍历,发现1的左树已经建好了,现在应该建1的右树,此时根据前序遍历红色箭头指向的应该是4这个节点,也就意味着4是右树的的根节点:
在这里插入图片描述

然后根据中序遍历可以判断5是左树,6是右树:
在这里插入图片描述

前序遍历和后序遍历差不多,只不过前序遍历找根是从前向后找,后序遍历是从后向前找。

最后再想想能不能根据前,后序建树?答案是不行,因为没有中序你即使找到了根,也找不到左/右树的位置。

相关文章:

景联文科技高质量大模型训练数据汇总!

3月25日&#xff0c;2024年中国发展高层论坛年会上&#xff0c;国家数据局局长刘烈宏在“释放数据要素价值&#xff0c;助力可持续发展”的演讲中表示&#xff0c;中国10亿参数规模以上的大模型数量已超100个。 当前&#xff0c;国内AI大模型发展仍面临诸多困境。其中&#xff…...

Finereport11 类Excel筛选

微信公众号:次世代数据技术 关注可了解更多的教程。问题或建议,请公众号留言或联系本人; 微信号:weibw162 本教程视频讲解可以关注本人B站账号进行观看:weibw162一、需求描述 在使用FIneReport软件开发时,我们希望前台报表展示时可以类似Excel表格筛选那样,在表头进行多选…...

134.加油站

// 定义一个名为Solution的类 class Solution {// 定义一个公开方法canCompleteCircuit&#xff0c;输入参数为两个整数数组gas和cost&#xff0c;分别代表加油站的汽油量和消耗油量public int canCompleteCircuit(int[] gas, int[] cost) {// 初始化当前剩余油量sum为0&#x…...

Shell脚本查看端口是否被占用

#!/bin/sh# 检查端口是否被占用并输出占用程序 check_port_usage() {port=$1# 使用netstat命令检查端口result=$(netstat -tuln | grep :$port)if [ -z "$result" ]; thenecho "Port $port is not being used."else# 输出占用端口的进程IDecho "Port …...

SCI论文写作技巧-introduction和related works

https://www.cnblogs.com/chengyf1999/p/16753184.html SCI论文写作技巧-introduction和related worksintroduction怎么写 a)背景介绍,现状(介绍别人研究),存在问题,怎样解决,我的做法,有何亮点b)研究背景和重要性、引出该领域科研空白、点题—指出本文的研究课题、概述…...

【Java 面试题】instanceof 关键字的作用

instanceof 关键字的作用&#xff1f; instanceof关键字是Java中的一个运算符&#xff0c;用于检查一个对象是否是某个类的实例&#xff0c;或者是否实现了某个接口。其作用可以概括如下&#xff1a; 判断对象类型&#xff1a; 使用instanceof可以判断一个对象是否是某个类的实…...

数据结构:二叉树的链式结构

文章目录一.前言二.二叉树遍历2.1前序遍历/先根遍历2.2中序遍历/中根遍历2.3后序遍历/后根遍历2.4层序遍历2.5二叉树的销毁三.二叉树节点个数四.二叉树叶子节点的个数五.二叉树的高度六.二叉树第K层的节点个数七.找二叉树的节点八.题目8.1判断单值二叉树8.2相同的树8.3另一棵子…...

[附源码]计算机毕业设计小区疫情事件处理系统Springboot程序

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…...

03、自定义镜像上传阿里云

目录 1、alpine Linux简介 2、基于alpine制作JDK8镜像 1.1 下载镜像 1.2 创建并编辑dockerfile 1.3 执行dockerfile创建镜像 1.4 创建并启动容器 1.5 进入容器 1.6 测试jdk 3、Docker容器之最小JRE基础镜像 4、将Docker镜像上传至阿里云(或从阿云下载镜像) 5、Docke…...

机器学习之过拟合和欠拟合

文章目录前言什麽是过拟合和欠拟合?过拟合和欠拟合产生的原因&#xff1a;欠拟合(underfitting)&#xff1a;过拟合(overfitting)&#xff1a;解决欠拟合(高偏差)的方法1、模型复杂化2、增加更多的特征&#xff0c;使输入数据具有更强的表达能力3、调整参数和超参数4、增加训练…...

【Linux网络编程】服务端编程初体验

文章目录前言服务端是啥、有什么特点核心函数socket的简介服务器编程客户端代码The End前言 在上节课(Linux网络编程初体验)中我们实现了连接bilibili的功能&#xff0c;并获取其html源码 如图所示. 今天我们要自己编写个服务端来服务我们的客户端 提示&#xff1a;以下是本篇…...

《人类简史》笔记四—— 想象构建的秩序

目录 一、盖起金字塔 1、未来的来临 2、 由想象构建的秩序 3、如何维持构建的秩序 二、 记忆过载 三、亚当和夏娃的一天 一、盖起金字塔 1、未来的来临 原始社会&#xff1a; 人口少&#xff1b; 狩猎和采集&#xff1b; 整体活动范围大&#xff08;有几十甚至上百平方…...

TIDB在centos7.9上通过docker-compose进行安装、备份

1.环境介绍&#xff1a; 在centos7.9上安装tidb docker-compose版本 虚拟机配置2C/8G/40G 最小化安装 2.安装步骤 2.1 安装centos7.9 略 2.2 安装docker &#xff08;1&#xff09;安装依赖包 yum install -y yum-utils device-mapper-persistent-data lvm2&#xff08;2…...

Spring中Bean的生命周期

先直接说出过程&#xff0c;再来演示具体的操作 过程 简化来说就是 1、首先是实例化Bean&#xff0c;当客户向容器请求一个尚未初始化的bean时&#xff0c;或初始化bean的时候需要注入另一个尚末初始化的依赖时&#xff0c;容器就会调用doCreateBean()方法进行实例化&#xf…...

ACM第三周---周训---题目合集.

&#x1f680;write in front&#x1f680; &#x1f4dd;个人主页&#xff1a;认真写博客的夏目浅石.CSDN &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​ &#x1f4e3;系列专栏&#xff1a;ACM周训练题目合集.CSDN &#x1f4ac;总结&#xff1a…...

VUE+Spring Boot前后端分离开发实战(六):基于RABC权限通用后台管理系统-给角色动态分配权限和用户

文章目录 前言功能设计后端实现前端实现写在后面前言 本文记录了通用后台管理系统中RABC权限中两个功能:给角色分配权限、给角色设置用户。 给角色分配用户:前端使用到了elementUI中的tree,包括加载树以及给已选配权限给默认值等。给角色设置用户:前端用到了elementUI中的…...

Dockerfile自定义镜像实操【镜像结构、Dockerfile语法、构建Java项目】

要自定义镜像&#xff0c;就必须先了解镜像的结构才行。 1 镜像结构 镜像是将应用程序及其需要的系统函数库、环境、配置、依赖打包而成。 以MySQL为例&#xff0c;镜像的组成结构&#xff1a; 简单讲&#xff0c;镜像就是在系统函数库、运行环境基础上&#xff0c;添加应用…...

javaScript 进阶之路 --- 《加深理解回调函数》

前言&#xff1a; 回想当初第一次看到“回调函数”这个名词的时候&#xff0c;真的快把我难哭了。所有视频教程在讲到某个知识点的时候&#xff0c;大概都会说一句&#xff1a;“啊&#xff0c;这里怎么办呢&#xff1f;这里我们就需要用到一个回调函数...”。 等等&#xff0…...

Linux开发常用ps命令选项详解

【摘要】本文介绍了在Linux应用/内核开发调试中&#xff0c;经常需要用到的两个选项组合&#xff0c;当然&#xff0c;如果你需要查看更多更详尽的选项说明&#xff0c;可以参考man说明文档&#xff0c;即命令行下输入man ps进行查看。 aux选项组合 使用场景&#xff1a;更多…...

【ceph】分布式存储ceph

1 块存储&#xff0c;文件存储&#xff0c;对象存储 1.1 简介 文件存储&#xff1a;分层次存储&#xff0c;文件存储在文件夹中&#xff1b;访问文件时系统需要知道文件所在的路径。 举例&#xff1a;企业部门之间运用网络存储器&#xff08;NAS&#xff09;进行文件共享。 …...

Spring框架(九):Spring注解开发Annotation

Spring注解开发引子如何用注解替代xml基础配置Bean可以加一些注解来实现原有的xml文件的功能Component注解及其衍生注解依赖注入AutowireSpring非自定义的注解开发Spring其他注解注解的原理解析-xml方式注解的原理解析-注解方式引子 痛定思痛&#xff0c;主要问题出现在自己雀…...

python隶属关系图模型:基于模型的网络中密集重叠社区检测方法

隶属关系图模型 是一种生成模型&#xff0c;可通过社区联系产生网络。下图描述了一个社区隶属关系图和网络的示例&#xff08;图1&#xff09;。最近我们被客户要求撰写关于社区检测的研究报告&#xff0c;包括一些图形和统计输出。 图1.左&#xff1a;社区关系图&#xff08;圆…...

Java实现猜数游戏

1 问题 编写一个Java程序&#xff0c;实现以下功能&#xff1a; 2 方法 首先导入java.util包下的Random&#xff0c;让程序随便分配给用户一个数。 再导入java.util包下的Scanner类&#xff0c;构建Scanner对象&#xff0c;以便输入。 利用Random().nextInt()生成一个随机的i…...

阿里云安装mysql、nginx、redis

目录 安装mysql 安装nginx ​编辑安装redis 先看一下系统基本信息 安装mysql rpm -qa | grep mariadb 卸载mariadb rpm -e --nodeps mariadb-libs-5.5.68-1.el7.x86_64 下载mysql源 wget -i http://dev.mysql.com/get/mysql57-community-release-el7-10.noarch.rpm yum…...

毕业设计-基于机器视觉的行人车辆跟踪出入双向检测计数

目录 前言 课题背景和意义 实现技术思路 实现效果图样例 前言 &#x1f4c5;大四是整个大学期间最忙碌的时光,一边要忙着备考或实习为毕业后面临的就业升学做准备,一边要为毕业设计耗费大量精力。近几年各个学校要求的毕设项目越来越难,有不少课题是研究生级别难度的,对本科…...

linux 安装nginx

1.安装依赖包 //一键安装上面四个依赖 yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel 2.下载并解压安装包 /或上传解压包 //创建一个文件夹 cd /usr/local mkdir nginx cd nginx //下载tar包 wget http://nginx.org/download/nginx-1.13.7.tar.gz t…...

javaee之黑马旅游网1

这是一个用来锻炼javaweb基础知识的项目&#xff0c;先来导入一些我们准备好的文件 下面这些东西是我们项目必备的&#xff0c;我们提前准备好了 &#xff0c;这个我会上传到我的资源&#xff0c;你们可以自己去下载 利用maven来创建一个项目 选择无骨架创建项目&#xff0c;域…...

【高并发基础】理解 MVCC 及提炼实现思想

文章目录1. 前言2. MVCC 概念2.1 MVCC 版本链2.2 MVCC trx_id2.3 MVCC Read View3. 提出问题4. 解决问题4.1 不读未提交的数据4.1.1 一般的并发情况4.1.2 特殊的并发情况4.1.3 剩下的并发情况4.2 如果自己修改了数据&#xff0c;要第一时间读到5. MySQL RC 使用 MVCC5.1 MVCC D…...

Flow-vue源码中的应用

认识 Flow Flow 是 facebook 出品的 JavaScript 静态类型检查工具。Vue.js 的源码利用了 Flow 做了静态类型检查&#xff0c;所以了解 Flow 有助于我们阅读源码。 #为什么用 Flow JavaScript 是动态类型语言&#xff0c;它的灵活性有目共睹&#xff0c;但是过于灵活的副作用…...

学习python第一天(数据类型)

关于Python的数据类型 Python数据类型包括&#xff1a; 数字类型&#xff0c;字符类型&#xff0c;布尔类型&#xff0c;空类型&#xff0c;列表类型&#xff0c;元组类型&#xff0c;字典类型 1、数字类型 包括&#xff1a;整型int 浮点型float(有小数位的都是是浮点型) 注…...

echarts:nuxt项目使用echarts

一、项目环境 nuxt 2.X vue2.X vuex webpack 二、安装 yarn add echarts 三、使用 3.1、plugins目录下创建echarts.js import Vue from vue import * as echarts from echarts // 引入echarts Vue.prototype.$echarts echarts // 引入组件&#xff08;将echarts注册为全…...

认证服务-----技术点及亮点

大技术 Nacos做注册中心 把新建的微服务注册到Nacos上去 两个步骤 在配置文件中配置应用名称、nacos的发现注册ip地址&#xff0c;端口号在启动类上用EnableDiscoveryClient注解开启注册功能 使用Redis存验证码信息 加入依赖配置地址和端口号即可 直接注入StringRedisTempla…...

【计算机毕业设计】74.家教平台系统源码

一、系统截图&#xff08;需要演示视频可以私聊&#xff09; 摘 要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐…...

Hbase的SQL接口之Phoenix使用心得

PHOENIX 官方定义 A SQL layer over HBase delivered as a client-embedded JDBC drivertargeting low latency queries over HBase data 不同于Hive on HBase的方式&#xff0c;Phoenix将Query Plan直接使用HBaseAPI实现&#xff0c;目的是规避MapReduce框架&#xff0c;减少…...

Springboot萌宠社交分享系统的设计与实现hfdwz计算机毕业设计-课程设计-期末作业-毕设程序代做

Springboot萌宠社交分享系统的设计与实现hfdwz计算机毕业设计-课程设计-期末作业-毕设程序代做 【免费赠送源码】Springboot萌宠社交分享系统的设计与实现hfdwz计算机毕业设计-课程设计-期末作业-毕设程序代做本源码技术栈&#xff1a; 项目架构&#xff1a;B/S架构 开发语言…...

线性代数与解析几何——Part4 欧式空间 酉空间

线性代数与解析几何——Part4 欧式空间 & 酉空间 1. 欧氏空间 1. 定义 & 性质2. 内积表示与标准正交基3. 欧氏空间的同构4. 欧氏空间的线性变换5. 欧氏空间的子空间 2. 酉空间 1. 定义 & 性质2. 酉变换3. Hermite变换4. 规范变换 1. 欧氏空间 1. 定义 & 性质…...

带头双向循环链表的实现

目录前言节点声明链表的初始化尾插打印链表头插尾删头删查找节点指定位置插入指定位置删除链表销毁前言 之前讲过单链表的实现&#xff0c;在实现的过程中&#xff0c;我们会发现每次删除或者在前面插入节点的时候&#xff0c;都要提前保存上一个节点的地址。这样做十分麻烦&a…...

07【C语言 趣味算法】最佳存款方案(采用 从后往前 递推解决)

目录 一、前情回顾二、Problem:最佳存款方案2.1 Description of the problem2.2 Analysis of the problem2.3 Algorithm design2.4 The complete code and the results of the run(完整的代码 以及 运行结果)一、前情回顾 06【C语言 & 趣味算法】牛顿迭代法求方程根(可…...

游戏开发36课 cocoscreator scrollview优化

在cocoscreator内&#xff0c;ScrollView控件封装的挺完美的了&#xff0c;不过对于一些对性能要求比较高的场景&#xff0c;会存在问题&#xff0c;以top100排行榜排行榜举例子 1、应用卡顿甚至崩溃 按照官方用例使用ScrollView&#xff0c;插入100个玩家的item&#xff0c;理…...

屏幕开发学习 -- 迪文串口屏

一 前言 最近学习了一款基于图形化开发的屏幕&#xff0c;在摸索一周后&#xff0c;基本熟悉了这款产品的一个开发过程&#xff0c;今天给大家分享一下迪文串口屏的学习过程&#xff0c;有不足之处&#xff0c;还请见谅&#x1f601;&#xff0c;包含了环境搭建和功能DEMO 二 …...

微机-------CPU与外设之间的数据传送方式

目录 一、无条件方式二、查询方式三、中断方式四、DMA方式一、无条件方式 外设要求:简单、数据变化缓慢。 外设被认为始终处于就绪状态。始终准备好数据或者始终准备好接收数据。 IN AL,数据端口 数据端口的地址通过CPU的地址总线送到地址译码器进行译码,同时该指令进行的是…...

从源码上解决rosdep update失败问题

&#xff08;一&#xff09;卸载官方的rosdep、rosdistro 卸载rosdistro # python2 sudo apt-get purge python-rosdistro# python3 sudo apt-get purge python3-rosdistro卸载rosdep # python2 sudo apt-get purge python-rosdep# python3 sudo apt-get purge python3-rosd…...

常用的shell命令

常用的shell命令 1、ls命令 功能&#xff1a;显示文件和目录的信息 ls 以默认方式显示当前目录文件列表 ls -a 显示所有文件包括隐藏文件 ls -l 显示文件属性&#xff0c;包括大小&#xff0c;日期&#xff0c;符号连接&#xff0c;是否可读写及是否可执行 ls -lh 显示文件的…...

新手入门SLAM必备资料

新手入门SLAM必备资料 文章目录 新手入门SLAM必备资料一、SLAM学习书籍1.必读经典2.有很多期,跟着会议一起出的文集3.入门书籍,简单实现及代码4.SLAM入门教材吐血推荐,对深入理解SLAM实质非常有帮助5.作者Joan Sola关于Graph-SLAM的教程,包含位姿变换、传感器模型、图优化以…...

如何选择和使用腾讯云服务器的方法新手教程

本文将介绍如何选择和使用腾讯云服务器的方法新手教程。云服务器能帮助快速构建更稳定、安全的应用&#xff0c;降低开发运维的难度和整体IT成本。腾讯云CVM云服务器提供多种类型的实例、操作系统和软件包。各实例中的 CPU、内存、硬盘和带宽可以灵活调整&#xff0c;以满足应用…...

亚马逊云科技re:Invent:Serverless是所有构想的核心

12月2日&#xff0c;2022亚马逊云科技re:Invent全球大会上&#xff0c;Amazon.com副总裁兼首席技术官Werner Vogels博士向开发者们展示了另一种可能。在一系列Serverless工具的帮助下&#xff0c;一些代码可以少写&#xff0c;因为未来你可能再也不需要写它们了。这恐怕是自云原…...

数据链路层(必备知识)

文章目录1、数据链路层的作用2、认识以太网<1>以太网帧格式<2>认识MAC地址<3>认识MTU<4>查看硬件地址和MTU3、ARP协议<1>什么是ARP协议<2>ARP数据报格式<3>ARP协议的工作机制4、其他重要协议或技术<1> DNS<2>NAT技术1、…...

【Spring系列】- Spring循环依赖

Spring循环依赖 &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 一个有梦有戏的人 怒放吧德德 &#x1f31d;分享学习心得&#xff0c;欢迎指正&#xff0c;大…...

Python学习基础笔记二十一——迭代器

列表&#xff0c;我们使用for循环来取值&#xff0c;我们把每个值都取到&#xff0c;不需要关心每一个值的位置&#xff0c;因为只能顺序的取值&#xff0c;并不能跳过任何一个去取其他位置的值。那么我们为什么可以使用for循环来取值&#xff0c;for循环内部是怎么工作的呢&am…...

【云原生之Docker实战】使用docker部署IT资产管理系统GLPI

【云原生之Docker实战】使用docker部署IT资产管理系统GLPI 一、GLPI介绍1.GLPI简介2.GLPI功能二、检查本地docker环境1.检查docker版本2.检查docker状态三、下载GLPI镜像四、编辑docker-compose.yaml文件五、部署GLPI系统1.创建数据目录2.使用docker compose创建容器应用3.查看…...

【SSM框架 二】Spring

文章目录二、Spring1、简介2、IOC理论思想3、Hello Spring4、IOC创建对象的方式4.1 无参构造构造器注入4.2 有参构造器注入5、Spring的配置5.1 别名5.2 Bean的配置5.3 import6、DI依赖注入6.1 构造方法注入6.2 set方法注入6.3 扩展注入6.4、Bean的作用域7、Bean的自动装配7.1 正…...

基于java+ssm+vue+mysql的社区流浪猫狗救助网站

项目介绍 随着迅速的发展&#xff0c;宠物饲养也较以前发生很大的变化&#xff0c;社区流浪猫狗救助网站系统以其独有的优势脱颖而出。“社区流浪猫狗救助网站”是以JAVA程序设计语言课为基础的设计出适合社区流浪猫狗救助网站&#xff0c;其开发过程主要包括后台数据库的建立…...

推特营销引流入门指南

一、关注 当您关注另一个Twitter用户时&#xff0c;您进行订阅&#xff0c;即可立即阅读其内容分享。因此&#xff0c;请评估您关注的人&#xff0c;尤其是刚开始时。跟踪新用户的一种简单方法是找到他们的个人资料&#xff0c;然后单击“关注”按钮。 Twitter对于那些疯狂点…...

Seata概述基础

分布式事务原因&#xff1a; 单体架构的spring事务不能跨机器&#xff0c;不能跨数据源 分布式事务的概念&#xff1a; 一个业务流程&#xff0c;在分布式系统&#xff08;微服务&#xff09;中&#xff0c;每个业务模块都是一个分支&#xff0c;保证每个业务分支一起成功&am…...

Python学习基础笔记二十二——生成器

一个包含yield关键字的函数就是一个生成器函数。yield可以为我们从函数中返回值&#xff0c;但是yield又不同于return&#xff0c;return的执行意味着程序的结束&#xff0c;调用生成器函数不会得到返回的具体的值&#xff0c;而是得到一个可迭代的对象。每一次获取这个可迭代对…...

python -- PyQt5(designer)中文详细教程(四)事件和信号

事件 signals and slots也 被其他⼈翻译成信号和槽机制。 所有的应用都是事件驱动的。事件大部分都是由用户的行为产⽣的&#xff0c;当然也有其他的事件产生方式&#xff0c;比如网络的连接&#xff0c;窗口管理器或者定时器等。调⽤应⽤的exec_()⽅法时&#xff0c;应⽤会进⼊…...

linux安装Zookeeper的详细步骤

1.Java环境确认 确保已经安装了Java环境&#xff0c;没有的自行安装 2.官网下载包 Apache ZooKeeper 3.安装 3.1上传到linux&#xff0c;解压 我的目录为/root/apache-zookeeper-3.8.4-bin 进入到/root/apache-zookeeper-3.8.4-bin/conf目录下&#xff0c;执行命令复制zoo…...

简历–自我介绍–英文--通用

文章目录 第一&#xff1a;问候第二&#xff1a;姓名&#xff0c;英文名&#xff0c;毕业院校&#xff0c;毕业专业&#xff0c;毕业学院现在&#xff1a;性格&#xff0c;爱好&#xff0c;实践经验未来&#xff1a;为什么想读研&#x1f680; 将来愿意从事的方向&#xff0c;读…...

动态规划刷题(算法竞赛、蓝桥杯)--导弹拦截(线性DP)

1、题目链接&#xff1a;[NOIP1999 提高组] 导弹拦截 - 洛谷 #include <bits/stdc.h> using namespace std; const int N2e55; int a[N],x,n; int b[N],len;int main(){while(cin>>x)a[n]x;//求最长不上升子序列 b[0]2e9;//初始化为无穷大for(int i1;i<n;i){if(…...

Mysql数据库-DQL查询

Mysql数据库-DQL基本查询 1 DQL基本查询1.1 基础查询1.2 WHERE子句1&#xff09;算术运算符2&#xff09;逻辑运算符3&#xff09;比较运算符A&#xff09;BETWEEN... AND ...B&#xff09;IN(列表)C&#xff09;NULL值判断 4&#xff09;综合练习 2 DQL高级查询2.1 LIKE 模糊查…...

对话 Mines of Dalarnia: Web3 游戏创新,社区驱动与公链共建

作者&#xff1a;stellafootprint.network 嘉宾&#xff1a;Manfred Pack&#xff0c;Mines of Dalarnia 游戏开发总监 采访者&#xff1a;Alex Cooper&#xff0c;Footprint Analytics 北美社区与 BD 负责人 在区块链游戏领域&#xff0c;去中心化和玩家经济正在颠覆传统游戏…...

4、Jenkins持续集成-用户权限和凭证管理

文章目录 一、用户权限管理1、安装用户权限管理插件2、开启权限全局安全配置3、创建角色4、创建用户5、给用户分配角色6、创建项目测试权限二、凭证管理1、安装凭证管理插件2、安装Git插件和工具2.1 用户密码类型2.2 SSH密钥类型一、用户权限管理 利用Role-based Authorizatio…...