线性链表及树
线性链表的基知：
1、线性链表的链式存储结构称为线性链表，每一个元素都有2部分组成。分别为数据域、指针域
2、链式存储既可以表示线性结构，也可以表示非线性结构
3、线性链表在进行元素插入与删除时，不需要移动表中的元素
4、线性链表的在存储时，存储空间可以连续也可以不连续
5、在线性单链表中，只能由根结点开始，遍历到所以结点，而且顺序不能颠倒
6、在双向链表、循环链表中，可以从任何一个结点开始直接遍历到所以结点
7、循环链表、循环队列都是顺序存储结构
8、链表结点中具有两个指针域的数据结构可以说线性结构，也可以是非线性结构
9、除前驱和后继，每一个结点只要有大于1的前件和后件就属于非线性结构
10、链式存储比顺序存储更耗费空间，毕竟链式存储一半是存数据，一半是存指针
树的基本概念：
1、树是n（n>=0）个结点的有限集合T
2、二叉树：
（1）、二叉树是另一种树形结构，它的特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，不能任意颠倒。
（2）、二叉树的基本术语：
a、结点：表示树中的元素，包含数据项及若干子树的分支；
b、叶子结点：也叫终端结点，是度为0的结点；
c、分支结点：也叫子节点，度不为0的结点；
d、结点的度：拥有结点子树的个数；
e、树的深度：树中最大的结点层数；
（3）、二叉树的性质：
a、一棵非空二叉树的第i层上最多有2i-1个结点；（计算叶子结点数）
b、一棵深度为k的二叉树，最多有2k-1个结点；（计算总结点数）
c、一棵二叉树中度为0的结点总比度为2的多一个结点；（叶子比根多一个）
d、总结点数：叶子结点+字结点+度为1的结点；（自己理解的）
3、完全二叉树：
完全二叉树是指除最后一层外，每一层上结点数均达到最大值，而在最后一层上指缺失右边若干结点。
4、满二叉树：
在一棵二叉树中，如果所有分支结点都存在左右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。
1、一棵二叉树共有70个叶子结点与80个度为1的结点，则二叉树的总结点数是【A】
(A).219 (B).221
(C).229 (D).231
分析：度为1的结点80+叶子结点70+子节点69=219
2、某二叉树有n个度为2的结点，则该二叉树的叶子结点是【B】
(A).n+1 (B).n-1
(C).2n (D).n/2
3、在深度为7的满二叉树中，度为2的结点个数为【63】；叶子结点的个数是【64】
4、某二叉树共有400个结点，其中有100个度为1的结点，则该二叉树中的叶子结点数为【B】
(A).151
(B).不存在这样的二叉树
(C).150
(D).149
分析：叶子结点+子结点=总结点-度为1的结点===》300，因此设叶子结点为x，则子结点为x-1，则：x+x-1=300===》x301/2，因此不存在这样的二叉树
5、一棵深度为7的完全二叉树，总结点个数为125，问这个数的叶子结点个数为【B】
(A).62 (B).63
(C).64 (D).65
分析：这个题可以根据完满叉树做，深度为7，则满二叉树总结点是128个，则是完成二叉树深度为7，总结的数为125，则推理出度为1的结点为3个，因此设叶子结点为x，则子结点为x-1，得出x=63