1. 数组特点：与线性表一样，所有数据元素都必须属于同一数据类型。 2. 数组的顺序存储结构：由于数组一般不作插入或删除操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不会发生变动，因此采用顺序存储结构表示数组。 存储位置计算：假设每个数据元素需占用L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定
以行序为主序的存储结构：LOC(i,j)=LOC(0,0)+(b2*i+j)*L 以列序为主序的存储结构：LOC(i,j)=LOC(0,0)+(b2*j+i)*L
式中LOC(i,j)是aij的存储位置；LOC(0,0)是a00的存储位置，即二维数组A的起始存储位置，也称基地址或基址；b2在以行序为主序的存储结构时为每行存储元素的个数(列数)，在以列序为主序的存储结构时为每列存储元素的个数(行数)。
3. 广义表：是线性表的推广，也有人称其为列表（lists，用复数形式以示与统称的表list的区别）。记作LS=(a1,a2,?an) ，其中LS是广义表(a1,a2,…an)的名称，n是它的长度。在线性表的定义中，ai(1≤i≤n)只限于是单个元素。而在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。 例如：
第6章、树和二叉树
1. 二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
2. 二叉树的性质：
1) 性质1：在二叉树的第i层上至多有2的i减1次方个结点(i≥1)。 2) 性质2：深度为k的二叉树至多有2的k次方减1个结点(k≥1)。
深度为k的二叉树至少有k个结点(k≥1)。
深度为k的完全二叉树至少有2的k次方减2的k减1次方个结点(k≥1)。
3) 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
4) 性质4：具有n个结点的完全二叉树的深度为[log2n]+1。
5) 性质5：如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一结点i（1
≤i≤n）有：
a) 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点[i/2]。 b) 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。
c) 如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。 3. 满二叉树：一颗深度为k且有 2的k次方减1个结点的二叉树。
4. 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。 5. 遍历二叉树：
-1) 根据二叉树写遍历结果：
a) 先序遍历（先根遍历）：DLR +/- + a * b - c d / e f
b) 中序遍历（中根遍历）：LDR a*efa + b * c - d - e / f
b-c) 后序遍历（后根遍历）：LRD
a b c d - * + e f / -
cd
2) 根据遍历结果画二叉树：
一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出，试求出空格处的结点字符，并画出该二叉树。
A先序：__B__EHI__FG__K 中序：D__HEIA__CJG__ 后序：__H__EBF__KG__A
解题思路：
a) 由先序或后序确定根结点；如本题后序最后一个为A，根结点为A，所以先序
DEFG第一个空就为A。
b) 在中序找出根结点，根结点左侧为左子树，右侧为右子树；如本题D__HEI为
HIJK左子树，__CJG__为右子树。
c) 由先序确定紧跟在根结点后的左子树根；如本题紧跟在A后的是B，B为左子树根，中序根结点的左子树只有一个空，所以为B。
d) 继续由中序确定左子树根的左右子树，左侧为左子树，右侧为右子树；如本题B的左子树为D，右子树为HEI，所以先序第二个空为D。
e) 重复c)、d)步骤确定整棵左子树；如本题先序中紧跟在D后的是E，E为B的右子树，由中序中看出E左子树为H，右子树为I，补充后序填空，前两空分别为D和I。
f) 由后序确定右子树根的左子树，再由中序确定右子树根；如本题紧跟在B后的是F，F为右子树根的左子树，已知中序__CJG__为右子树，F只可能第一个空，
BC那第二个空为K，补全先序、中序、后序填空并可画出二叉树。 6. 森林与二叉树的转换：
1) 树转换成二叉树：连兄弟，留长子，删孩子。 a) 连线，连接所有兄弟结点。
b) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。 c) 整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。 d) 注意，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子树必为空。
2) 森林转换成二叉树：连树根及兄弟，留长子，删孩子。 a) 连线，连接每棵树的根结点及所有兄弟结点。
b) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。 c) 整理，第一棵树根结点为二叉树根结点，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。
3) 二叉树转换成树：连左孩子的右孩子及其右孩子?，删原树右孩子。
a) 连线，若某结点X存在左孩子XL，则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR、左孩子的右孩子的右孩子的右孩子结点XLRRR?都与X结点连线。
b) 删线，删除原二叉树的所有双亲与右孩子结点的连线。 c) 整理，原二叉树根结点为树根结点。
4) 二叉树转换成森林：连左孩子的右孩子及其右孩子?，删原树右孩子。 a) 连线，若某结点X存在左孩子XL，则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR、左孩子的右孩子的右孩子的右孩子结点XLRRR?都与X结点连线。
b) 删线，删除原二叉树的所有双亲与右孩子结点的连线。 c) 整理，调整为多棵树的森林。
7. 赫夫曼树：又称最优树，是一类带权路径长度最短的树。
a) 两个最小数值组成一对，小的在前，大的在后；如上图中2与4最小，2在前，4在后。
b) 将两个最小数值的和算作一个数，再与其他数重复a)步骤；如上图中2与4的和为6，5与6最小，5在前，6在后。
c) 最后计算WPL，它等于每个数值乘以从根结点到这个数值的连线个数的积之和；如上图中WPL=2*3+4*3+5*2+7*1=35。 8. 赫夫曼编码：
a) 在赫夫曼树上，左分支代表0，右分支代表1。 b) 由根结点到指定结点的路径(从上到下把0、1连起来)，就是该结点的赫夫曼编码；如上图(d)中a为0，b为10，c为110，d为111。
第7章、图
1. 图：多个结点，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。
2. 无向完全图：有n(n-1)/2条边的无向图。 3. 有向完全图：有n(n-1)条边的有向图。
4. 入度：以顶点V为头的弧的数目称为V的入度。 5. 出度：以V为尾的弧的数目称为V的出度。
6. 连通图：在无向图中，任意两个顶点之间都有路径。 7. 连通分量：在无向图中的极大连通子图。