7. 矩阵
特殊矩阵：矩阵中的元素 (或非0元素)的分布有一定的规律。常见的特殊矩阵 有对称矩阵、三角矩阵和对角矩阵。
稀疏矩阵：在一个矩阵中， 若非零元素的个数远远少于 零元素个数，且非零元素的 分布没有规律。
存储方式为三元组结构，即存储每个非零元素的（行， 列，值)。
8.广义表
广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
广义表与线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的 元素既可以单元素，也可以是有结构的表。
广义表一般记为：LS=(a1,a2,…,an) 其中LS是表名，ai是表元素，它可以是表（称为子表），也可以是数据元素（称为原子)。其中n是广义表的长度（也就是最外层包含的元素个数），n=0的广义表 为空表；而递归定义的重数就是广义表的深度，即定义中所含括号的重数（单边 括号的个数，原子的深度为0，空表的深度为1)。
head(和tail():取表头（广义表第一个表元素，可以是子表也可以是单元素）和取表尾（广义表中，除了第一个表元素之外的其他所有表元素构成的表，非空广义表的表尾必定是一个表，即使表尾是单元素)操作。
树
树结构是一种非线性结构，树中的每一个数据元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系。
树是n个结点的有限集合(n>=0),当n=0时称为空树，在任一颗非空树中，有且 仅有一个根节点；其余结点可分为m(m>=0)个互不相交的有限子集T1,T2,,Tm, 其中每个又都是一棵树，并且成为根结点的子树。 树的结构如下图所示
树的基本概念如下：
（1）双亲、孩子和兄弟。结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
（2）结点的度。一个结点的子树的个数记为该结点的度。
（3）叶子结点。叶子结点也称为终端结点，指度为0的结点。
（4）内部结点。度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
（5）结点的层次。根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第计1层。
（6)树的高度。一棵树的最大层数记为树的高度（或深度）。
（7）有序(无序)树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
二叉树
二叉树是个节点的有限集合，它或者是空树，或者是由一个根节点及两颗互不相交的 且分别称为左、右子树的二叉树所组成。与树的区别在于每个根节点最多只有两个孩 子结点。
设一棵二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。
满二叉树：每层都是满结点的。
完全二叉树的k-1层是满结点的，第k层结点从左到右是满的。 如下图所示:
二叉树的存储结构
二叉树的顺序存储结构
顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。
对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此，从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。假设有编号为i的节点，则有：
二叉树的链式存储结构
一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储有左孩 子结点的指针、右孩子结点的指针，即一个数据+两个指针。 每个二叉链表节点存储一个二叉树节点，头指针则指向根节点。
二叉树的遍历
一颗非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整颗二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有下列三种遍历方式：
先序（前序）遍历：根左右。
中序遍历：左根右。
后序遍历：左右根。
还有层次遍历方法： 层次遍历：按层次，从上到下，从左到右。
线索二叉树
引入线索二叉树是为了保存二叉树遍历时某节点的前驱节点和后继节点的信息，二叉树的链式存储只能获取到某节点的左孩子和右孩子结点，无法获取其遍历时的前驱和后继节点，因此可以在链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法：
若n个节点的二叉树使用二叉链表存储，则必然有n+1个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历节点，如下：
若二叉树的二叉链表采用上述结构 则称为线索链表，其中指向前驱、 后继节点的指针称为线索，加上线 索的二叉树称为线索二叉树。
最优二叉树
最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树，相关概念如下：
路径：树中一个结点到另一个结点之间的通路。
结点的路径长度：路径上的分支数目。
树的路径长度：根节点到达每一个叶子节点之间的路径长度之和。
权：节点代表的值。
结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值。
树的带权路径长度（树的代价）：树的所有叶子节点的带权路径长度之和。
哈夫曼树
哈夫曼树的求法：给出一组权值，将其中两个最小的权值作为叶子节点，其和作 为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到 该组权值中。重复进行上述步骤，直至所有权值都被使用完。
构造出的哈夫曼树中，所有初始给出的权值都作为了叶子节点，此时，求出每个 叶子节点的带权路径长度，而后相加，就是树的带权路径长度，这个长度是最小 的。
树和森林
树的存储结构
双亲表示法：用一组连续的地址单元存储树的节点，并在每个节点中附带一个指 示器，指出其双亲节点所在数组元素的下标。
孩子表示法：在存储结构中用指针指示出节点的每个孩子，为树中每个节点的孩 子建立一个链表。
孩子兄弟表示法：又称为二叉链表表示法，为每个存储节点设置两个指针域，分 别指向该节点的第一个孩子和下一个兄弟节点。
树和森林的遍历
由于树中每个节点可能有多个子树，因此遍历树的方法有两种：
先根遍历：先访问根节点，再依次遍历根的各颗子树。
后根遍历：先遍历根的各颗子树，再访问根节点。
森林中有很多课树，森林的遍历方法也分为两种，与树的遍历类似，就是对森林 中的每棵树都依次做先根遍历或后根遍历。
树和二叉树的转换
规则是：树的最左边节点作为二叉树的左子树，树的其他兄弟节点作为二叉树的右子树节点。
示例如下图：采用连线法，将最左边节点和其兄弟节点都连接起来，而原来的父节点和兄弟节点的连线则断开，这种方法最简单，要求掌握。
查找二叉树
查找二叉树上的每个节点都存储一个值，且每个节点的所有左孩子结点值都小于父节点值，而所有右孩子结点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。
二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小，而单枝树的深度是最大的，故效率最差。
平衡二叉树
前面讲过查找（排序）二叉树，特点是所有左子树值小于根节点值，所有右子树值大于根节点值，而这个特点可以构造出多个不同的二叉树，并不唯一，因此提出平衡二叉树的概念，在查找二叉树特点的基础上，要求每个节点的平衡度只能为0或1或-1.
节点的左右子树深度就是其左右子树各自的层数，而后将左子树深度减去右子树深度，就得到了该节点的平衡度。因此，平衡二叉树就是任意左右子树层次相差不超过1
网友评论