二叉树 两种存储结构的优缺点

一、顺序存储

优点：读取某个指定的节点的时候效率比较高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/2

2。双亲数组表示法。这个我没用过，大概是对每个结点记录其双亲，但是结点不一定是连续的，比如：

结点

双亲

1

0

4

1

3

4

5

2

2

1

嘛，这个只是从底向上的遍历比较简单，所以一般不用

3。孩子链表表示法

对于每个结点给予两个指针域分别指向其左孩子，右孩子，若指针域为空则表示没有这边的孩子。

详细的实现比较长懒的写了，随便找点资料好了。

基础的就这三种，一般用到的也是这样，其他也就是没有大改动只是加入一些域什么的而已。。。

以上纯手打

---