树和二叉树基础

引言:

树是一种非线性的结构,也是由一个一个的结点构成。

树的一些基本概念:

节点的度:一个节点含有的子树的个数称为该节点的度;如上图:A的度为6

叶节点或终端节点:度为0的节点称为叶节点。

非终端节点或分支节点:度不为0的节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点。

孩子节点或子节点:如B是A的子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点

树的度:一棵树中,最大的节点的度称为树的度

节点的层次:从根开始定义,根为第一层,根的子节点是第二层,以此类推。

树的高度或深度:树中节点的最大层次,如上图:树的高度是4.(注意从1开始计数,同时也意味着空树就是0

树的表示

左孩子右兄弟表示法:

二叉树概念及结构

概念:

  • 每个结点最多有两颗子树,即二叉树不存在度大于2 的节点。
  • 二叉树的子树有左右之分,其子树的次序不能颠倒。、

二叉树的定义

因为孩子最多有两个,所以直接定义左孩子,右孩子即可。

二叉树的前、中、后序

首先需要明确任何一个二叉树分为3个部分:

  1. 根节点
  2. 左子树
  3. 右子树

注意左子树和右子树都是一个整体,然后从这个整体中再细分根节点、左子树、右子树。

前序(先根):根 左子树 右子树

中序:左子树 根 右子树

后序:左子树 右子树 根

这个前中后的顺序是根据根的位置而决定的

下面是前、中、后序的原码(利用递归去求解)

void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->val);
}

特殊的二叉树

  1. 满二叉树:一个二叉树,如果每一个层的结点树都达到最大值,就称为满二叉树
  2. 完全二叉树:就是在满二叉树的基础上,前h-1层都是满的,但是最后一层不满,但是最后一层从左往右都是连续的。

二叉树的性质

  1. 如果规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点个数(也就是满二叉树的个数)是2^h-1
  3. 对任何一棵二叉树,如果度为0的叶节点的个数为n0,度为2的分支结点的个数为n2,则有n0 = n2+1.
  4. 若规定根节点的层数为1,具有n个结点的二叉树的深度h = LogN。

根据二叉树的性质进行解题

例题1:

由二叉树的性质3得到叶节点的个数是度为2的分支结点个数+1,所以直接199+1 = 200即可。

例题2:

选择题快速法:

直接假设n = 2,接着进行带入计算,与每个选项进行比较得到正确答案。

常规解法:

设未知数,度为0的结点个数有X0个,度为1的结点个数有X1个,度为2的结点个数有X2个.

就会得到X0+X1+X2 = 2n.

又因为X0和X2的关系X2+1 = X0.

又因为是一个完全二叉树所以度为1结点的个数要么是1要么是0,所以分两种情况,发现当X1 = 1时计算结果是小数,不符合题意,所以X1 = 0得出答案。

例题3:

解答:

假设这棵树的高度是h,假设最后一层缺了X个

本题也是将选择题的答案带到题目中进行比较,然后得出正确答案。

如何求一棵二叉树中结点的个数?

解法一:

采用循环遍历的思想

遍历这棵树的每一个结点,如果不是空,就size++,否则不进行++。

注意运用这种方法时,因为可能需要计算多颗树的结点,所以每次传参时,需要传一个新的size地址,在主函数中直接打印输出size的值

原码:
void TreeSize(BTNode* root,int* psize)//直接传地址
{if (root == NULL)return;else{(*psize)++;TreeSize(root->left, psize);TreeSize(root->right, psize);}
}

解法二:

采用分治的思想。

何为分治的思想,就是将一个比较复杂的问题进行一层一层的分解,直到分解到简单的层次。将大问题分解为小问题。

例如校长想要统计整个学校的人数,校长将这个任务分配给院长,院长再分配给每个班的班主任,每个班主任再分配给每个宿舍的宿舍长。

本题思路也是如此,统计整棵树的结点个数,将这颗树分为左子树和右子树,左子树再分为小的左子树和小的右子树,层层递归,直到最后一层加1。

原码:

int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;/*if (root == NULL)return 0;else{return TreeSize(root->left) + TreeSize(root->right) + 1;}*/
}

如何求二叉树叶子节点的个数?

按照上面分支的思想,咱们举一反三~

int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;elsereturn TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

TIP:

只需要给出中序+任何一个前序或者后序,就可以将一个完整的二叉树还原出来

原因:

前序和中序都是知道根节点是哪个,但是并不知道左子树和右子树。

如果有了中序后,并且已知根节点,那么在中序排列中,在根节点的左边就是左子树,在根节点的右边就是右子树,就可以轻松将树还原出来。

关于二叉树的一些经典例题

例题1:二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

题目描述:

注意事项:

利用递归的思想去进行前序遍历,注意在递归时,计数器一般需要传址,防止局部变量出生命周期就自动销毁。

假设计数器用全局变量,是不行的。

因为函数接口会被多次调用,全局变量会一直累加

原码:

