数据结构教程（Java语言描述）（第2版 微课视频版） 课件 李春葆 第6-10章 数组和稀疏矩阵 -排序

第6章数组和稀疏矩阵6.1数

组6.2特殊矩阵的压缩存储CONTENTS提纲6.3稀疏矩阵1/55数组是一个二元组（idx，value）的集合，对每个idx，都有一个value值与之对应。idx称为下标，可以由一个整数、两个整数或多个整数构成，下标含有d（d≥1）个整数称为维数是d。数组按维数分为一维、二维和多维数组。一维数组A是n（n>1）个相同特性元素a0，a1，…，an-1构成的有限序列，其逻辑表示为A=（a0，a1，…，an-1），其中，A是数组名，ai（0≤i≤n-1）是数组A中序号为i的元素。一个二维数组可以看作是每个数据元素都是相同特性的一维数组的一维数组。以此类推。6.1.1数组的基本概念6.1数

组2/55二维数组的逻辑关系用二元组表示B=(D，R)R={r1，r2}r1={<1，2>，<2，3>，<3，4>，<5，6>，<6，7>，<7，8>，<9，10>，<10，11>，<11，12>} //同行关系r2={<1，5>，<5，9>，<2，6>，<6，10>，<3，7>，<7，11>，<4，8>，<8，12>} //同列关系3/55数组具有以下特点

（1）数组中各元素都具有相同特性。

（2）d（d≥1）维数组中的非边界元素具有d个前驱元素和d个后继元素。

（3）数组维数确定后，数据元素个数和元素之间的关系不再发生改变，特别适合于顺序存储。

（4）每个有意义的下标都存在一个与其相对应的数组元素值。4/55d维数组抽象数据类型ADTArray{

数据对象：

D={数组中所有元素}

数据关系：

R={r1，r2，…，rd}ri={元素之间第i维的线性关系|i=1，…，d}

基本运算：Value(A，i1，i2，…，id)：A是已存在的d维数组，其运算结果是返回A[i1，i2，…，id]值。Assign(A，e，i1，i2，…，id)：A是已存在的d维数组，其运算结果是

置A[i1，i2，…，id]=e。

…}5/556.1.2数组的存储结构1.一维数组一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中。其起始地址为第一个元素a0的地址即LOC(a0)。假设每个数据元素占用k个存储单元。则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出LOC(ai)=LOC(a0)+i×k

（1≤i<n）一维数组具有随机存取特性6/552.d维数组以m行n列的二维数组Am×n=(ai，j)为例讨论（二维数组也称为矩阵）。7/55按行优先存储ai,j前面有0～i-1共i行，每行n个元素，共有i×n个元素。在第i行中前面有a[i,0..j-1]，共j个元素。合起来，ai,j前面有i×n+j个元素。LOC(ai,j)=LOC(a0,0)+(i×n+j)×k

假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。对于元素ai，j：8/55按列优先存储ai,j前面有0～j-1共j列，每列m个元素，共有j×m个元素。在第j列中前面有a[0..i-1,j]，共i个元素。合起来，ai,j前面有j×m+i个元素。则：LOC(ai,j)=LOC(a0,0)+(j×m+i)×k

假设每个元素占k个存储单元，LOC(a0，0)表示a0，0元素的存储地址。对于元素ai，j：二维数组也具有随机存取特性，以此类推。9/55更一般地，数组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)]×k10/556.1.3Java中的数组1.一维数组Java声明一维数组的语法有两种，两种形式上没有区别，使用效果完全一样：

int[]a;

//第一种 inta[];

//第二种

与C/C++不同，Java中的数组是一种引用类型的变量，数组变量并不是数组本身，它只是指向堆内存中的数组对象，因此[]中无需指定数组元素的个数即数组长度。所以必须在先分配内存空间后才能访问数组中的元素。为数组分配内存空间的方式如下：

int[]a;

//定义一个int数组变量a

a=newint[3];

//为int数组变量a指定元素个数为3，此时分配内存空间

也可以这样写：

int[]a=newint[3];

//相当于在定义int数组变量的时候， //为其分配内存空间11/55Java数组初始化有两种方式，一种是静态初始化，即初始化时由程序员显式指定每个数组元素的初始值，由系统决定数组长度，另外一种是动态初始化，即初始化时程序员只指定数组长度，由系统为数组元素分配初始值。例如：int[]a=newint[]{1,2,3}; //静态初始化String[]b=newString[3]; //动态初始化b[0]="Hello";b[1]="World";b[2]="HelloWorld";12/55int[]c=newint[N];定义的一维数组c的内存空间如图所示，总共占用24+4N个字节。对象开销长度N填充字节………16字节4字节4字节头信息N个int值，占用4N个字节13/552.二维数组二维数组的声明、初始化和访问元素和一维数组相似，例如：int[][]a={{1,2},{2,3},{4,5}}; //静态初始化int[][]b=newint[2][3];b[0][0]=1; //动态初始化b[0][1]=2;//...b[1][2]=6;14/55

