首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

算法与数据结构(三) 二叉树的遍历及其线索化(Swift版)

前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作,并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西,并且所涉及的相关Demo依然使用面向对象语言Swift来表示。本篇博客我们就来介绍树结构的一种:二叉树。在之前的博客中我们简单的聊了一点树的东西,树结构的特点是除头节点以外的节点只有一个前驱,但是可以有一个或者多个后继。而二叉树的特点是除头结点外的其他节点只有一个前驱,节点的后继不能超过2个。 本篇博客,我们只对二叉树进行讨论。在本篇博客中,我们对二叉树进行创建,然后进行各种遍历

010
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法与数据结构(十一) 平衡二叉树(AVL树)(Swift版)

    今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树,详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊平衡二叉树,也叫AVL树,AVL是发明平衡二叉树的两个科学家的名字的缩写,在此就不做深究了。其实平衡二叉树就是二叉排序树的一种,比二叉排序树多了一个平衡的条件。在一个平衡二叉树中,一个结点的左右子树的深度差不超过1。 本篇博客我们就依照平衡二叉树的特点,在创建二叉排序树的同时要保证结点的左右子树的深度差不超过1的规则。当我们往二叉排序树中插入结点时,

    07

    【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。 基于二叉树的链式结构,于是可以先malloc动态开辟出二叉树的每个节点并初始化,然后通过节点中的指针struct BinaryTreeNode* left(指向左树)和struct BinaryTreeNode* right(指向右树),将各个节点连接起来,最后大致模拟出了一棵二叉树,代码如下:

    01

    【Java数据结构】二叉树详解(一)

    结点的度:一个结点含有子树的个数称为该结点的度; 如上图:A的度为6 树的度:一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6 叶子结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I...等节点为叶结点 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点 根结点:一棵树中,没有双亲结点的结点;如上图:A 结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推 树的高度或深度:树中结点的最大层次; 如上图:树的高度为4 树的如下概念只需了解,我们只要知道是什么意思即可: 非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G...等节点为分支结点 兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点 堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为堂兄弟结点 结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙 森林:由m(m>=0)棵互不相交的树组成的集合称为森林

    01

    [数据结构]—二叉树基本概念

    节点的度:一个节点含有的子树的个数称为该节点的度; 如上图: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)棵互不相交的树的集合称为森林;

    01

    二叉树的性质及其创建

    二叉树的性质 性质1 在二叉树的第i层上至多有2^(i-1)个结点(i>=1) 性质2 深度为k的二叉树至多有2^k-1个结点(k>=1) 性质3 对任意一棵二叉树,若终端结点数为n0,其度数为2的结点数为n2,那么n0=n2+1 满二叉树 深度为k且结点个数为2^k-1,即每一层都具有最大结点数 完全二叉树 深度为k,结点数为n的二叉树,如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号对应,则为完全二叉树 性质4 具有n个结点的完全二叉树的深度为ceil[log(2)(n)]+1 性质5 具有n个结点的完全二叉树,结点的序号i满足 ①i=1,结点i为根结点 ②2i>n,结点i无左孩子;2i<n,结点i的左孩子序号为2i ③2i+1>n,结点i无右孩子;2i+1<n,结点i的右孩子序号为2i+1

    03

    扫码

    添加站长 进交流群

    领取专属 10元无门槛券

    手把手带您无忧上云

    扫码加入开发者社群

    相关资讯

    热门标签

    活动推荐

      运营活动

      活动名称
      广告关闭
      领券