一、顺序存储
优点:读取某个指定的节点的时候效率比较高O(0)
缺点:会浪费空间(在非完全二叉树的时候)
二、链式存储
优点:读取某个指定节点的时候效率偏低O(nlogn)
缺点:相对二叉树比较大的时候浪费空间较少
二叉树的顺序存储,寻找后代节点和祖先节点都非常方便,但对于普通的二叉树,顺序存储浪费大量的存储空间,同样也不利于节点的插入和删除。因此顺序存储一般用于存储完全二叉树。
链式存储相对顺序存储节省存储空间,插入删除节点时只需修改指针,但寻找指定节点时很不方便。不过普通的二叉树一般是用链式存储结构。
扩展资料:
性质1:二叉树的第i层上至多有2i-1(i≥1)个节点
性质2:深度为h的二叉树中至多含有2h-1个节点
性质3:若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1
性质4:具有n个节点的完全二叉树深为log2x+1(其中x表示不大于n的最大整数)
参考资料来源:百度百科-二叉树
1。对于完全二叉树就用数组表示法,结点i的左孩子为2*i,右孩子为2*i+1,双亲为i/22。双亲数组表示法。这个我没用过,大概是对每个结点记录其双亲,但是结点不一定是连续的,比如:
结点
双亲
1
0
4
1
3
4
5
2
2
1
嘛,这个只是从底向上的遍历比较简单,所以一般不用
3。孩子链表表示法
对于每个结点给予两个指针域分别指向其左孩子,右孩子,若指针域为空则表示没有这边的孩子。
详细的实现比较长懒的写了,随便找点资料好了。
基础的就这三种,一般用到的也是这样,其他也就是没有大改动只是加入一些域什么的而已。。。
以上纯手打
此结构是将二叉树的所有结点,按照一定的次序,存储到一片连续的存储单元中。
因此,必须将结点排成一个适当的线性序列,
使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。
这种结构特别适用于近似满二叉树。
在一棵具有n个结点的近似满二叉树中,
我们从树根起,自上层到下层,逐层从左到右给所有结点编号,就能得到一个足以反映整个二叉树结构的线性序列
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)