数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

简介: 数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

二叉树的定义

二叉树T:一个有穷的节点集合。

这个集合可以为空;若不为空,则它是由根节点和称为其左子树 右子树 的两个不相交的二叉树组成。

二叉树具体的五种基本形态

1.空树

2.只有一个节点

3.有左子树,但右子树为空

4.有右子树,但左子树为空

5.左右两子树都不为空

要注意,二叉树与普通的度为二的树不同的一点是:二叉树的子树有左右顺序之分。

特殊二叉树

斜二叉树

斜二叉树都只有左儿子或者都只有右儿子,这样的二叉树,实际上相当于一个链表,形成了一个线性结构。

满二叉树

又叫完美二叉树

这样的二叉树是除了最底层的叶节点没有节点,其它每一个节点都有两个儿子;且叶节点都在同一层。

完全二叉树

有n个节点的二叉树,对树中节点按从上至下、从左到右顺序进行编号,编号为i(1<= i <= n)节点与满二叉树中编号为i节点在二叉树中位置相同。

简单地来说,完全二叉树的节点编号要与它满二叉树形态下的节点编号相一致,如下图:

二叉树的几个重要性质

  • 一个二叉树第i层的最大节点数为 ,i >=1。

这个性质很好理解,像满二叉树这种树每一层都达到了最大节点数,节点数满足首项为1,公比为2的等比数列。

  • 深度为K的二叉树有最大节点总数为: -1,k >=1。

能达到最大节点数的树是怎样的呢?

当然就是完美二叉树啦,其节点数:

第一层:1

第二层:2

第三层:4

......

第k层:

用等比数列求和公式

就可以求和最大节点数为: -1。

  • 对任何非空二叉树T,若n0表示叶节点的个数,n2是度为2的非叶节点个数,那么两者满足关系n0 = n2 +1。


我们从边的角度来推导出这个性质:



初识二叉树的几个操作函数

  • Boolean IsEmpty(BinTree BT):判别BT是否为空
  • void Traversal(BinTree BT):遍历,按某个顺序访问每个节点
  • BinTree CreatBinTree():创建一个二叉树

常用的遍历方法有:

  1. void PreOrderTrversal(BinTree BT):先序——根、左子树、右子树
  2. void InorderTraversal(BinTree BT):中序——左子树、根、右子树
  3. void PostOrderTraversal(BinTree BT):后序——左子树、右子树、根
  4. void LevelOrderTraversal(BinTree BT):层次遍历,从上到下、从左到右

end



目录
相关文章
|
18天前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
32 1
|
18天前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
30 0
|
5天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
5天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
5天前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
6 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
11天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
10天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
10天前
|
算法 JavaScript
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
18 0
|
2天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
16 7
|
22小时前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。