由于二叉树是数据结构中偏难的一块,这里我们先熟悉二叉树的结构,再具体来实现一颗二叉树,采用手动构建二叉树的方式,帮助大家进一步理解
呈现的是一个树型结构
BTNode *BinaryTreeCreate(char ch)
{
BTNode *newNode = (BTNode *)malloc(sizeof(BTNode));
newNode->data = ch;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void func()
{
BTNode* A = BinaryTreeCreate('A');
BTNode* B = BinaryTreeCreate('B');
BTNode* C = BinaryTreeCreate('C');
BTNode* D = BinaryTreeCreate('D');
BTNode* E = BinaryTreeCreate('E');
BTNode* F = BinaryTreeCreate('F');
A->left = B;
A->right = C;
B->left = D;
C->left = E;
C->right = F;
}
构建了结点与结点之间的父子关系,从代码中可以看到A的左右子树是B和C,B的左子树是D,C的左右子树是E和F,剩余的默认给NULL值,在创建结点的时候就已经初始化好了,那如果想要呈现出遍历顺序呢。
#pragma once
#include<memory.h>
#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include"Queue.h"
typedef char BTDataType;
typedef struct BTNode
{
struct BTNode *left;
struct BTNode *right;
BTDataType data;
}BTNode;
//创建结点
BTNode *BinaryTreeCreate(char ch);
//后序遍历
void PrevOrder(BTNode *root);
//中序遍历
void Inorder(BTNode *root);
//后序遍历
void Postorder(BTNode *root);
//树结点的个数
int BinaryTreeSize(BTNode *root);
//求叶子结点的个数
int BinaryleafSize(BTNode* root);
//求二叉树的第k层结点个数
int BinaryKSize(BTNode* root,int k);
//查找值为val的结点
BTNode* BinaryFind(BTNode* root,char ch);
//广度优先遍历二叉树
void TreeLevelorder(BTNode* root);
//二叉树的销毁
void BinaryTreeDestroy(BTNode* root);
//判断一颗树是不是完全二叉树
bool BinaryTreecomp(BTNode* root);
#include"BinaryTree.h"
BTNode *BinaryTreeCreate(char ch)
{
BTNode *newNode = (BTNode *)malloc(sizeof(BTNode));
assert(newNode);
newNode->data = ch;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
//后序遍历
void PrevOrder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
PrevOrder(root->right);
printf("%c ",root->data);
}
}
//中序遍历
void Inorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
printf("%c ", root->data);
PrevOrder(root->right);
}
}
//后序遍历
void Postorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
}
//树结点的个数
int BinaryTreeSize(BTNode *root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
//求叶子结点的个数
int BinaryleafSize(BTNode *root)
{
if (root == NULL)
{
return 0;
}
else if(!root->left && !root->right)
{
return 1;
}
else
{
return BinaryleafSize(root->left) + BinaryleafSize(root->right);
}
}
//求二叉树的第k层结点个数
int BinaryKSize(BTNode* root,int k)
{
if (!root)
{
return 0;
}
else if (k == 1)
{
return 1;
}
else
{
return BinaryKSize(root->left, k - 1)
+ BinaryKSize(root->right, k - 1);
}
}
//查找值为val的结点
BTNode* BinaryFind(BTNode* root,char ch)
{
if (!root)
{
return NULL;
}
if (root->data == ch)
{
return root;
}
BTNode* leftNode = BinaryFind(root->left,ch);
BTNode* rightNode = BinaryFind(root->right, ch);
if (leftNode )
{
return leftNode;
}
if(rightNode)
{
return rightNode;
}
return NULL;
}
void TreeLevelorder(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while (!QueueEmpty(&q))
{
//取出队头的数据
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ",front->data);
//接着入,出一层父亲结点,带进去子节点
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q);
}
//二叉树的销毁
void BinaryTreeDestroy(BTNode* root)
{
if (!root)
{
return;
}
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);
}
//判断一颗树是不是完全二叉树
bool BinaryTreecomp(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (!front)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front)
{
return false;
}
}
return true;
}
我们知道二叉树有三种遍历方式,为了遍历前面构建出来的树型结构这三种遍历方式我们都采用
按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
总结:
//后序遍历
void PrevOrder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
PrevOrder(root->right);
printf("%d ",root->data);
}
}
//中序遍历
void Inorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
PrevOrder(root->left);
printf("%d ", root->data);
PrevOrder(root->right);
}
}
//前序遍历
void Postorder(BTNode *root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
else
{
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
}
int BinaryTreeSize(BTNode *root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left)
+ BinaryTreeSize(root->right) + 1;
}
后序思想,递归左右子树,如果该结点为空就返回0,不为空就返回左右子树的结点个数相加的和值 + 1,这里的+ 1 操作是用作计数根结点的(每一个真实结点),其实看作是一个二叉树的后序遍历也不为过
//求叶子结点的个数
int BinaryleafSize(BTNode *root)
{
if (root == NULL)
{
return 0;
}
else if(!root->left && !root->right)
{
return 1;
}
else
{
return BinaryleafSize(root->left)
+ BinaryleafSize(root->right);
}
}
叶子结点表示的是没有孩子的结点,当遍历一颗树不断的往下递归,总会遇到度为0的结点,而这个结点的就是作为这颗树的叶子结点,在这里可以将一颗大树看成是多颗小树,计算出多颗小树的叶子结点个数就是整个大树的叶子结点
//求二叉树的第k层结点个数
int BinaryKSize(BTNode* root,int k)
{
if (!root)
{
return 0;
}
else if (k == 1)
{
return 1;
}
else
{
return BinaryKSize(root->left, k - 1)
+ BinaryKSize(root->right, k - 1);
}
}
想求出第k层的结点的个数只需要将这一层的结点相加得到的结果就是这一层的结点个数
BTNode* BinaryFind(BTNode* root,char ch)
{
if (!root)
{
return NULL;
}
if (root->data == ch)
{
return root;
}
BTNode* leftNode = BinaryFind(root->left,ch);
BTNode* rightNode = BinaryFind(root->right, ch);
if (leftNode )
{
return leftNode;
}
if(rightNode)
{
return rightNode;
}
return NULL;
}
到树的左右子树中去查找该结点如果找到就返回该节点,否则继续查找,直到走到NULL的位置,那就返回NULL
英文缩写为BFS即Breadth FirstSearch。其过程检验来说是对每一层节点依次访问,访问完一层进入下一层,而且每个节点只能访问一次。这里用队列来实现这个遍历方式,还是由于队列先进先出的特性,
实现思路:
先将根入队列,将父亲pop出去后再入孩子,打印父亲的值,那么这一层就已经遍历完了,紧接着就可以继续入下一层,父亲每次pop出去的时让父亲的孩子入队,
void TreeLevelorder(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
QueuePush(&q,root);
while (!QueueEmpty(&q))
{
//取出队头的数据
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ",front->data);
//接着入,出一层父亲结点,带进去子节点
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
}
QueueDestroy(&q);
}
实现思路:后序遍历,从最后一个NULL位置开始边回退,返回它的上一层,释放这个结点
//二叉树的销毁
void BinaryTreeDestroy(BTNode* root)
{
if (!root)
{
return;
}
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);
}
首先我们得有完全二叉树的概念,完全二叉树的最后一层结点个数可以不满,但是必须是从左到右连续的,那么看上面的图,你觉得他会是完全二叉树吗,左边是,右边不是,原因不是连续的,如果接着采用层序遍历的思路搞定这个,还是比较简单的,
//判断一颗树是不是完全二叉树
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root) {
// write code here
if(!root) return false;
queue<TreeNode *> q;
q.push(root);
while(!q.empty()){
auto node = q.front();
q.pop();
if(!node) break;
if(node->left) q.push(node->left);
else q.push(nullptr);
if(node->right) q.push(node->right);
else q.push(nullptr);
}
while(!q.empty()){
auto node = q.front();
if(node != nullptr) return false;
q.pop();
}
return true;
}
};
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回 true;否则返回 false
实现思路:
如果左孩子跟右孩子的值都与父亲的值相等,那么他就是单值二叉树,再往下递归的过程中只需要将值不等就直接返回false,否则就继续递归下去直到整个树遍历完了,那么就是单值二叉树
bool isUnivalTree(struct TreeNode* root){
if(!root)
{
return true;
}
//判断左孩子跟父亲是否相等,不等返回false
if(root->left && root->left->val != root->val)
{
return false;
}
//判断右孩子是否和父亲相等,不等返回false
else if(root->right && root->right->val != root->val)
{
return false;
}
//相等继续往下递归,
else
{
return isUnivalTree(root->left)
&& isUnivalTree(root->right);
}
}
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
实现接口
int* preorderTraversal(struct TreeNode* root,
int* returnSize)
{
}
实现思路:
前序遍历这颗二叉树,将二叉树每个结点的值存放进数组中,最后返回该数组,值得注意的是这个接口的参数,*returnsize,到底需要开辟多大的空间来存放二叉树的值,可以通过遍历二叉树求出它的结点个数,malloc出等大的数组出来,存放结点的值
//计算结点的个数
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//以前序遍历的方式,将树的值存放到数组中
void _preoder(struct TreeNode* root,int *retArr, int *pi)
{
if(!root)
{
return;
}
else
{
retArr[(*pi)++] = root->val;
_preoder(root->left,retArr,pi);
_preoder(root->right,retArr,pi);
}
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = TreeSize(root);
int *retArr = (int *)malloc(sizeof(int) * (* returnSize));
int i = 0;
_preoder(root,retArr,&i);
return retArr;
}
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
实现思路:
能先想到的就是这两颗树都是空树,那么他们就是相同的,还有一种情况就是一个树的结点多,一个树的结点少,少的先被遍历完,所以他们肯定不相同,剩下的就是判断值了,比较两颗树的左右子树的值是否是相等的
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p == NULL && q == NULL)
{
return true;
}
if(p == NULL || q == NULL)
{
return false;
}
else if(p->val != q->val)
{
return false;
}
else
{
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
}
从树的第二层开始,将每一层的根划分出两颗左右子树,比较根再分别将两颗子树的左孩子和右孩子比较,右孩子和左孩子比较,如果相同就返回true
bool _issymmetry(struct TreeNode *Treeleft, struct TreeNode* Treeright)
{
if(!Treeleft && !Treeright)
{
return true;
}
if(!Treeleft || !Treeright)
{
return false;
}
else if(Treeleft->val != Treeright->val)
{
return false;
}
return _issymmetry(Treeleft->left,Treeright->right)
&& _issymmetry(Treeleft->right,Treeright->left) ;
}
bool isSymmetric(struct TreeNode* root){
if(!root)
{
return true;
}
return _issymmetry(root->left,root->right);
}
题目描述:
翻转一棵二叉树。
实现思路:
递归到最后一层开始再往回返的过程,备份根的左右孩子,回退到根的时候交换左右孩子的位置
struct TreeNode* invertTree(struct TreeNode* root){
if(!root)
return NULL;
struct TreeNode* left = invertTree(root->left);
struct TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
实现思路:
从root中选出每一个根看作一颗子树去和subroot这颗子树比较,如果他们,左右子树都相等了就返回true,如果不相等继续从root中找下一个根
bool _issymmetry(struct TreeNode *root,
struct TreeNode* subRoot)
{
if(!root && !subRoot)
return true;
if(!root || !subRoot)
return false;
else if(root->val != subRoot->val)
return false;
return _issymmetry(root->left,subRoot->left)
&& _issymmetry(root->right,subRoot->right);
}
bool isSubtree(struct TreeNode* root,
struct TreeNode* subRoot){
if(!root)
return false;
if(_issymmetry(root,subRoot))
return true;
//寻找下一个根比较是否与subRoot相等
return isSubtree(root->left,subRoot)
|| isSubtree(root->right,subRoot);
}
题目描述:
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
实现思路:
大问题化成小问题的思路,要想判断是不是平衡二叉树,就得把整个树拆分成多颗子树,去判断左右子树的高度差是否 < 2,分别求出n颗左右子树的深度,如果他们的差距 < 2 就满足,直到把整个树遍历完就返回true,这里采用的遍历方式是后序遍历
bool isbalance(struct TreeNode* root, int *pi)
{
if(!root)
{
*pi = 0;
return true;
}
int leftheight = 0;
if(isbalance(root->left,&leftheight) == false)
return false;
int rightheight = 0;
if(isbalance(root->right,&rightheight) == false)
return false;
*pi = fmax(leftheight,rightheight) + 1;
return abs(leftheight - rightheight) < 2;
}
bool isBalanced(struct TreeNode* root){
if(!root)
return true;
int i = 0;
return isbalance(root,&i);
}
KY11 二叉树遍历
链接: link.
原题描述:
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
根据题意手动还原出来的二叉树应该是这样的,满足先序遍历的结构
实现思路:
把字符串存放进一个数组中,每次遍历这个数组,取出一个字符创建结点,从上往下递归,不断创建左右孩子,当遇到#的时候就表示这个结点是叶子,那就返回它的上一层,它的上一层就是根,把叶子当作根的孩子,往上返回,不断创建父子关系,当左子树递归完了就去递归右子树,直到整个树创建出来。
#include<stdio.h>
typedef char BTNodeType;
typedef struct BTNode
{
struct BTNode *left;
struct BTNode *right;
BTNodeType data;
}BTNode;
BTNode *BTNodecreate(char *str,int *pi)
{
if(str[*pi] == '#')
{
(*pi)++;
return NULL;
}
//取字符创建结点
BTNode* root = (BTNode *)malloc(sizeof(BTNode));
root->data = str[(*pi)++];
//创建左右孩子
root->left = BTNodecreate(str, pi);
root->right = BTNodecreate(str, pi);
return root;
}
//中序遍历
void inorder(BTNode *root)
{
if(!root)
{
return ;
}
inorder(root->left);
printf("%c ",root->data);
inorder(root->right);
}
int main()
{
int i = 0;
char arr[100] = {
0};
scanf("%s",arr);
BTNode *root = BTNodecreate(arr,&i);
inorder(root);
return 0;
}
文章浏览阅读4.2k次。打开src目录下的AppDelegate.cpp文件,若无修改则在第45行处找到全局声明的Size变量,修改`designResolutionSize`中的大小即可。_cocos2dx设置窗口大小
文章浏览阅读1.6k次。测试代码:@PostMapping() public void test(@RequestBody Student student){ System.out.println(student.getLover().name()); }class Student{ private Lover lover; public Lover getLover() { return lover; } public void setLover_springboot get请求怎么接收前端传递的枚举数字
文章浏览阅读1.5w次,点赞24次,收藏120次。简单来说就是去量纲后的回归(因为你要比较不同变量之间的显著性的大小,那么带着量纲怎么比,所以先把量纲去掉,然后再比较)官话:为了更为精准的研究影响评价量的重要因素(去除量纲的影响),我们可考虑使用标准化回归系数。_stata两个虚拟变量的交互项
文章浏览阅读203次。有时候安装mysql后使用mysql命令时报错 Can't connect to MySQL server on localhost (10061),或者用net start mysql 时报服务名无效,一般是因为mysql服务没有启动。这时候可以用管理身份运行cmd.exe(注意必须是管理..._c:\program files\mysql\mysql server 5.6\bin>mysqld --install install/remove
文章浏览阅读6.2k次,点赞3次,收藏44次。亚信联创科技校园招聘B 卷考试时间60_分钟 _考试方式(闭)卷(本试卷满分 100 分,答案请写在答题卡上)请不要在问卷上答题或涂改,笔试结束后请务必交回试卷部分内容分值备注一、计算机基础40分C/C++语言基础40分技能部分二、二选一JAVA 语言基础40分三、数据库20分总分100 分第一部分——计算机基础一、选择题(每题 2 分,总分 40分)1.CPU 状态分为目态和管态两种..._亚信科技java实习笔试题
文章浏览阅读1.3k次。3年对一个程序员来说是非常重要的。像我自己本身就是做程序员的,目前的薪资待遇是13K左右,虽然在我所在的公司不是最高的,但在所在的这个城市的消费水平来说,除了日常的开支,包括房租、水电、伙食、人际交往等费用之外,还能留下一部分闲钱自己存起来。不同城市的薪资待遇是不一样的,这主要是由于当地的消费水平和经济发展水平不同,所以如果你想要更高的薪资待遇,就要考虑在一线城市或者经济发达的城市工作。一个有着丰富工作经验的程序员,他的技能水平、经验和能力都比没有经验的程序员更加出色,所以他们的薪资待遇也会更高一些。_三线城市学java
文章浏览阅读418次。标签PostgreSQL , 标签 , 推荐系统 , 实时圈人 , 数组 , gin , gist , 索引 , rum , tsvector , tsquery , 万亿 , user , tag , 淘宝背景我们仅用了PostgreSQL的两个小特性,却解决了业务困扰已久的大问题。推荐系统是广告营销平台的奶牛,其核心是精准、实时、..._实时圈人
文章浏览阅读430次。软件测试风险追踪表风险追踪表 项目名称: 填制人: 编号 风险描述 影响 风险等级 发生的可能性 应对策略 状态 责任人 备注 ..._软件测试风险管理表格
文章浏览阅读1.2k次。一、AAC音频格式种类有哪些AAC音频格式是一种由MPEG-4标准定义的有损音频压缩格式。AAC包含两种格式 ADIF(Audio Data Interchange Format音频数据交换格式)和ADTS(Audio Data transport Stream音频数据传输流)。ADIF特点:可以确定的找到音视频数据的开始,不需要进行在音视频数据流中间开始的解码,它的解码必须在明确的定义开始。应用场景:常用在磁盘文件中。ADTS特点:具有同步字的比特流,解码可以在这个流中任何位置开始。类似于mp_aac adts
文章浏览阅读213次。像要使用Resouce类,必须创建一个 Resouce 文件夹,然后把需要的资源放进去,才可以在代码中设置路径进行访问_unity基本概念
文章浏览阅读2.4k次。指定自定义 CI/CD 配置文件,顾名思义就是在项目中指定文件来代替默认的.gitlab-ci.yml文件的方式来运行流水线。以往我们在使用流水线的时候,都是默认将.gitlab-ci.yml文件存在在项目的跟路径下,但是我们也可以指定备用文件名路径,或者不想在每个项目中来维护这个yml文件,那么通过自定义 CI/CD 配置文件便可以实现。_gitlab配置cicd
文章浏览阅读1w次。出现这个表示如果设置了自动增长,字段类型应该设置为int整型。_sql 错误 [1063] [42000]: incorrect column specifier for column 'id' incorrec