Java语言中把二维数组看作是一维数组的数组，数组空间不是连续分配的，所以不要求二维数组每一维的大小相同。例如：int[][]a=newint[2][];a[0]=newint[3];a[1]=newint[5];System.out.printf("数组a的大小:%d\n",a.length); //输出:2System.out.printf("a[0]的大小:%d\n",a[0].length); //输出:3System.out.printf("a[1]的大小:%d\n",a[1].length); //输出:515/55对象开销长度N填充字节…16字节4字节4字节头信息M个一维数组引用，占用8M个字节对象开销长度N填充字节………16字节4字节4字节头信息对象开销长度N填充字节………16字节4字节4字节头信息N个double值，占用8N个字节N个double值，占用8N个字节double[][]c=newdouble[M][N];c是一个M行N列的二维数组，在内存存储时，c的每个元素又是一个一维数组，存放的是对应一维数组的引用，这里每个对象引用地址为8个字节，总共占用24+8M+M(24+8N)=24+32M+8MN个字节。16/55Java数组的说明

（1）Java数组都是静态数组，一旦被声明其容量就固定了，不能改变。所以在声明数组时，一定要考虑数组的最大容量，防止容量不够的现象。

（2）如果希望在执行程序时动态改变容量，可以使用Java集合中的ArrayList或者Vector容器。17/55（3）由于Java中数组（非基本类型的一维数组或者二维及以上的数组）并不像C/C++数组占用一片连续空间，所以C/C++数组的一些优化操作并不适合Java数组。例如，在C/C++中定义二维数组：inta[500][1000];for(inti=0;i<500;i++) //程序段1for(intj=0;j<1000;j++) a[i][j]=i+j;

for(intj=0;j<1000;j++) //程序段2for(inti=0;i<500;i++) a[i][j]=i+j;程序段1的性能明显好于程序段2，这是因为C/C++数组按行优先存储，而程序段1的访问顺序恰好也是按行优先访问的。但在Java中性能的提升不明显，这是因为Java中二维数组的所有元素并非占用一片连续空间，需要寻址访问元素。18/553.Java中的数组类ArraysJava中提供了Arrays类可以方便地操作数组，它提供的所有方法都是静态的，实际上在Java中建立的各种数组都看成Arrays类的实例。Arrays类的主要方法（以int数据类型为例）

（1）static

intbinarySearch(int[]

a，int

key)：使用二分搜索法来搜索int型数组a，以获得指定的值。

（2）static

intbinarySearch(int[]

a，int

fromIndex，int

toIndex，int

key)：使用二分搜索法来搜索int数组a的[fromIndex，toIndex)范围，以获得指定的值。该范围从索引fromIndex（包括）一直到索引toIndex

（不包括）。

（3）static

booleanequals(int[]

a，int[]

a2)：如果两个指定的int型数组a和a2彼此相等，则返回true。

（4）static

voidfill(int[]

a，int

val)：将指定的int值分配给int型数组a的每个元素。

（5）static

voidsort(int[]

a)：对int型数组a按数字升序进行排序。19/55

（6）static

voidsort(int[]

a，int

fromIndex，int

toIndex)：对int型数组a的[fromIndex，toIndex)范围按数字升序进行排序。排序范围从索引fromIndex（包括）一直到索引toIndex

（不包括），如果fromIndex=toIndex，则排序范围为空。

（7）<E>voidsort(E[]

a，Comparator<?superE>

c)：根据指定比较器产生的顺序对对象数组a进行排序。

（8）<E>voidsort(E[]

a，intfromIndex，inttoIndex，Comparator<?superE>

c)：根据指定比较器产生的顺序对指定对象数组a从索引fromIndex（包括）一直到索引toIndex（不包括）范围内元素进行排序。

（9）static

StringtoString(int[]

a)：返回int数组a的内容的字符串表示形式。20/55

【例6.2】有一个整数数组为（6，2，1，9，5，7，4，3，8），采用Arrays类的sort()方法实现以下方式排序：

（1）全部元素递增排序。

（2）全部元素递减排序。