//提前计算好树的结点的个数,方便创建动态数组的个数
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void _PrevOrder(struct TreeNode* root,int* arr,int* pcnt)
{//前序递归遍历,将遍历的结点存储到动态数组中if(root == NULL)return;arr[*pcnt] = root->val;(*pcnt)++;_PrevOrder(root->left,arr,pcnt);_PrevOrder(root->right,arr,pcnt);
}int* preorderTraversal(struct TreeNode* root, int* returnSize){int size = TreeSize(root);int* arr = (int*)malloc(sizeof(int) * size);int cnt = 0;//注意传地址,递归调用一般需要传址操作_PrevOrder(root,arr,&cnt);*returnSize = cnt;return arr;
}

例题二:二叉树的最大深度

104. 二叉树的最大深度 - 力扣(LeetCode)

题目描述:

解题思路:

同样采用分治的思想,求二叉树的最大深度,就是求左子树和右子树的最大深度,接着继续分治,求左子树中的小左子树和小右子树的最大深度,直到不可分解进行+1即可

原码:

int maxDepth(struct TreeNode* root){if(root == NULL)return 0;int leftmax = maxDepth(root->left) + 1;int rightmax = maxDepth(root->right) + 1;return leftmax > rightmax ? leftmax : rightmax;
}

例题3:判断平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode)

题目描述:

解题思路:

本题要求二叉树的每一个结点都要满足左右两个子树的高度差的绝对值不超过1,所以先判断头结点的左右子树是否满足,如果头结点都不满足,那么直接就返回false

如果头结点满足,则继续向下递归左右子树的结点是否满足。

原码:

