大家好，本期是二叉树的最后一期，这一期我们来看看二叉树的编程题
单值二叉树
. - 力扣（LeetCode）
首先我们的思路是：遍历二叉树，把每个节点去比较一次，按照要求返回
我们来看代码
bool isUnivalTree(struct TreeNode* root) {
if(root==NULL){
return true;
}
if(root->left&&root->left->val!=root->val){
return false;
}
if(root->right&&root->right->val!=root->val){
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
检查两颗树是否相同
. - 力扣（LeetCode）
这里我们的思路是：同时遍历两给树，遇到空树或者不相等时返回。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p==NULL&&q==NULL){
return true;
}
if(p==NULL||q==NULL){
return false;
}
if(p->val!=q->val){
return false;
}
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
对称二叉树
. - 力扣（LeetCode）
我们仔细观察该对称二叉树，我们发现互相对称的节点它们的左子树与右子树分别相等，这就是突破口，我们可以重新创建一个函数，将参数分成两个一左一右两个节点，然后向下比较，这个过程与上一题类似。
我们来看代码
bool _isSymmetric(struct TreeNode* pl,struct TreeNode* pr){
if(pl==NULL&&pr==NULL){
return true;
}
if(pl==NULL||pr==NULL){
return false;
}
if(pl->val!=pr->val){
return false;
}
return _isSymmetric(pl->left,pr->right)&&_isSymmetric(pl->right,pr->left);
}
bool isSymmetric(struct TreeNode* root) {
return _isSymmetric(root->left,root->right);
}
另一颗树的子树
. - 力扣（LeetCode）
这题我们的思路是找出root所有的子树跟subroot比较，这里的比较函数我们前面已经写过了，如果相同就返回true，如果没找到就返回false
代码如下
//比较函数
bool pdxt(struct TreeNode*p,struct TreeNode*q){
if(p==NULL&&q==NULL){
return true;
}
if(p==NULL||q==NULL){
return false;
}
if(p->val!=q->val){
return false;
}
return pdxt(p->left,q->left)&&pdxt(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL){
return false;
}
if(pdxt(root,subRoot)){
return true;
}
return isSubtree( root->left, subRoot)||isSubtree( root->right, subRoot);
}
二叉树的前序遍历
. - 力扣（LeetCode）
这一题可跟我们前一期的前序遍历有所不同，我们仔细观察一下他给我们的参数是一个二叉树的根和一个int*的指针，这个指针是输出型指针，也就是说这个指针是出题人用来获取二叉树节点个数的，而这个函数的返回类型是int*，它要我们返回一个存储二叉树数据的数组，所以我们这里最好动态开辟内存来存储，
所以我们的思路是用两个子函数来辅助完成，一个函数来计算二叉树的节点数一个函数用来遍历二叉树，最后由原函数返回。
int evertreenode(struct TreeNode* root){
return root==NULL?0: evertreenode(root->left)+evertreenode(root->right)+1;
}
void qianxu(struct TreeNode*root,int*a,int*i){
if(root==NULL){
return;
}
a[(*i)++]=root->val;
qianxu(root->left,a,i);
qianxu(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=evertreenode(root);
int*a=(int*)malloc(sizeof(int)*(*returnSize));
int i=0;
qianxu(root,a,&i);
return a;
}
二叉树的构建与销毁
二叉树的销毁
我们的思路是遍历二叉树，把节点一个一个销毁，那么这里我们选什么方式遍历？
答案是后序，因为前序是先销毁根，如果根销毁了就找不到，只能先把左右子树先存储起来再销毁。（这里三种遍历顺序都可以，只是后序更好）。
void treeDestory(BTnode* node1) {
if (node1 == NULL) {
return;
}
treeDestory(node1->lest);
treeDestory(node1->right);
free(node1);
}
判断二叉树是否是完全二叉树
这一题我们就要用到我们上一期学习的层序遍历来实现了，主要思路是，用层序遍历如果遇到NULL后还可以遇到不为空的节点就不是完全二叉树。
说到层序遍历我们就会想到队列，下面是队列的源码大家可以直接使用
Queue.h
# include<stdio.h>
# include<assert.h>
# include<stdlib.h>
# include<string.h>
# include<errno.h>
# include<stdbool.h>
typedef struct Qhead Qhead;
typedef struct Queue Queue;
typedef struct Binarytreenode BTnode;
//二叉树
struct Binarytreenode {
int size;//保存的数据
BTnode* lest;//左子树
BTnode* right;//右子树
};
//链表结构
struct Qhead {
BTnode* size;
struct Qhead* next;
};
//队列结构
struct Queue {
Qhead* top;//队头
Qhead* end;//队尾
int SZ;
};
//初始化
void Queueinit(Queue* head);
//队尾输入数据
void Queuepush(Queue* head, BTnode* n);
//判断队列是否为空
bool QueueEmpty(Queue* haed);
//队头删除数据
void Queuepop(Queue* head);
//获取对头数据
BTnode* Queuefrost(Queue* head);
//获取队列中的有效元素个数
int Queuesize(Queue* head);
//销毁队列
void QueueDestroy(Queue* head);
Queue.c
//初始化
void Queueinit(Queue* head) {
assert(head);
head->end = NULL;
head->top = NULL;
head->SZ = 0;
}
//队尾输入数据
void Queuepush(Queue* head, BTnode* n) {
assert(head);
Qhead* ps = (Qhead*)malloc(sizeof(Qhead));
if (ps == NULL) {
printf("%s", strerror(errno));
return;
}
ps->next = NULL;
ps->size = n;
if (head->top) {
head->end->next = ps;
head->end = head->end->next;
}
else {
head->top = ps;
head->end = ps;
}
head->SZ++;
}
//判断队列是否为空
bool QueueEmpty(Queue* head) {
assert(head);
return head->SZ == 0;
}
//队头删除数据
void Queuepop(Queue* head) {
assert(head);
assert(!QueueEmpty(head));
if (head->top->next == NULL) {
free(head->top);
head->top = NULL;
head->end = NULL;
}
else {
Qhead* cur = head->top->next;
head->top->next = NULL;
free(head->top);
head->top = cur;
}
head->SZ--;
}
//获取队头数据
BTnode* Queuefrost(Queue* head) {
assert(head);
assert(!QueueEmpty(head));
return head->top->size;
}
//获取队列中的有效元素个数
int Queuesize(Queue* head) {
assert(head);
return head->SZ;
}
//销毁队列
void QueueDestroy(Queue* head) {
assert(head);
while (head->top == NULL) {
Qhead* cur = head->top->next;
head->top->next = NULL;
free(head->top);
head->top = cur;
}
head->top = NULL;
head->end = NULL;
head->SZ = 0;
}
下面是判断完全二叉树的代码
//判断树是不是完全二叉树
bool BTcomplete(BTnode* root) {
Queue head;
Queueinit(&head);
if(root)
Queuepush(&head,root);
while (!QueueEmpty(&head)) {
BTnode* frost = Queuefrost(&head);
Queuepop(&head);
if (frost == NULL)
break;
Queuepush(&head, frost->lest);
Queuepush(&head, frost->right);
}
while (!QueueEmpty(&head)) {
BTnode* frost = Queuefrost(&head);
Queuepop(&head);
if (frost != NULL) {
QueueDestroy(&head);
return false;
}
}
QueueDestroy(&head);
return true;
}
我们可以测试一下。
二叉树的创建
二叉树遍历_牛客题霸_牛客网
这道题我们要从一个先序数组中读取数据构建二叉树。
我们的思路是先创建一个二叉树的结构体，然后将他初始化，再从数组中按照前序来读取数据并为它们开辟一个节点来存储，然后把这些节点按前序来插入。遇到‘#’就说明这是空树。
#include <stdio.h>
# include<stdlib.h>
//二叉树的结构
typedef struct treenode BTnode;
struct treenode{
char size;
BTnode*left;
BTnode*right;
};
//初始化
BTnode* treeinit(char add){
BTnode*root=(BTnode*)malloc(sizeof(BTnode));
if(root==NULL){
return NULL;
}
root->left=NULL;
root->right=NULL;
root->size=add;
return root;
}
//在二叉树中插入数据
BTnode* treepush(char*ps,int*i){
if(ps[*i]=='#'){
(*i)++;
return NULL;
}
BTnode*root=treeinit(ps[*i]);
(*i)++;
root->left=treepush(ps,i);
root->right=treepush(ps,i);
return root;
}
//中序输出
void intree(BTnode*root){
if(root==NULL){
return;
}
intree(root->left);
printf("%c ",root->size);
intree(root->right);
}
int main() {
int i=0;
char add[100];
scanf("%s",add);
BTnode* root =treepush(add,&i);
intree(root);
return 0;
}
我们可以从这道题找出二叉树创建的函数
BTnode* treepush(char*ps,int*i){
if(ps[*i]=='#'){
(*i)++;
return NULL;
}
BTnode*root=treeinit(ps[*i]);
(*i)++;
root->left=treepush(ps,i);
root->right=treepush(ps,i);
return root;
}经过了这几期的学习我们二叉树学习就告一段落了，这并不意味着我们二叉树已经学完了，随着我们的学习我们还会再学习二叉树的。
以上就是全部内容了，如果有错误或者不足的地方欢迎大家给予建议。 文章来源：https://www.toymoban.com/news/detail-848800.html
文章来源地址https://www.toymoban.com/news/detail-848800.html
到了这里，关于数据结构——二叉树(OJ练习)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
