🔥引言
本篇将从树与二叉树相关概念进行入手,帮助我们接下二叉树更进一步的学习。
🌈个人主页: 是店小二呀
🌈C语言笔记专栏: C语言笔记
🌈C++笔记专栏: C++笔记
🌈初阶数据结构笔记专栏: 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
树是一种非线性的数据结构,它是由n(n>=0)
个有限节点组成一个具有层次关系的集合,然而树在实践中价值不大,但是二叉树实践价值比较大(这种集合称为树的理由,是它是根朝上,而叶朝下,看起来很像树)
M(M>0)
个互不相交的集合T1、T2、....、Tm
,其中每一个集合Ti(1<=i<=m)
又是一颗结构与树类似的子树。每颗子树的根节点有且只有一个前驱,可有0个或多个后继。由于树状结构相对线性表复杂,存储方式也更加麻烦,既要保存值域,也要保存好结点和结点之间的关系。
以下根据之前知识得到的几种方法
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
当然不局限以上几种方式,还有双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法
一颗二叉树是节点的一个有限集合,该集合可能有两种情况
正在上传图片...
从图中可以得出两个结论:
注意:对于任意的二叉树都是通过下列几种情况组成的(空树的情况最容易忘记)
简单概括下:
这种就是普通的二叉树,从左到右不是连续的。
二叉树一般可以使用两种结构存储,一种是顺序结构,一种链式结构
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是满二叉树会有空间的浪费,对此现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树,在接下来做题我们需要根据物理上是数组,逻辑上是二叉树配合去解出一道题目。
leftchild = parent * 2 + 1;
rightchild = paretn * 2 +2;
parent = (child - 1) / 2;
(不区分左右孩子)leftchild
下标拆为leftchild- 1
和1
,对于leftchild-1
为parent
下标两倍,对于(child - 1) / 2
运算将leftchild
拆出来为1
部分单独除于2取整数为0,leftchild -1
部分可以看成leftchild
,而且rightchild与leftchild相差1
,由于rightchild = leftchild - 1
和通过上面leftchild - 1 ~= leftchild
,可以推理出rightchild = leftchild(在进行/2运算,取整数情况下)
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面学到高阶数据结构如红黑树等会用到三叉链
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};
顺序结构存储就是通过数组进行存储,一般使用数组只适合完全二叉树,非完全二叉树就不适合数组结构存储,普通二叉树只适合链式结构存储。但是在现实中使用堆才会使用数组来存储,大部分还是通过链式结构存储。
原因在于:
以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二初阶数据结构笔记,希望对你在学习初阶数据结构中有所帮助!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。