int MaxDepth(struct TreeNode* root)
{if(root == NULL)return 0;int leftDepth = MaxDepth(root->left);int rightDepth = MaxDepth(root->right);return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}bool isBalanced(struct TreeNode* root){if(root == NULL)return true;//先判断头结点,接着再判断子节点int leftDepth = MaxDepth(root->left);int rightDepth = MaxDepth(root->right);return  abs(leftDepth-rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/115980.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【LeetCode75】第四十四题 省份数量

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 给我们一个二维数组&#xff0c;表示城市之间的连通情况&#xff0c;连在一起的城市为一个省份&#xff0c;问我们一共有多少个省份。 这…

cocos creator配置终端调试

在launch.json里添加"preLaunchTask":“CocosCreator compile” 在cocos creator里选择开发者&#xff0c;visual studio code工作流&#xff0c;选择添加编译任务。 添加 settings.json {"files.exclude":{"**/.git": true,"**/.DS_Sto…

【大数据】Flink 详解(六):源码篇 Ⅰ

Flink 详解&#xff08;六&#xff09;&#xff1a;源码篇 Ⅰ 55、Flink 作业的提交流程&#xff1f;56、Flink 作业提交分为几种方式&#xff1f;57、Flink JobGraph 是在什么时候生成的&#xff1f;58、那在 JobGraph 提交集群之前都经历哪些过程&#xff1f;59、看你提到 Pi…

2023年7月京东打印机行业品牌销售排行榜(京东运营数据分析)

鲸参谋监测的京东平台7月份打印机行业销售数据已出炉&#xff01; 7月份&#xff0c;打印机市场呈现下滑趋势。根据鲸参谋平台的数据可知&#xff0c;当月京东平台打印机的销量为48万&#xff0c;环比下降约28%&#xff0c;同比下降约18%&#xff1b;销售额为4亿&#xff0c;环…

【云原生】Kubernetes容器编排工具

目录 1. K8S介绍 1.1 k8s的由来 下载地址 1.2 docker编排与k8s编排相比 1.3 传统后端部署与k8s 的对比 传统部署 k8s部署 ​2. k8s的集群架构与组件 &#xff08;1&#xff09; Kube-apiserver &#xff08;2&#xff09;Kube-controller-manager &#xff08;3&a…

(数字图像处理MATLAB+Python)第十一章图像描述与分析-第三、四节:几何表述和形状描述

文章目录 一&#xff1a;几何描述&#xff08;1&#xff09;像素间几何关系A&#xff1a;邻接与连通B&#xff1a;距离 &#xff08;2&#xff09;像素间几何特征A&#xff1a;位置B&#xff1a;方向C&#xff1a;尺寸 &#xff08;3&#xff09;程序 二&#xff1a;形状描述&a…

SPI3+DMA外设驱动-TFTLCD初始化

前言 &#xff08;1&#xff09;本系列是基于STM32的项目笔记&#xff0c;内容涵盖了STM32各种外设的使用&#xff0c;由浅入深。 &#xff08;2&#xff09;小编使用的单片机是STM32F105RCT6&#xff0c;项目笔记基于小编的实际项目&#xff0c;但是博客中的内容适用于各种单片…

13.动态渲染侧边栏

为什么要动态渲染&#xff1f; 比如我们现在需要以下侧边栏的数据&#xff1a; 如果一个个的去写标签会很麻烦&#xff0c;发现导航栏中的数据分为两类&#xff0c;一类是一级导航&#xff0c;另一位是二级导航&#xff08;有子页&#xff09;&#xff0c;因此直接写两个函数判…

ClickHouse进阶(六):副本与分片-2-Distributed引擎

进入正文前&#xff0c;感谢宝子们订阅专题、点赞、评论、收藏&#xff01;关注IT贫道&#xff0c;获取高质量博客内容&#xff01; &#x1f3e1;个人主页&#xff1a;含各种IT体系技术,IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 &#x1f4cc;订阅…

如何使用SQL系列 之 了解SQL中的约束规则

简介 在设计数据库时&#xff0c;有时可能需要对某些列中允许的数据设置限制。例如&#xff0c;如果你要创建一张表来保存摩天大楼的信息&#xff0c;你可能希望在保存每座大楼高度的列中禁止使用负值。 关系型数据库管理系统(RDBMS)允许你使用约束来控制哪些数据被添加到表中…

Spring Boot源码解读与原理剖析:深入探索Java开发的奥秘!

评论区留言赠书15本 关注点赞评论&#xff0c;评论区回复“Spring Boot源码解读与原理剖析&#xff1a;深入探索Java开发的奥秘&#xff01;” 每篇最多评论3条&#xff01;&#xff01;采用抽奖助手自动拉取评论区有效评论送书两本&#xff0c; 开奖时间&#xff1a;9月11号 承…

MySQL数据库——多表查询(3)-自连接、联合查询、子查询

目录 自连接 查询语法 自连接演示 联合查询 查询语法 子查询 介绍 标量子查询 列子查询 行子查询 表子查询 自连接 通过前面的学习&#xff0c;我们对于连接已经有了一定的理解。而自连接&#xff0c;通俗地去理解就是自己连接自己&#xff0c;即一张表查询多次。…

二进制数的位运算(非和异或)invert()和bitwise_xor()

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 二进制数的位运算(非和异或) invert()和bitwise_xor() [太阳]选择题 下列代码最后一次输出的结果是&#xff1f; import numpy as np a, b 3, 10 print("【执行】np.binary_repr(a, 4)…

vue3+ts组件通信

1、父组件向组件传参 父组件代码 子组件代码 2、子组件向父组件传参 组件间代码 父组件代码 3、如果eslint报错&#xff0c;需在.eslintrc.js中添加一行代码 4、通过父组件通过 ref 获取子组件的属性或者方法 父组件代码 子组件代码 5、孙子组件provide和inject 父组件…

再也不信能用99年的IDEA激活方式了

今天给大家安利一款IDEA伴侣神器 Toolbox&#xff0c;开发必备的IDEA大家都在用&#xff0c;但很多小伙伴没用过Toolbox。 介绍 为什么使用 JetBrains Toolbox&#xff1f; 包含超过 15 款可用于专业开发的工具。 每个工具专门针对其技术开发。 所有工具都会定期更新&#…

python 笔记(3)——request、爬虫、socket、多线程

目录 1、使用requests发送http请求 1-1&#xff09;发送get请求 1-2&#xff09;发送 post 请求 1-3&#xff09;发送 get 请求下载网络图片 1-4&#xff09;使用 post 上传文件 1-5&#xff09;自动维护 session 的方式 2、使用 os.popen 执行cmd命令 3、基于 beautif…

卷积神经网络实现运动鞋识别 - P5

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f366; 参考文章&#xff1a;Pytorch实战 | 第P5周&#xff1a;运动鞋识别&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制&#x1f680; 文章来源&#xff1a;K同学的学习圈子 目录…

沐风老师3DMAX厨房橱柜生成器KitchenCabinetGenerator教程

3DMAX厨房橱柜生成器插件使用方法 3DMAX橱柜生成器KitchenCabinetGenerator是一个在3dMax中自动创建三维橱柜模型的高效脚本。它有多种风格的台面、门和橱柜&#xff0c;可以灵活地应用于Archviz项目&#xff0c;同时为3D艺术家节省大量时间。 【适用版本】 1.3dMax2018 – 20…

YOLO数据集划分(训练集、验证集、测试集)

1.将训练集、验证集、测试集按照7:2:1随机划分 1.项目准备 1.在项目下新建一个py文件&#xff0c;名字就叫做splitDataset1.py 2.将自己需要划分的原数据集就放在项目文件夹下面 以我的为例&#xff0c;我的原数据集名字叫做hatDataXml 里面的JPEGImages装的是图片 Annota…

设计模式-适配器

文章目录 一、简介二、适配器模式基础1. 适配器模式定义与分类2. 适配器模式的作用与优势3.UML图 三、适配器模式实现方式1. 类适配器模式2. 对象适配器模式3.类适配器模式和对象适配器模式对比 四、适配器模式应用场景1. 继承与接口的适配2. 跨平台适配 五、适配器模式与其他设…