二叉树 两种存储结构的优缺点
作者&投稿:泰备 (若有异议请与网页底部的电邮联系)
- 当需要读取或访问特定节点时,顺序存储结构具有较高的效率,时间复杂度为O(1)。
顺序存储结构的缺点:
- 在处理非完全二叉树时,会存在空间浪费的问题。
二、链式存储结构的优点:
- 相较于顺序存储,链式存储在访问特定节点时效率虽低,时间复杂度为O(n),但在处理大规模二叉树时,空间浪费较少。
链式存储结构的缺点:
- 在进行节点的插入和删除操作时,链式存储结构仅需修改指针,相对较为方便,但查找特定节点时较为不便。
三、二叉树的存储结构选择:
- 对于完全二叉树,顺序存储结构因其便于寻找后代和祖先节点的优势而被广泛使用。
- 对于普通的二叉树,链式存储结构在节省空间方面更具优势,且插入和删除操作更为便捷。
扩展资料:
- 性质1:二叉树的第i层上至多有2^(i-1)个节点(i≥1)。
- 性质2:深度为h的二叉树中至多含有2^h-1个节点。
- 性质3:若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1。
- 性质4:具有n个节点的完全二叉树深度为log2(n)+1,其中x表示不大于n的最大整数。
参考资料来源:百度百科-二叉树
谯固复方: 链式结构优点都是便于寻址,二叉链表缺点结构性开销随着数据结构的规模变大而变大(尤其是叶子节点都有2个NULL,即损失2*sizeof(ElemType*)) 线性结构优点没有结构性开销,缺点个人感觉是插入和删除不够方便?试用场合估计取决问题...
郁南县13177007588: 二叉树的两种物理结构是什么 - ?
谯固复方: 答:二叉树就物理结构来分可以分成:顺序存储结构和链式存储结构. (1)顺序存储结构:顺序存储结构,顾名思义就是二叉树的数据元素存放在一组连续的存储单元中.其主要有一下几个特点:①逻辑上相邻的两个元素在物理位置上也是相邻的;②操作删除和插入的时候,需要整体移动元素;③需要预先分配空间,不能动态增长; (2)链式存储结构:链式存储结构中二叉树的每个结点至少包含三个域:数据域、左指针域和右指针域.其二叉树是通过指针实现,链式存储结构有以下几个特点:①逻辑上相邻的两个元素在物理位置上不一定是相邻的;②操作删除和插入的时候,不需要整体移动元素;只需要修改相应的指针即可;③不需要预先分配空间;④存储指针本身会消耗一定的存储的空间;
郁南县13177007588: 二叉树的存储结构是怎样的?有哪些类型的存储结构?对应的c语言描述是??
谯固复方: 楼上回答的是树的存储,不是二叉树的存储,主要如下: 1、顺序存储:适用于完全二叉树,如果根从1开始编号,则第i结点的左孩子编号为2i,右孩子为2i+1,双亲编号为(i/2)下取整,空间紧密 2、二叉链表:适用于普通二叉树,每个结点除了数据外,还有分别指向左右孩子结点的指针,存储n个结点有n+1个空指针域,存储密度小于顺序存储,但是适用范围广,缺陷是正常遍历只能从双亲向孩子,退回来一般需要借助栈(或者用递归,其实也是栈) 3、三叉链表:同样适用于普通二叉树,结点除了数据外,还有左右孩子与双亲的指针,存储密度低于二叉链表,但是可以非常方便地在二叉树中遍历,不需要其他辅助工具
郁南县13177007588: 数据结构中,图与树,二叉树比线性表有什么优点? - ?
谯固复方: 图:非线性结构 点与点是多对多的关系 之间是平等的 没有父节点 兄弟 孩子之分 树:非线性结构 点与点是一对多的关系 有父节点 孩子节点 兄弟节点 (注意*树不能为空**** 所以二叉树不是树)存储: 双亲表示法 孩子表示法 孩子兄弟表示法) 二叉树:有左右方向之分 可以为空 ,二叉树可以顺序存储(主要用于完全二叉是树的存储)也可用二叉链表 三叉链表 索引表 线性表:线性结构可以顺序表示 也可以用链表表示
郁南县13177007588: 数据结构知识归纳?
谯固复方: 第一章:数据结构概述 一、什么是数据结构 1、作者开篇谈到: 一般来说解决一个具体的问题时,大致需要经过下列几个步骤:首先要从具体的问题抽象出一个适当的数学模型,然后设计一个解此数学模型的算法,最后编写出程序代码,进行...
郁南县13177007588: 三叉链表与二叉链表储存结构比较,有何区别?有何优缺点? - ?
谯固复方: 三叉链表相比二叉链表,比较容易访问到双亲,二叉链表则只能往孩子方向访问(不算线索化的),确定自然是三叉链表的空间浪费较多,存储密度比二叉链表要低
郁南县13177007588: 二叉树的顺序存储结构最适用于什么二叉树,为什么? - ?
谯固复方: 二叉树的顺序存储结构最适用于完全二叉树,因为叶子结点在最下面两层,中间没有空的
郁南县13177007588: 二叉树相关知识 - ?
谯固复方: 二叉树 (binary tree) 是另一种树型结构,它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 ),并且,二叉树的子树有左右之分,其次序不能任意颠倒 . 二叉树是一种数据结构 :Binary_tree=(D,R)其中: D是具有...
郁南县13177007588: 数据结构中树与二叉树的区别在于? - ?
谯固复方: 二叉树是树的一种,开可以有三叉树、四叉树、……,以及混合叉树.不过一般只讨论二叉树,这是最典型、最有用的数据结构.
郁南县13177007588: 散列表和二叉树的优缺点对比,如何在这两种数据结构中选择 - ?
谯固复方: 散列表的优点很明显,查询时间为常数1,最快的查询速度.二叉树的查询速度也很快,为log(n)但是慢于散列表.但是二叉树相对于散列表的优点是,对于一个二叉查找树,即binary search tree,其中元素是排序的,而散列表是不排序的.那么问题就来了,在你手机中,显然你希望联系人是按姓氏排序的,那么如果你使用散列表,你就需要额外的内存空间进行排序,而二叉查找树本身就是排好序的,因此节省了宝贵的空间.结论就是,在空间不受限制时,且不需要高频率的排序操作时,二叉查找树不如散列表.反之二叉查找树优于散列表.