对于数组A[c1…d1,c2..d2], 以行序为主序 L0C(a,j)=LOC(acl,ce2)+[(i-c1)*(d2-c2+1)+(-c2)】*k 以列序为主序 L0Ca,j)=L0(acl,c2)+[(j-c2)*(d1-c1+1)+(1-c1)]喇 3.特殊矩阵的压缩存储 (1)对称矩阵 若一个n阶方阵Amm中的元素满足ai,j=aj,i(0≤i,j≤n1),则称其为n阶对称矩阵。 A[O.n-1][0..n-1]-B[0..n(an+1)/2] i(i+1)/2+j 当i≥j时 j(j+1)/2+i 当i<j时 (2)三角矩阵 采用类似的压缩方法 4.稀疏矩阵 (1)三元组表示 (2)十字链表表示 各种表示的基本思路 则1oc(A[2][2])为多少? 答:Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=10m长度为2, 【例5.1】二维数组A[4][4](即A[0..3][0..3])的元素起始地址是1oc(A[O][0])=1000,元素的长度为2, 第6章树和二叉树 6.1树 1.树的定义 树是由n(n≥0)个结点组成的有限集合(记为T)。其中, 如果n=0,它是一棵空树,这是树的特例; 如果n>0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分 为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根 root的子树 2.树的表示法(逻辑表示方法 (1)树形表示法 (2)文氏图表示法 (3)凹入表示法 (4)括号表示法 3.树的遍历 先根遍历算法为 (1)访问根结点 (2)按照从左到右的次序先根遍历根结点的每一棵子树 后根遍历算法为 (1)按照从左到右的次序后根遍历根结点的每一棵子树 (2)访问根结点 4.树(森林)与二叉树之间的相互转换 6.2二叉树 1.二叉树的定义 叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不 相交的称为左子树和右子树的二叉树组成。 完全二叉树,满二叉树的定义 2.二叉树性质 性质1非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1 性质2非空二叉树上第i层上至多有21-1个结点(i≥1) 质3高度为h的二叉树至多有2-1个结点(h≥1) 性质4完全二叉树的性质 性质5具有n个(n>0)结点的完全二叉树的高度为1og2n+1或 loggn+1 【例6.1】将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点 的编号为1,则编号为49的结点的左孩子编号为。对于数组 A[c1 ..d1 ,c2 ..d2 ] , 以行序为主序 : LOC(ai,j)=LOC(ac1,c2)+[(i-c1 )*(d2 -c2 +1)+(j-c2 )]*k 以列序为主序 LOC(ai,j)=LOC(ac1,c2)+[(j-c2 )*(d1 -c1 +1)+(i-c1 )]*k 3.特殊矩阵的压缩存储 (1) 对称矩阵 若一个 n 阶方阵 A[n][n]中的元素满足 ai,j=aj,i（0≤i，j≤n-1），则称其为 n 阶对称矩阵。 A[0..n-1][0..n-1]->B[0..n(n+1)/2] i(i+1)/2 +j 当 i≥j 时 k= j(j+1)/2 +i 当 i＜j 时 (2)三角矩阵 采用类似的压缩方法. 4.稀疏矩阵 (1) 三元组表示 (2) 十字链表表示 各种表示的基本思路。 【 例 5.1】 二维数组 A[4][4]（即 A[0..3][0..3]）的元素起始地址是 loc(A[0][0])=1000，元素的长度为 2， 则 loc(A[2][2])为多少？ 答：Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=1020。 第 6 章 树和二叉树 6.1 树 1.树的定义 树是由 n（n≥0）个结点组成的有限集合（记为 T）。其中， 如果 n=0，它是一棵空树，这是树的特例； 如果 n>0，这 n 个结点中存在（有仅存在）一个结点作为树的根结点，简称为根（root），其余结点可分 为 m （m>0）个互不相交的有限集 T1 ,，T2，…，Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根 root 的子树。 2.树的表示法 (逻辑表示方法) (1) 树形表示法 (2) 文氏图表示法 (3) 凹入表示法 (4) 括号表示法 3.树的遍历 先根遍历算法为： （1）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。 后根遍历算法为： （1）按照从左到右的次序后根遍历根结点的每一棵子树； （2）访问根结点。 4.树(森林)与二叉树之间的相互转换 6.2 二叉树 1.二叉树的定义 二叉树也称为二次树或二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不 相交的称为左子树和右子树的二叉树组成。 完全二叉树,满二叉树的定义 2.二叉树性质 性质 1 非空二叉树上叶结点数等于双分支结点数加 1。即 n0=n2+1. 性质 2 非空二叉树上第 i 层上至多有 2 i-1 个结点（i≥1）。 性质 3 高度为 h 的二叉树至多有 2 h-1 个结点（h≥1） 。 性质 4 完全二叉树的性质 。 性质 5 具有 n 个（n＞0）结点的完全二叉树的高度为 log2 n+1 或 log2 n+1。 【例 6.1】将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点 的编号为 1，则编号为 49 的结点的左孩子编号为