数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

这篇具有很好参考价值的文章主要介绍了数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院

一、二叉树

1、二叉树的概念

1.1 二叉树中组分构成名词概念

1.2 二叉树的结构概念

1.3 特殊的二叉树

2、二叉树的存储结构

2.1 顺序存储

2.2 链式存储

二、二叉树的性质

三、完结撒❀

前言:
在你的想象中如果有一个“二叉树”会是什么样子呢?
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode
顾名思义,现实中的二叉树我们就可以抽象的看成数据结构中的二叉树:
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode
可以看出来把它叫做树是因为它具有树一样的树形结构看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
我们思考下面问题:
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode
上面哪些为树,而哪些又不是树呢?
——————————————————————————————————————————————————
答案:
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀正文开始❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

一、二叉树

1、二叉树的概念

1.1 二叉树中组分构成名词概念

二叉树中各个组分构成名词如下:
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode
节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6。

叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点。

非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点。

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点。

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点。

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6。

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为4。

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点。

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先。

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙。

森林:由m(m>0)棵互不相交的树的集合称为森林;

1.2 二叉树的结构概念

一棵二叉树是结点的一个有限集合,该集合:

1. 或者为空。
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode从上图中可以看出来:

1. 二叉树不存在度大于2的结点。
3. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。

注意:对于任意的二叉树都是由以下几种情况复合而成的:
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode

1.3 特殊的二叉树

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。

2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode

2、二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构

2.1 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。

**二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

而在实际使用中只有堆**才会使用数组来存储。(下一篇我会对堆进行讲解实现)
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode

2.2 链式存储

二叉树的链式存储结构是指用链表来表示一棵二叉树,即用链表来指示元素的逻辑关系

通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面课程学到高阶数据结构如红黑树等会用到三叉链。
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode链式结构代码:

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; // 当前节点值域
};

这里对于三叉树我们只做了解即可。

下一篇博客我会对二叉树顺序(堆),链序的整体实现及应用进行讲解,大家尽情期待。

二、二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h-1个
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为N0 , 度为2的分支结点个数为N2,则有N0=N2+1。
  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1) . (ps: 是log以2为底,n+1为对数)。
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
    1)若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点。
    2)若2i+1<n,左孩子序号:2i+1,2i+1>=n则无左孩子。
    3)若2i+2<n,右孩子序号:2i+2,2i+2>=n则无右孩子。

三、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友❤
数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质),数据结构,算法,链表,c语言,笔记,经验分享,leetcode文章来源地址https://www.toymoban.com/news/detail-849782.html

到了这里,关于数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】树和二叉树概念

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月09日
    浏览(40)
  • 【数据结构】二叉树的基本概念

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 子树不能有交集,就是不能有闭环.N个节点两个一条边,所以是N-1个边,父节点的概念在下面讲. 节点的度

    2024年02月08日
    浏览(45)
  • 数据结构入门 — 二叉树的概念、性质及结构

    本文属于数据结构专栏文章,适合数据结构入门者学习,涵盖数据结构基础的知识和内容体系,文章在介绍数据结构时会配合上 动图演示 ,方便初学者在学习数据结构时理解和学习,了解数据结构系列专栏点击下方链接。 博客主页:Duck Bro 博客主页 系列专栏:数据结构专栏

    2024年02月07日
    浏览(36)
  • 【数据结构入门】-二叉树的基本概念

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 今天的内容可是一个大头,比以往学的内容上了一个档次。大家对于这块内容一定要好好学,不是很理解的地方一定要及时解决,要不然到

    2023年04月10日
    浏览(82)
  • 【数据结构】树及二叉树的概念

    😛 作者:日出等日落 📘 专栏:数据结构 一次失败,只是证明我们成功的决心还够坚强。                                        ——博 维 目录  🎄树概念及结构: ✔树的概念: ✔树的相关概念 :​编辑  ✔树的表示: ✔树在实际中的运用: 🎄二叉树概念及结构 ✔概念

    2023年04月23日
    浏览(56)
  • 爱上数据结构:二叉树的基本概念

    ​ ​ 🔥个人主页 : guoguoqiang. 🔥 专栏 : 数据结构 ​ 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 没有前驱节点的结点叫做根结点 在树中,子树不

    2024年04月14日
    浏览(48)
  • 数据结构--线索二叉树的概念

    中序遍历序列:D G B E A F C ①如何找到指定结点p在中序遍历序列中的前驱? ②如何找到p的中序后继? 思路: 从根节点出发,重新进行一次中序遍历,指针q记录当前访问的结点,指针pre记录上一个被访问的结点 ①当q p时,pre为前驱 ②当pre p时,q为后继 缺点 : 找前驱、后继很不方便

    2024年02月13日
    浏览(49)
  • 数据结构_进阶(1):搜索二叉树

    建议再看这节之前能对C++有一定了解 二叉树在前面C的数据结构阶段时有出过,现在我们对二叉树来学习一些更复杂的类型,也为之后C++学习的 map 和 set 做铺垫 1. map和set特性需要先铺垫二叉搜索树 ,而二叉搜索树也是一种树形结构 2. 二叉搜索树的特性了解,有助于更好的理

    2024年02月16日
    浏览(46)
  • 【数据结构】树和二叉树堆(基本概念介绍)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录  前言  树的概念  树的常见名词 树与非树  二叉树 概念 满二叉树和完全二叉树 二叉树的存储结构 顺序存储 链式

    2024年02月01日
    浏览(35)
  • 初级数据结构(五)——树和二叉树的概念

        文中代码源文件已上传:数据结构源码  -上一篇 初级数据结构(四)——队列        |        初级数据结构(六)——堆 下一篇-         自然界中的树由根部开始向上生长,随机长出分支,分支之上又可长出分支,层层递进,直至长出叶子则此分支结束。   

    2024年02月04日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包