认识了树,再来看看二叉树吧

这篇具有很好参考价值的文章主要介绍了认识了树,再来看看二叉树吧。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

欢迎来到 Claffic 的博客 💞💞💞 

前言:

上一期给大家讲了树的基本概念和特点,现在可以试着回忆一下树的样子,还有一些关系称谓。那么今天要讲的,是二叉树,是一种特殊且实用的树,是不是有些小期待呢! 


目录

🐷1.什么是二叉树

1.1二叉树的结构

1.2满二叉树

1.3完全二叉树

1.4二叉树的性质

🐽2.二叉树的存储结构

2.1顺序存储

2.2链式存储 


1.什么是二叉树

1.1二叉树的结构

先来回顾下树:倒置的,根在顶端,向下分岔... ...

所谓二叉树,二叉嘛,就是有两个叉子呗:

认识了树,再来看看二叉树吧

       一颗简单的二叉树

还真是,简单说,它就是每个结点最多能分两个叉的树。

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

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

认识了树,再来看看二叉树吧

二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

那么二叉树是不是只有二叉的情况呢?

其实并不是,下面总结二叉树的几种单元形态:

认识了树,再来看看二叉树吧

任意一种二叉树都可以由上面的形态复合而成。

1.2满二叉树

这是一种特殊的二叉树

满,意味着除根节点以外的结点都拥有左右结点(子树),即每一层的结点数达到最大值。

认识了树,再来看看二叉树吧

例:满二叉树

非常完美的二叉树~

如果设它的高度为K,那么它共有2^K-1个结点,同样可以用这条性质来判断是否为满二叉树。

1.3完全二叉树

这种树相比满二叉树就有些空缺了,

但是空的结点也有讲究:

从二叉树末端(右下角)开始,空到这一层的任意位置,保证空结点不间断

换句话说,最后一层的结点都仅靠左部。

认识了树,再来看看二叉树吧

 例:完全二叉树

它的准确的定义是:

对于深度为 K的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 n 的结点

要注意:满二叉树是一种特殊的完全二叉树,完全二叉树的范围更广一些。

1.4二叉树的性质

• 若规定根节点的层数为 1 ,则一棵非空二叉树的 i 层上最多有 2^(i-1) 个结点。

认识了树,再来看看二叉树吧

最多就是满的情况,层的编号与每层最多结点的个数关系:Ni = 2^(i-1);

可以联想一下有丝分裂... ...

• 若规定根节点的层数为1 ,则 深度为 h 的二叉树的最大结点数是2^h-1

这里就是一个等比数列求和,

在完全二叉树的情况下,第一层到第h层的结点个数:

2^0,2^1,2^2,2^3,... ... 2^(h-1)

求和:

Nh = 2^0+2^1+2^2+2^3+...+2^(h-1)

通过错位相减求和得到结点总数:

Nh = 2^h-1

•  对任何一棵二叉树, 如果度为 0 其叶结点个数为n0  , 度为 2 的分支结点个数为n2  , 则有
n0 = n2+ 1

这个可以简单找找规律:

认识了树,再来看看二叉树吧

可以发现叶子结点的个数总比度为2的结点个数多1

• 若规定根节点的层数为 1 ,具有 n 个结点的满二叉树的深度 h = log2(n+1)  
【log2(n+1)是以2为底,n+1的对数】

其实就是按之前求最大个数的式子 Nh = 2^h-1 把h表示出来,一个意思

• 对于具有n 个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号,则对于序号为i 的结点有:
若  i>0 位置节点的双亲序号: (i-1)/2 i=0 i 为根节点编号,无双亲节点
若  2i+1<n ,左孩子序号: 2i+1 2i+1>=n 否则无左孩子
若  2i+2<n ,右孩子序号: 2i+2 2i+2>=n 否则无右孩子

可以看看这个标记:

认识了树,再来看看二叉树吧

2.二叉树的存储结构

2.1顺序存储

所谓顺序存储,就是以数组来实现二叉树。

欸?用数组来实现二叉树,

其实这个跨度还蛮大的,心里想的是链型的,实际实现却是用数组这种顺序结构。

这里用 逻辑结构 物理结构 来分别表示:

认识了树,再来看看二叉树吧

逻辑结构就是心里想的,物理结构就是实际实现需要的

这种存储结构适用于满二叉树,因为满二叉树不会有数组空间的浪费。 

顺序存储中有一个典型的数据结构叫做堆(一种二叉树,此堆非彼堆,彼堆是操作系统中管理内存的一块区域分段),这里放到下期讲解。

2.2链式存储 

这个链式存储就是正常的思路了: 

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

这里定义一棵二叉树树的基本结构:

要存储的数据,指向左子树的指针,指向右子树的指针。

所以根据左右孩子的关系就可以创建一颗二叉树:

认识了树,再来看看二叉树吧

 根据左右孩子关系创建的一颗简单二叉树

