for（intj=0;j<[i].length;j++）
[j][i]=[i][j];
returntrans;
}
第2章
树和二叉树
【习2.1】画出3个结点的各种形态的树和二叉树。
3个结点的树有2种形态，3个结点的二叉树有5种形态，如图所示。
图2.23个结点树和二叉树的形态
【习2.1】找出分别满足下面条件的所有二叉树。
1先根遍历序列和中根遍历序列相同：
右单支二叉树，如图（a）所示。
2中根遍历序列和后根遍历序列相同：
左单支二叉树，如图（b）所示。
3先根遍历序列和后根遍历序列相同：
空树，只有一个根结点的二叉树。
图2.3单支二叉树
【习2.1】输出叶子结点。
在BinaryTree类中增加以下方法。
publicvoidleaf（）quals（i））））
returnfalse;
returntrue;
}
returnfalse;
}
【习2.2】实验单链表的全部替换操作。
在SinglyLinkedList单链表类中，增加替换操作方法如下。
publicbooleanreplace（Objectobj,Eelement）//详见实验
publicbooleanreplaceAll（Objectobj,Eelement）//将所有元素值为obj的结点值替换为element
{//若替换成功返回true，否则返回false
booleandone=false;
if（obj!
=null&&element!
=null）
{
Nodep=;
while（p!
=null）
{
if）
{
=element;
done=true;
}
p=;
}
}
returndone;
}
【习2.3】实验单链表的全部删除操作。
在SinglyLinkedList单链表类中，增加删除操作方法如下。
publicbooleanremoveAll（Objectobj）//将所有元素值为obj的结点删除
{
if==null||obj==null）
returnfalse;
booleandone=false;
while!
=null&&{
=//头删除
done=true;
}
Nodefront=,p=;
while（p!
=null）
if）
{
=;//删除p结点
p=;
done=true;
}
else
{
front=p;
p=;
}
returndone;
}
【习2.4】折半查找的递归算法。
publicstaticintbinarySearch（int[]table,intvalue）//折半查找算法，数组元素已按升序排列
{//若查找成功返回元素下标，否则返回-1
if（table!
=null）
returnbinarySearch（table,value,0,;
return-1;
}
privatestaticintbinarySearch（int[]table,intvalue,intlow,inthigh）//折半查找，递归算法
{//low、high指定查找范围的下界和上界
if（low<=high）//边界有效
{
intmid=（low+high）/2;//中间位置，当前比较元素位置
""）;
if（table[mid]==value）
returnmid;//查找成功
else
if（table[mid]>value）//给定值小
returnbinarySearch（table,value,low,mid-1）;//查找范围缩小到前半段
else
returnbinarySearch（table,value,mid+1,high）;//查找范围缩小到后半段
}
return-1;
}
【习2.5】二叉排序树查找的递归算法。
将二叉排序树类BinarySortTree中的search（value）方法替换为以下方法。
publicBinaryNodesearchNode（Evalue）//查找值为value的结点
{//若查找成功返回结点，否则返回null
if（value==null||!
（valueinstanceofComparable））
returnnull;
returnsearchNode（value,root）;
}
privateBinaryNodesearchNode（Evalue,BinaryNodep）//查找值为value的结点，递归算法
{
if（p!
=null）
{
Comparablecmpobj=（Comparable）value;
if==0）//若两个对象相等，查找成功
returnp;
""）;
if<0）
returnsearchNode（value,;//在左子树中查找
else
returnsearchNode（value,;//在右子树中查找
}
returnnull;
}
【习2.6】二叉排序树插入结点的非递归算法。
将二叉排序树类BinarySortTree中的insert（value）方法替换为以下方法。
publicbooleaninsertNode（Evalue）//插入结点，非递归算法
{
if（value==null||!
（valueinstanceofComparable））
returnfalse;
if（root==null）
root=newBinaryNode（value）;//建立根结点
else
{
BinaryNodep=,parent=null;
Comparablecmpobj=（Comparable）value;
while（p!
=null）
{
parent=p;
if==0）
returnfalse;//不插入重复关键字
if<0）
p=;
else
p=;
}
p=newBinaryNode（value）;//建立叶子结点p
if<0）
=p;//p作为parent的左孩子
else
=p;//p作为parent的右孩子
}
returntrue;
}
【习2.7】判断一棵二叉树是否为二叉排序树。
将二叉树类BinaryTree中增加以下方法。
publicbooleanisSorted（）//判断一棵二叉树是否为二叉排序树
{
returnisSorted;
}
publicbooleanisSorted（BinaryNodep）
{
booleanyes=true;
if（p!
=null）
{
if（!
instanceofComparable））
returnfalse;
Comparablecmpobj=（Comparable）;
if（==null||!
=null&&&&
==null||!
=null&&{
yes=isSorted;
if（yes）
yes=isSorted;
}
else
yes=false;
}
returnyes;
}
第3章
排序
【习3.1】判断一个数据序列是否为最小堆序列。
publicstaticbooleanisMinHeap（int[]table）//判断一个数据序列是否为最小堆
{
if（table==null）
returnfalse;
inti=2-1;//最深一棵子树的根结点
while（i>=0）
{
intj=2*i+1;//左孩子
if（j<
if（table[i]>table[j]）
returnfalse;
else
if（j+1<&&table[i]>table[j+1]）//右孩子
returnfalse;
i--;
}
returntrue;
}
【习3.2】归并两条排序的单链表。
使用一趟归并排序算法，将两条排序的单链表合并成一条排序的单链表。
算法描述如图所示。
图3.2归并两条排序的单链表
在带头结点的单链表类SortedHSLinkedList中，增加merge（）方法如下：
publicvoidmerge（SortedHSLinkedListlist）//归并两条排序的单链表
{
if（list==null||==null）
return;
if==null）
{
=;
return;
}
Nodefront=,p=;//front是p的前驱，p指向this单链表的第一个结点
Nodeq=//q指向list单链表的第一个结点
while（p!
=null&&q!
=null）
{
if（（（Comparable）pareTo（（Comparable）<0）//比较两个链表当前结点值
{
front=p;
p=;
}
else
{//将q结点插入到front结点之后
=q;
q=;
front=;
=p;
}
}
if（q!
=null）//list链表中剩余结点并入当前链表尾
{
=q;
while!
=null）
q=;
=q;
}
+=;
}
【习3.1】说明二叉排序树与堆的差别。
二叉排序树与堆是不同的。
二叉排序树是二叉树结构，通常采用链式存储结构，父母结点的关键字值比左孩子结点值大，而比右孩子结点值小。
而堆序列是顺序存储结构的线性表，只看成是完全二叉树结点的层次序列；堆序列的性质强调对应完全二叉树中父母结点值比子女结点值小，而不考虑左右孩子值间的大小。
升级会员 