线性表顺序存储结构、树

线性表顺序存储结构
优点：1、无须为表示表中元素之间的逻辑关系而增加额外的存储空间。2、可以快速的存取表中任一位置的元素。
缺点：1、插入和删除操作需要移动大量元素。2、当线性表长度变化较大时，难以确定存储空间的容量。3、造成存储空间的碎片。

线性表的链式存储结构
特点：查询元素慢，增加删除速度快。

栈与队列
栈是限定仅在表尾（栈顶）进行插入和删除操作的线性表。
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。
它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。

image.png

树
树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：
（1）有且仅有一个特定的称为根（Root）的结点；
（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

image.png image.png image.png image.png

森林：对树中每个结点而言，其子树的集合即为森林。

树的存储结构
三种表示法：双亲表示法、孩子表示法、孩子兄弟表示法
1、双亲表示法：我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。（个人理解就是每一个结点持有父节点的索引）
这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为O（1），知道parent为-1时，表示找到了树结点的根。
可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。
改进一下，我们增加一个结点的最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。

后面两种表示法没看懂

6.5 二叉树的定义。大话数据结构191 程杰著

image.png