数据结构之二叉树简介

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

二叉树

二叉树是一种非线性数据结构,代表“祖先”与“后代”之间的派生关系,体现了“一分为二”的分治逻辑。与链表相似,二叉树的基本单元是节点,每个节点包含值,左子节点的索引,右子节点的索引

/* 二叉树节点结构体 */
struct TreeNode {
    int val;          // 节点值
    TreeNode *left;   // 左子节点指针
    TreeNode *right;  // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
  • 当给定一个二叉树的节点时,我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树,同理可得,右子节点及其以下节点形成的树称为该节点的右子树。

  • 在给定的二叉树中,除了叶子节点,其他所有节点均包含子节点和非空子树文章来源地址https://www.toymoban.com/news/detail-789799.html

二叉树的常见术语

  • 根节点:位于二叉树顶层的节点,没有父节点
  • 叶子节点:没有字节的的节点,左右指针均为null
  • 边:连接两个节点的线段,
  • 节点所在的层:从顶到底递增,根节点的层数为1
  • 节点的度:节点的字节点的个数,在二叉树中,节点的度的取值范围:0,1,2
  • 二叉树的高度:从根节点到最远叶子节点所经过的边的数量
  • 节点的深度:从根节点到该节点边的数量
  • 节点的高度:从最远的叶子节点到该节点边的数量

二叉树的基本操作

/* 初始化二叉树 */
// 初始化节点
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// 构建节点之间的引用(指针)
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
/* 插入与删除节点 */
TreeNode* P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1->left = P;
P->left = n2;
// 删除节点 P
n1->left = n2;

常见二叉树的类型

  • 完美二叉树:**所有层的节点都被填满。**所有叶子节点的度为0,其余所有节点的度为2
  • 完全二叉树:只有最底层的节点没有被填满并且最底层的节点靠左填满
  • 完满二叉树:除了叶子节点外,其余所有节点的度为2
  • 平衡二叉树:任意节点的左子树和右子树的高度之差的绝对值不超过1

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

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

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

相关文章

  • 数据结构之二叉树(详细版)

            二叉树作为数据结构的一种,尤为重要,下面是对二叉树的详细讲解。想要了解二叉树,首先要了解 二叉树的基本概念,以及创建二叉树的结构,再深层点,遍历二叉树的前序中序和后续,其次是层序,后面将会讲解如何计算二叉树的高和叶结点 等等。        

    2024年02月03日
    浏览(46)
  • 数据结构之二叉树(Java)

    在这里先说明一下,结点和节点其实一样的,无须关注这个。 1. 概念:树是一种非线性的数据结构,它是由n个有限节点组成一个具有层次关系的集合。 如上图所示,把此种数据结构称作树是因为它看起来像一个倒挂的树。  2. 特点 有一个特殊的节点,称为根节点,它是唯一

    2024年02月07日
    浏览(39)
  • 数据结构之二叉树的实现

    目录 前言 1. 二叉树的遍历 1.1二叉树的前、中、后序遍历 1.2 层序遍历 2.二叉树的实现 2.1 二叉树的结构 2.2构建二叉树  2.2 前序遍历的实现 2.3 中序遍历的实现 2.4 后序遍历的实现 2.5 计算树的节点个数 2.6 计算树的深度 2.7 计算叶子节点个数 2.8 计算树第k层的节点数 2.9 以内容

    2023年04月10日
    浏览(49)
  • 《数据结构与算法》之二叉树(补充树)

    二叉搜索树,也称二叉排序树或二叉查找树 二叉搜索树:一棵二叉树,可以为空,如果不为空,应该满足以下性质: 非空左子树的所有结点小于其根结点的键值 非空右子树的所有结点大于其根结点的键值 左右子树都是二叉搜索树 对于二叉树的查找,其实沿用的是分治法的

    2024年02月08日
    浏览(49)
  • 数据结构之二叉树的性质与存储结构

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月21日
    浏览(49)
  • 数据结构之二叉树的数组表示

    若某节点的索引为 i ,则该节点的左子节点的索引为 2i+1 ,右子节点的索引为 2i+2 给定某节点,获取它的左右字节点,父节点 获取前序遍历,中序遍历,后序遍历,层序遍历

    2024年01月18日
    浏览(51)
  • 数据结构奇妙旅程之二叉树初阶

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年01月19日
    浏览(64)
  • 【数据结构之二叉树的构建和遍历】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续完善二叉树的相关知识并完成实现二叉树的构建和遍历的内容。 / 知识点汇总 / 因为前篇已经非常详细的单独学习了数和二叉树的基本知识概念,那么这里就简单回顾一下即可。 概念 : 二叉树(Bina

    2024年02月21日
    浏览(47)
  • 数据结构之二叉树(C语言附详细代码)

    目录 一,树和二叉树 1.树 ①定义 ②关于树的一些概念 2.二叉树 ①定义 ②特殊的二叉树 ③二叉树的性质 ④二叉树的存储结构(顺序结构,只适用于完全二叉树) ⑤二叉树的遍历 二,二叉树操作代码 1.头文件 2.函数代码 ①创建二叉树 ②前序遍历二叉树 ③中序遍历二叉树 ④后序

    2024年02月01日
    浏览(33)
  • 数据结构初阶之二叉树的详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 1.前言  2.二叉树各个功能代码实现 2.1二叉树结构体 2.2二叉

    2024年02月05日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包