（3）将[2..6]范围的元素递增排序。21/55importjava.util.*;publicclassExam6_2{publicstaticvoidmain(String[]args){int[]a={6,2,1,9,5,7,4,3,8};System.out.print("增序排序:");

Arrays.sort(a);for(inti=0;i<a.length;i++) //输出:123456789System.out.print(a[i]+"");22/55System.out.print("\n减序排序:");//需要使用包装类型而不是 //基本类型Integer[]b={6,2,1,9,5,7,4,3,8};

Arrays.sort(b,newComparator<Integer>(){publicintcompare(Integero1,Integero2){returno2-o1; //返回值>0时进行交换}});for(Integerx:b) //输出:987654321System.out.print(x+"");System.out.print("\n部分排序:");int[]c={6,2,1,9,5,7,4,3,8}; //对数组的[2,6)区间进行排序

Arrays.sort(c,2,6);for(inti=0;i<c.length;i++) //输出:621579438System.out.print(c[i]+"");}}23/556.1.4数组的应用

【例6.4】有一个n阶二维整数数组a，设计一个算法求ak（k为大于1的整数），结果矩阵元素值取模111的结果。例如：24/55

如果求ak=a×…×a时做k-1次矩阵乘法运算，由于一次乘法运算的时间为O(n3)，所以这样做的算法时间复杂度为(k×n3)，当k较大时算法的性能低下。可以借鉴第5章例5.4的快速幂方法。doublepow1(doublex,intn){doubleans=1.0;doublebase=x;while(n!=0){if((n&1)==1)ans*=base;base*=base;n>>=1;}returnans;}求xn的快速幂算法求ak的矩阵快速幂算法int[][]pow(int[][]a,intk){ans置为单位矩阵;base=a;while(k!=0){if((k&1)==1)ans=mult(ans,base);base=mult(base,base);k>>=1;}returnans;}25/55publicstaticint[][]mult(int[][]a,int[][]b){//返回矩阵a和b相乘的矩阵intn=a.length;int[][]c=newint[n][n];for(inti=0;i<n;i++){for(intj=0;j<n;j++){for(intk=0;k<n;k++)c[i][j]+=(a[i][k]*b[k][j])%MOD;c[i][j]%=MOD;}}returnc;}26/55publicstaticint[][]pow(int[][]a,intk){//返回a^k的矩阵intn=a.length;int[][]ans=newint[n][n]; //建立ans矩阵for(inti=0;i<n;i++) //置ans为单位矩阵ans[i][i]=1;int[][]base=newint[n][n]; //建立base矩阵for(inti=0;i<n;i++) //置base=afor(intj=0;j<n;j++)base[i][j]=a[i][j];while(k!=0){if((k&1)==1) //遇到二进制位1ans=mult(ans,base);base=mult(base,base); //倍乘k>>=1; //右移一位}returnans;}上述算法的时间复杂度为(log2k×n3)。27/556.2特殊矩阵的压缩存储n阶方阵A[n][n]a0,0a0,1a0,n-1

a1,0a1,1a1,n-1

an-1,0an-1,1an-1,n-1

ai,j（i<j）上三角ai,j（i>j）下三角ai,i（0≤i≤n-1）主对角线28/551.对称矩阵的压缩存储若一个n阶方阵A的元素满足ai,j=aj,i（0≤i，j≤n-1），则称其为n阶对称矩阵。a0,0，a1,0，a1,1，，an-1,0，an-1,1，，an-1,n-1B=（b0，b1，b2，，，bs）下三角+主对角线n(n+1)/2个元素a0,0a0,1a0,n-1

a1,0a1,1a1,n-1

an-1,0an-1,1an-1,n-1

i≥jai,jbkk=?29/55k=当i≥j时（下三角+主对角线的元素）当i<j时（ai,j=aj,i）i(i+1)2+jj(j+1)2+iB=(a0,0,a1,0,a1,1,

,ai-1,0,

,ai-1,i-1，ai,0,

,ai,j-1,ai,j,

,an-1,n-1)1个元素2个元素i个元素j个元素共计i(i+1)/2+j个元素bk30/55n2个元素

n(n+1)/2个元素A[0..n-1,0..n-1]

B[0..n(n+1)/2-1]

a[i][j]

b[k]对于对称矩阵A，采用一维数组B存储，并提供A的所有运算。k=当i≥j时（下三角+主对角线的元素）当i<j时（ai,j=aj,i）i(i+1)2+jj(j+1)2+i31/552.三角矩阵的压缩存储a0,0a0,1a0,n-1

a1,1a1,n-1

an-1,n-1c

i≤j上三角矩阵32/55a0,0a0,1a0,n-1

a1,1a1,n-1

an-1,n-1c

对于上三角部分的元素ai,j第0行：存储n个元素第1行：存储n-1个元素…第i-1行：存储n-i个元素i(2n-i+1)/2个元素第i行有a[i,i..j-1]：j-i个元素k=当i≤j时当i>j时存放常量ci(2n-i+1)2+j-in(n+1)233/55存放一个常量ck=当i≥j时当i<j时i(i+1)2+jn(n+1)2a0,0a0,1a0,n-1

a1,0a1,1a1,n-1an-1,0an-1,1an-1,n-1

ci≥j下三角矩阵34/55

若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（i≤j）的下标i、j与k的对应关系是（）。A.i(i+1)/2+j B.i(i-1)/2+jC.j(j+1)/2+i

D.j(j-1)/2+i

a1,1a1,2a1,n

a1,0a2,2a2,n

an-1,0an-1,1an,n

i≤jc按行还是按列初始下标从0还是从1开始1～j-1列的元素个数：j(j-1)/2第j列aij之前的元素个数：i-1k=j(j-1)/2+i-1+1=j(j-1)/2+i示例35/553.对角矩阵的压缩存储

半带宽为b的对角矩阵

b条00……b条36/55

A

B

a[i][j]b[k]当b=1时称为三对角矩阵其压缩地址计算公式如下：

k=2i+j

00对角矩阵压缩存储37/556.3稀疏矩阵一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时，即s<<t时，称该矩阵为稀疏矩阵。

例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。定性的描述38/55稀疏矩阵和特殊矩阵的不同点：特殊矩阵的特殊元素（值相同元素、常量元素）分布有规律。稀疏矩阵的特殊元素（非0元素）分布没有规律。39/556.3.1稀疏矩阵的三元组表示通常按行优先顺序排列40/55classTupElem<E>{

//三元组元素类intr; //行号intc; //列号intd; //元素值publicTupElem(intr1,intc1,intd1){ //构造方法r=r1;c=c1;d=d1;}}三元组表示中每个元素的类定义如下：41/55publicclassTupClass { //三元组表示类introws; //行数intcols; //列数intnums; //非零元素个数ArrayList<TupElem>data; //稀疏矩阵对应的三元组顺序表publicTupClass(){ //构造方法data=newArrayList<TupElem>();nums=0;}

publicvoidCreateTup(int[][]A,intm,intn)

//创建三元组表示publicbooleanSetvalue(inti,intj,intx)

//三元组元素赋值A[i][j]=xpublicintGetValue(inti,intj)

//执行x=A[i][j]publicvoidDispTup() //输出三元组表示}设计稀疏矩阵三元组存储结构类TupClass如下：42/55（1）从一个稀疏矩阵创建其三元组表示publicvoidCreateTup(int[][]A,intm,intn){//由二维数组A创建三元组表示datarows=m;cols=n;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(A[i][j]!=0){ //只存储非零元素data.add(newTupElem(i,j,A[i][j]));nums++;}}}}43/55（2）三元组元素赋值publicbooleanSetvalue(inti,intj,intx){intk=0;if(i<0||i>=rows||j<0||j>=cols)returnfalse; //下标错误时返回falsewhile(k<nums&&i>data.get(k).r)k++; //找到第i行while(k<nums&&i==data.get(k).r&&j>data.get(k).c)k++; //在第i行中找到第j列if(data.get(k).r==i&&data.get(k).c==j)//若存在该非0元素data.set(k,newTupElem(i,j,x)); //修改k下标元素值else { //不存在该元素时插入一个元素data.add(k,newTupElem(i,j,x)); //在下标k位置插入新元素nums++;}returntrue; //赋值成功时返回true}执行A[i][j]=x。44/55（3）将指定位置的元素值赋给变量publicintGetValue(inti,intj){ //执行x=A[i][j]intk=0;if(i<0||i>=rows||j<0||j>=cols)return0; //下标错误时返回0while(k<nums&&data.get(k).r<i)k++; //找到第i行while(k<nums&&data.get(k).r==i&&data.get(k).c<j)k++; //在第i行中找到第j列if(data.get(k).r==i&&data.get(k).c==j)//找到该非0元素returndata.get(k).d; //返回非0元素值return0; //没有找到返回0}执行x=A[i][j]。45/55（4）输出三元组publicvoidDispTup() { //输出三元组表示if(nums<=0)return; //没有非零元素时返回System.out.printf("行数=%d,列数=%d,非0元素个数=%d\n", rows,cols,nums);for(inti=0;i<nums;i++)System.out.printf("%5d%5d%5d\n", data.get(i).r,data.get(i).c,data.get(i).d);}46/55每个非零元素对应一个结点。0012340321236.3.2稀疏矩阵的十字链表表示47/55每行的所有结点链起来构成一个带行头结点的循环单链表。以h[i]（0≤i≤m-1）作为第i行的头结点。0012340321233个行头结点48/550012340321233个行头结点4个列头结点每列的所有结点链起来构成一个带列头结点的循环单链表。以h[i]（0≤i≤m-1）作为第i列的头结点。49/55001234032123行、列头结点可以共享第1行、第1列的头结点第2行、第2列的头结点第3行、第3列的头结点第4行、第4列的头结点行、列头结点个数=MAX(m，n)50/55001234032123增加一个总头结点，并把所有行、列头结点链起来构成一个循环单链表34h总的头结点个数=MAX(m,n)+151/55

(a)非0元素结点结构(b)头结点结构ijvaluedownrightijlinkdownright为了统一，设计结点类型如下：用标识tag区分52/55classCNode{ //十字链表结点类inti; //行号intj; //列号CNoderight,down; //向右和向下的指针booleantag; //true:头结点，false:元素结点intvalue; //存放非零元素值CNodelink; //头结点指针publicCNode(inti1,intj1,booleantag1){i=i1;j=j1;tag=tag1;right=down=link=null;}}有关算法不做介绍。十字链表元素结点和头结点合起来声明的结点类型如下：53/551011张三1013李四…1班1028王五1029刘六…2班1082陈功1085许斌…8班∧15届∧十字链表的启示：设计存储某年级所有学生的存储结构。…h通过h来唯一标识学生存储结构。示例54/5555/55第7章树和二叉树7.1树7.2二叉树CONTENTS提纲7.3二叉树先序、中序和后序遍历7.4二叉树的层次遍历7.5二叉树的构造7.6线索二叉树7.8二叉树与树、森林之间的转换7.7哈夫曼树7.9树算法设计和并查集56/36树是由n（n≥0）个结点组成的有限集合（记为T）。如果n=0，它是一棵空树，这是树的特例。如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点（root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。7.1.1树的定义7.1树57/36树是一种非线性数据结构，具有以下特点：每一结点可以有零个或多个后继结点，但有且只有一个前驱结点（根结点除外）。数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。58/36ADTTree{

数据对象：

D={ai

|0≤i≤n-1，n≥0，ai为E类型}

数据关系：

R={r} r={<ai，aj>|ai，aj∈D，0≤i，j≤n-1，其中每个结点最多只有一个

前驱结点、可以有零个或多个后继结点，有且仅有一个结点即根

结点没有前驱结点}

基本运算： boolCreateTree()：由树的逻辑结构表示建立其存储结构。 StringtoString()：返回由树转换的括号表示串。 EGetParent(inti)：求编号为i的结点的双亲结点值。

…}抽象数据类型树的描述59/367.1.2树的逻辑结构表示方法树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。ABCDEFHG60/36文氏图表示法。使用集合以及集合的包含关系描述树结构。ABCDEFHG61/36凹入表示法。使用线段的伸缩关系描述树结构。ABCDEFHG62/36括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。A(B,C(E(H),F),D(G))ABCDEFHG根(子树1，子树2，…，子树m）63/367.1.3树的基本术语度为3度为1结点的度。树中每个结点具有的子树数或者后继结点数称为该结点的度。ABCDEFHG64/36树的度。树中所有结点的度的最大值称之为树的度。树的度为3ABCDEFHG65/36分支结点。度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。ABCDEFHGA、C、D、E为分支结点66/36叶子结点（或叶结点）。度为零的结点称为叶子结点或终端结点。ABCDEFHGB、H、F、G为叶子结点67/36孩子结点。一个结点的后继称之为该结点的孩子结点。结点A的孩子结点为B、C和DABCDEFHG68/36双亲结点（或父亲结点）。一个结点称为其后继结点的双亲结点。结点E和F的双亲结点均为CABCDEFHG69/36子孙结点。一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。ABCDEFHG结点C结点的子孙结点为E、F和H70/36祖先结点。从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）。ABCDEFHG结点F的祖先结点为A、C71/36兄弟结点。具有同一双亲的结点互相称之为兄弟结点。结点E和F是兄弟结点ABCDEFHG72/36结点层次。树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次。1234ABCDEFHG73/36树的高度。树中结点的最大层次称为树的高度或深度。1234ABCDEFHG高度是474/36森林。零棵或多棵互不相交的树的集合称为森林。ABCDEFHG4棵树构成的森林75/367.1.4树的性质性质1：

树中的结点数等于所有结点的度数加1。度之和=分支数分支数=n-1所以，n=度之和+1ABCDEFHGABCDEFHG76/36性质2：度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。数学归纳法证明

当一棵m次树的第i层有mi-1个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层，所有层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。推广77/36性质3：

高度为h的m次树至多有个结点。由性质2推出78/36性质4：具有n个结点的m次树的最小高度为

logm(n(m-1)+1)

。

证明：设具有n个结点的m次树的最小高度为h，若在该树中前h-1层都是满的，即每一层的结点数都等于mi-1个（1≤i≤h-1），第h层（即最后一层）的结点数可能满，也可能不满，则该树具有最小的高度。其高度h可计算如下：h层全满高度为h，结点个数最多的情况h-1层满高度为h，结点个数最少的情况+179/36根据树的性质3可得：<

n≤乘(m-1)后得：

mh-1<n(m-1)+1≤

mh以m为底取对数后得：

h-1<logm(n(m-1)+1)≤

h即 logm(n(m-1)+1)≤

h<logm(n(m-1)+1)+1因h只能取整数，所以h=

logm(n(m-1)+1)

，结论得证。80/36

【例7.1】若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？

设该三次树中总结点个数、度为0的结点个数、度为1的结点个数、度为2的结点个数和度为3的结点个数分别为n、n0、n1、n2和n3。

显然，每个度为i的结点在所有结点的度数之和中贡献i个度。依题意有：n1=2，n2=1，n3=2。由树的性质1可知

n=所有结点的度数之和+1

=0×n0+1×n1+2×n2+3×n3+1=1×2+2×1+3×2+1=11又因为n=n0+n1+n2+n3即：n0=n-n1-n2-n3=11-2-1-2=6所以该三次树中总的结点个数和度为0的结点个数分别是11和6。81/367.1.5树的基本运算树的运算主要分为三大类：查找满足某种特定关系的结点，如寻找当前结点的双亲结点等；插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；遍历树中每个结点。82/36

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。

有以下3种遍历方法：

先根遍历后根遍历层次遍历1.树的遍历83/36先根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。层次遍历:若树不空，则自上而下自左至右访问树中每个结点。先根和后根遍历算法都是递归的。注意84/36ABCDEFGHJIK先根遍历的顶点访问次序：ABEFCDGHIJK后根遍历的顶点访问次序：EFBCIJKHGDA层次遍历的顶点访问次序：ABCDEFGHIJK85/367.1.6树的存储结构1.双亲存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。ABCDEFHG位置dataparent0A-11B02C03D04E25F26G37H486/36classPTree<E> { //双亲存储结构结点类Edata; //存放结点的值intparent; //存放双亲的位置}PTree<E>[]t; //双亲存储结构t双亲存储结构中结点类PTree利用了每个结点（根结点除外）只有唯一双亲的性质。这种存储结构中，求某个结点的双亲结点十分容易，但求某个结点的孩子结点时需要遍历整个结构。优缺点87/362.孩子链存储结构孩子链存储结构可按树的度（即树中所有结点度的最大值）设计结点的孩子结点指针域个数。ABCFDEGA∧BC∧∧∧D∧∧∧E∧∧G∧∧∧F∧∧∧88/36孩子链存储结构的结点类TSonNodeclassTSonNode<E>{

//孩子链存储结构结点类Edata; //结点的值TSonNode<E>[]sons; //指向孩子结点}孩子链存储结构的优点是查找某结点的孩子结点十分方便。缺点是查找某结点的双亲结点比较费时。当树的度较大时，存在较多的空指针域，可以证明含有n个结点的m次树采用孩子链存储结构时有mn-n+1个空指针域。优缺点89/363.孩子兄弟链存储结构

孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个指向该结点的第一个孩子结点的指针域，一个指向该结点的下一个兄弟结点指针域。ABCFDEGA∧BD∧G∧∧C∧∧EF∧∧90/36兄弟链存储结构中结点类TSBNode定义如下：classtTSBNode<E>{

//孩子兄弟链存储结构中结点类Edata; //结点的值TSBNode<E>hp; //指向兄弟TSBNode<E>vp; //指向孩子结点}孩子兄弟链存储结构的最大优点是可以方便地实现树和二叉树的相互转换。缺点和孩子链存储结构的缺点一样：就是从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。优缺点91/36二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树中许多概念与树中的概念相同。在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结点个数，n1表示单分支结点个数，n2表示双分支结点个数。7.2.1二叉树的概念7.2二叉树1.二叉树的定义92/35度为2的树至少有3个结点，而二叉树的结点数可以为0。度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。提示二叉树与度为2的树是不同的。93/35归纳起来，二叉树的5种形态：Ø(a)空二叉树(b)只有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树非空的二叉树94/35ADTBTree{

数据对象： D={ai|1≤i≤n，n≥0，ai为E类型}//为了简单，假设E为char

数据关系： R={r} r={<ai，aj>|ai，aj∈D，1≤i，j≤n，当n=0时，称为空二叉树；

否则其中有一个根结点，其他结点构成根结点的互不相交的左、右子

树，该左、右两棵子树也是二叉树}

基本运算： voidCreateBTree(stringstr)：由二叉树括号表示串建立其存储结构。 StringtoString()：返回由二叉树树转换的括号表示串。 BTNodeFindNode(x)：在二叉树中查找值为x的结点。 intHeight()：求二叉树的高度。

…}2.二叉树抽象数据类型的描述95/353.满二叉树和完全二叉树在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次序进行。满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h且有2h-1个结点的二叉树称为满二叉树。ABDHIEJKCFLMGNO12489510113612137141596/35满二叉树的特点如下：叶子结点都在最下一层。只有度为0和度为2的结点。含n个结点的满二叉树的高度为log2(n+1)，叶子结点个数为

n/2

+1，度为2的结点个数为

n/2

。ABDHIEJKCFLMGNO124895101136121371415n=15h=log2(n+1)=497/35若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二叉树相同，图中每个结点外边的数字为对该结点的编号。ABDHIEJKCFG124895101136798/35完全二叉树的特点如下：叶子结点只可能出现在最下面两层中。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子；按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。ABDHIEJKCFG124895101136799/357.2.2二叉树性质性质1

非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。总结点数n=n0+n1+n2。一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。总的度数=总分支数=n-1。则n1+2n2=n0+n1+n2-1，求出n0=n2+1。证明：在二叉树中计算结点时常用的关系式有：①所有结点的度之和=n-1②所有结点的度之和＝n1＋2n2

③n=n0+n1+n2。归纳100/35性质2

非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。

由树的性质2可推出。性质3

高度为h的二叉树至多有2h-1个结点（h≥1）。

由树的性质3可推出。101/35性质4对完全二叉树中层序编号为i的结点（1≤i≤n，n≥1）有：

（1）若i≤

n/2

，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。

（2）若n为奇数，则n1=0，这样每个分支结点都是双分支结点；若n为偶数，则n1=1，只有一个单分支结点，该单分支结点是编号最大的分支结点（编号为

n/2

）。

（3）若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为2i+1。

（4）若编号为i的结点有双亲结点，其双亲结点的编号为

i/2

。i/2i2i2i+1102/35

性质5

具有n个（n＞0）结点的完全二叉树的高度为

log2(n+1)

或

log2n

+1。

由完全二叉树的定义和树的性质3可推出。一棵完全二叉树中，由结点总数n可以确定其树形。n1只能是0或1，当n为偶数时，n1=1，当n为奇数时，n1=0。层序编号为i的结点层次恰好为

log2(i+1)

或者

log2i

+1。归纳103/35

【例7.2】一棵含有882个结点的二叉树中有365个叶子结点，求度为1的结点个数和度为2的结点个数。这里n=882，n0=365。由二叉树的性质1可知n2=n0-1=364。n=n0+n1+n2，即n1=n-n0-n2=882-365-364=153。所以该二叉树中度为1的结点和度为2的结点个数分别是153和364。104/35【例7.5】一棵完全二叉树中有501个叶子结点，则至少有多少个结点。该二叉树中有，n0=501。由二叉树性质1可知n0=n2+1，所以n2=n0-1=500。n=n0+n1+n2=1001+n1，由于完全二叉树中n1=0或n1=1，则n1=0时结点个数最少，此时n=1001，即至少有1001个结点。105/357.2.3二叉树存储结构1.二叉树的顺序存储结构顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树中的结点。由二叉树的性质4可知，对于完全二叉树（或满二叉树），树中结点层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。106/35一棵完全二叉树的顺序存储结构1234567891011121314…ABCDEFGHIJK####位置sbABDHIEJKCFG1248951011367107/35ABDEGHCFKABDEGHCFK1248951011361271413增添空结点补齐为一棵完全二叉树并对所有结点进行编号一般的二叉树的顺序存储结构设计：108/351234567891011121314…ABCDE#F##GH##K#位置sb仅保留实际存在的结点值，其他为空ABDEGHCFK1248951011361271413109/35

二叉树顺序存储结构采用这样的数组存放（假设每个结点值为单个字符）：

Stringsb; //二叉树的顺序存储结构用sb字符串存储

当二叉树中某结点为空结点或无效结点（不存在该编号的结点）时，对应位置的值用特殊值（如'#'）表示。110/35完全二叉树或满二叉树采用顺序存储结构比较合适如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。h=4MazSize=24-1=15空间利用率=4/15=27%优缺点111/352.二叉树的链式存储结构ABCEFDG二叉链存储结构AB∧C∧D∧E∧∧G∧∧F∧b112/35对应Java语言的二叉链结点类BTNode<E>classBTNode<E>{

//二叉链中结点类Edata; //存放数据元素BTNodelchild; //指向左孩子结点BTNoderchild; //指向右孩子结点publicBTNode(){

//默认构造方法lchild=rchild=null;}publicBTNode(Ed){

//重载构造方法data=d;lchild=rchild=null;}}113/357.2.4二叉树的递归算法设计对于二叉树b，设f(b)是求解的“大问题”。f(b->lchild)和f(b->rchild)为“小问题”。假设f(b->lchild)和f(b->rchild)是可求的，在此基础上得出f(b)和f(b->lchild)、f(b->rchild)之间的关系，从而得到递归体。再考虑b=NULL或只有一个结点的特殊情况，从而得到递归出口。一般地，二叉树的递归结构如下：bf(b)b->lchildf(b->lchild)b->rchildf(b->rchild)114/357.2.5二叉树的基本运算及其实现1.二叉树类设计publicclassBTreeClass{

//二叉树类BTNode<Character>b; //根结点Stringbstr; //二叉树的括号表示串publicBTreeClass(){ //构造方法b=null;}//二叉树基本运算算法}

为了简单，本节讨论的二叉树中所有结点值为单个字符。逻辑结构采用括号表示串，存储结构采用二叉链。115/352.二叉树的基本运算算法实现（1）创建二叉树CreateBTree(str)str逻辑结构b存储结构正确的括号表示串（每个结点值为单个字符）116/35用ch扫描str，其中只有4类字符，各类字符的处理方式如下：若ch='('：表示前面刚创建的p结点存在着孩子结点，需将其进栈。然后开始处理该结点的左孩子，因此置flag=true，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点。若ch=')'：表示以栈顶结点为根结点的子树创建完毕，将其退栈。若ch=','：表示开始处理栈顶结点的右孩子结点，置flag=false。其他情况：只能是单个字符，表示要创建一个新结点p，根据flag值建立p结点与栈顶结点之间的联系，当flag=true时，表示p结点作为栈顶结点的左孩子结点，当flag=false时，表示p结点作为栈顶结点的右孩子结点。117/35publicvoidCreateBTree(Stringstr){

Stack<BTNode>st=newStack<BTNode>();

//建立一个栈stBTNode<Character>p=null;booleanflag=true;charch;inti=0;由括号表示层str创建以b为根结点的二叉链存储结构118/35while(i<str.length()){ //循环扫描str中每个字符ch=str.charAt(i);switch(ch){ case'(': st.push(p); //刚刚新建的结点有孩子,将其进栈flag=true;break; case')':st.pop(); //栈顶结点的子树处理完，出栈break; case',':flag=false; //开始处理栈顶结点的右孩子break;119/35default:p=newBTNode<Character>(ch); //用ch值新建一个结点if(b==null)b=p; //若尚未建立根结点,p作为根结点else{ //已建立二叉树根结点if(flag){ //新结点p作为栈顶结点的左孩子if(!st.empty())st.peek().lchild=p;}else{ //新结点p作为栈顶结点的右孩子if(!st.empty())st.peek().rchild=p;}}break;}i++; //继续遍历}}120/35str="A(B(D(，G))，C(E，F))"AB∧C∧D∧E∧∧G∧∧F∧b121/35（2）返回二叉链的括号表示串toString()publicStringtoString(){ //返回二叉链的括号表示串bstr="";

toString1(b);returnbstr;}privatevoidtoString1(BTNode<Character>t){//被toString方法调用if(t!=null){bstr+=t.data; //输出根结点值if(t.lchild!=null||t.rchild!=null){bstr+="("; //有孩子结点时输出"("

toString1(t.lchild); //递归输出左子树if(t.rchild!=null)bstr+=","; //有右孩子结点时输出","

toString1(t.rchild); //递归输出右子树bstr+=")"; //输出")"}}}122/35（3）查找值为x的结点FindNode(x)设f(t，x)在以t为根结点的二叉树中查找值为x的结点，找到后返回其地址，否则返回null。f(t，x)=null 若t=nullf(t，x)=t 若t.data=xf(t，x)=p

若在左子树中找到了，即

p=f(t.lchild，x)且p!=nullf(t，x)=f(t.rchild，x)

其他情况123/35publicBTNode<Character>FindNode(charx){

//查找值为x的结点算法retur