由于二叉树是数据结构中偏难的一块,这里我们先熟悉二叉树的结构,再具体来实现一颗二叉树,采用手动构建二叉树的方式,帮助大家进一步理解
呈现的是一个树型结构
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;
}
文章浏览阅读1k次。通过使用ajax方法跨域请求是浏览器所不允许的,浏览器出于安全考虑是禁止的。警告信息如下:不过jQuery对跨域问题也有解决方案,使用jsonp的方式解决,方法如下:$.ajax({ async:false, url: 'http://www.mysite.com/demo.do', // 跨域URL ty..._nginx不停的xhr
文章浏览阅读2k次。关于在 Oracle 中配置 extproc 以访问 ST_Geometry,也就是我们所说的 使用空间SQL 的方法,官方文档链接如下。http://desktop.arcgis.com/zh-cn/arcmap/latest/manage-data/gdbs-in-oracle/configure-oracle-extproc.htm其实简单总结一下,主要就分为以下几个步骤。..._extproc
文章浏览阅读1.5w次。linux下没有上面的两个函数,需要使用函数 mbstowcs和wcstombsmbstowcs将多字节编码转换为宽字节编码wcstombs将宽字节编码转换为多字节编码这两个函数,转换过程中受到系统编码类型的影响,需要通过设置来设定转换前和转换后的编码类型。通过函数setlocale进行系统编码的设置。linux下输入命名locale -a查看系统支持的编码_linux c++ gbk->utf8
文章浏览阅读750次。今天准备从生产库向测试库进行数据导入,结果在imp导入的时候遇到“ IMP-00009:导出文件异常结束” 错误,google一下,发现可能有如下原因导致imp的数据太大,没有写buffer和commit两个数据库字符集不同从低版本exp的dmp文件,向高版本imp导出的dmp文件出错传输dmp文件时,文件损坏解决办法:imp时指定..._imp-00009导出文件异常结束
文章浏览阅读143次。当下是一个大数据的时代,各个行业都离不开数据的支持。因此,网络爬虫就应运而生。网络爬虫当下最为火热的是Python,Python开发爬虫相对简单,而且功能库相当完善,力压众多开发语言。本次教程我们爬取前程无忧的招聘信息来分析Python程序员需要掌握那些编程技术。首先在谷歌浏览器打开前程无忧的首页,按F12打开浏览器的开发者工具。浏览器开发者工具是用于捕捉网站的请求信息,通过分析请求信息可以了解请..._初级python程序员能力要求
文章浏览阅读7.6k次,点赞2次,收藏6次。@Service标注的bean,类名:ABDemoService查看源码后发现,原来是经过一个特殊处理:当类的名字是以两个或以上的大写字母开头的话,bean的名字会与类名保持一致public class AnnotationBeanNameGenerator implements BeanNameGenerator { private static final String C..._@service beanname
文章浏览阅读6.9w次,点赞73次,收藏463次。1.前序创建#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#include<iostream>#include<stack>#include<queue>using namespace std;typed_二叉树的建立
文章浏览阅读7.1k次。在Asp.net上使用Excel导出功能,如果文件名出现中文,便会以乱码视之。 解决方法: fileName = HttpUtility.UrlEncode(fileName, System.Text.Encoding.UTF8);_asp.net utf8 导出中文字符乱码
文章浏览阅读2.1k次,点赞4次,收藏23次。第一次实验 词法分析实验报告设计思想词法分析的主要任务是根据文法的词汇表以及对应约定的编码进行一定的识别,找出文件中所有的合法的单词,并给出一定的信息作为最后的结果,用于后续语法分析程序的使用;本实验针对 PL/0 语言 的文法、词汇表编写一个词法分析程序,对于每个单词根据词汇表输出: (单词种类, 单词的值) 二元对。词汇表:种别编码单词符号助记符0beginb..._对pl/0作以下修改扩充。增加单词
文章浏览阅读773次。我在使用adb.exe时遇到了麻烦.我想使用与bash相同的adb.exe shell提示符,所以我决定更改默认的bash二进制文件(当然二进制文件是交叉编译的,一切都很完美)更改bash二进制文件遵循以下顺序> adb remount> adb push bash / system / bin /> adb shell> cd / system / bin> chm..._adb shell mv 权限
文章浏览阅读6.8k次,点赞12次,收藏125次。1. 单目相机标定引言相机标定已经研究多年,标定的算法可以分为基于摄影测量的标定和自标定。其中,应用最为广泛的还是张正友标定法。这是一种简单灵活、高鲁棒性、低成本的相机标定算法。仅需要一台相机和一块平面标定板构建相机标定系统,在标定过程中,相机拍摄多个角度下(至少两个角度,推荐10~20个角度)的标定板图像(相机和标定板都可以移动),即可对相机的内外参数进行标定。下面介绍张氏标定法(以下也这么称呼)的原理。原理相机模型和单应矩阵相机标定,就是对相机的内外参数进行计算的过程,从而得到物体到图像的投影_相机-投影仪标定
文章浏览阅读2.2k次。文章目录Wayland 架构Wayland 渲染Wayland的 硬件支持简 述: 翻译一篇关于和 wayland 有关的技术文章, 其英文标题为Wayland Architecture .Wayland 架构若是想要更好的理解 Wayland 架构及其与 X (X11 or X Window System) 结构;一种很好的方法是将事件从输入设备就开始跟踪, 查看期间所有的屏幕上出现的变化。这就是我们现在对 X 的理解。 内核是从一个输入设备中获取一个事件,并通过 evdev 输入_wayland