链式结构方便在遍历,后期会讲解二叉树的遍历。


总结:
这篇博客给大家介绍了二叉树,更加偏向理论层面,那么下期就会带大家敲代码实现一些特殊的二叉树:堆,二叉树的遍历等等。

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗文章来源地址https://www.toymoban.com/news/detail-417935.html

到了这里,关于认识了树,再来看看二叉树吧的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 二叉树的概念|满二叉树与完全二叉树|二叉树的性质|二叉树的存储结构

    在数据结构中树的用途其实并不大,用得更多的其实是二叉树。所以在本章我们将详细讲解二叉树。 一颗二叉树是结点的一个 有限集合 ,该集合: 或者为空 或者由一个根节点加上两颗(互不相交)别称为左子树和右子树的二叉树组成 如图我们可知, 二叉树的特点: 二叉

    2024年01月21日
    浏览(41)
  • 完全二叉树、完美二叉树、完满二叉树、计算完全二叉树的结点

    对于完美二叉树,我们常用的是另一个名称:满二叉树 完美二叉树的定义: 完美二叉树是一种特殊的完全二叉树,每层都是满的,像一个稳定的三角形 完全二叉树的定义: 全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

    2023年04月08日
    浏览(79)
  • 数据结构——常见二叉树的分类(完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树)

    专业术语 中文 描述 Root 根节点 一棵树的顶点 Child 孩子结点 一个结点含有的子树的根节点称为该结点的子节点 Leaf 叶子结点 没有孩子的节点 Degree 度 一个节点包含子树的数量 Edge 边 一个节点与另外一个节点的连接 Depth 深度 根节点到这个节点经过边的数量 Height 节点高度 从

    2024年02月03日
    浏览(42)
  • 二叉树OJ题进阶(二叉树层序遍历、根据二叉树创建字符串、判断完全二叉树、二叉树的构建及遍历、二叉树的最近公共祖先(2种))

    1.思路 用队列写: 1.从上到下,从左到右的顺序 2.非递归的方法:使用队列来完成 3.cur充当根结点,当cur不为空的时候,cur进入队列,队列不为空,cur弹出队列打印 4.如果cur的左边不为空,左边进队,右边不为空,右边进队 5.此时队列不为空,弹出队头(也就是cur的左边)打

    2024年02月05日
    浏览(37)
  • 【二叉树part01】| 二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代遍历

    目录 ✿二叉树的递归遍历❀ ☞LeetCode144.前序遍历 ☞LeetCode145.二叉树的后序遍历  ☞LeetCode94.二叉树的中序遍历  ✿二叉树的迭代遍历❀  ☞LeetCode144.前序遍历  ☞LeetCode145.二叉树的后序遍历   ☞LeetCode94.二叉树的中序遍历  ✿二叉树的统一迭代遍历❀   ☞LeetCode144.前序遍

    2024年02月09日
    浏览(37)
  • 【数据结构】树,二叉树,满二叉树,完全二叉树的定义和二叉树的基本操作

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 ⭐树 🏳️‍🌈定义  🏳️‍🌈注意 🍔树的基本术语 ⭐二叉树 🏳️‍🌈定义 🎆二叉树和树的区别 🏳️‍🌈二叉树

    2024年02月05日
    浏览(66)
  • 【考研复习】二叉树的特殊存储|三叉链表存储二叉树、一维数组存储二叉树、线索二叉树

    三叉链表结构体表示如下图所示: 构造三叉链表方式: 另外设计一个填充函数,函数功能是将所有结点的parent结点填充正确。 线索二叉的的基本结构: 使用中序遍历的顺序进行线索化。代码中有一个难以理解的点,为什么不用p直接找后继,而是使用了前驱结点找后继。实

    2024年02月04日
    浏览(35)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(47)
  • 二叉树进阶(搜索二叉树)

    目录 引言  1.二叉搜索树的模拟实现 1.1  链式二叉树的定义 1.2 二叉搜索树的模拟实现  1.2.1 二叉搜索树的结点类 1.2.2 二叉搜索树类的构造与中序遍历实现 1.2.3 增 1.非递归实现 2.非递归实现 1.2.4 查 1.非递归实现 2.递归实现  1.2.5 删 1.非递归实现 (1)情况分析 (2)解决方案  (

    2024年02月15日
    浏览(286)
  • 二叉树题目:对称二叉树

    标题:对称二叉树 出处:101. 对称二叉树 3 级 要求 给你一个二叉树的根结点 root texttt{root} root ,检查它是否轴对称。 示例 示例 1: 输入: root   =   [1,2,2,3,4,4,3] texttt{root = [1,2,2,3,4,4,3]} root = [1,2,2,3,4,4,3] 输出: true texttt{true} true 示例 2: 输入: root   =   [1,2,2,null,3,null,

    2024年02月12日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包