《數(shù)據(jù)結(jié)構(gòu)Java版》習(xí)題解答

-PAGE2-..TOC\h\z\t"標(biāo)題1,1,例題,4"第0章Java程序設(shè)計基礎(chǔ)1[習(xí)0.1]實驗0.1哥德巴赫猜想。1[習(xí)0.2]實驗0.2楊輝三角形。1[習(xí)0.3]實驗0.3金額的中文大寫形式。1[習(xí)0.4]實驗0.4下標(biāo)和相等的數(shù)字方陣。1[習(xí)0.5]實驗0.5找出一個二維數(shù)組的鞍點2[習(xí)0.6]實驗0.6復(fù)數(shù)類。2[習(xí)0.7]實驗0.8圖形接口與實現(xiàn)圖形接口的類2第1章緒論3[習(xí)1.1]實驗1.1判斷數(shù)組元素是否已按升序排序。3[習(xí)1.2]實驗1.3用遞歸算法求兩個整數(shù)的最大公因數(shù)。3第2章線性表5[習(xí)2.1]習(xí)2-5圖2.19的數(shù)據(jù)結(jié)構(gòu)聲明。5[習(xí)2.2]習(xí)2-6如果在遍歷單鏈表時,將p=p.next語句寫成p.next=p,結(jié)果會怎樣？5[習(xí)2.3]實驗2.2由指定數(shù)組中的多個對象構(gòu)造單鏈表。5[習(xí)2.4]實驗2.2單鏈表的查找、包含、刪除操作詳見。5[習(xí)2.5]實驗2.2單鏈表的替換操作。6[習(xí)2.6]實驗2.2首尾相接地連接兩條單鏈表。6[習(xí)2.7]實驗2.2復(fù)制單鏈表。6[習(xí)2.8]實驗2.2單鏈表構(gòu)造、復(fù)制、比較等操作的遞歸方法。7[習(xí)2.9]建立按升序排序的單鏈表〔不帶頭結(jié)點。8[習(xí)2.10]實驗2.6帶頭結(jié)點的循環(huán)雙鏈表類,實現(xiàn)線性表接口。10[習(xí)2.11]實驗2.5建立按升序排序的循環(huán)雙鏈表。14第3章棧和隊列17[習(xí)3.1]習(xí)3-5棧和隊列有何異同？17[習(xí)3.2]能否將棧聲明為繼承線性表,入棧方法是add<0,e>,出棧方法是remove<0>？為什么？17[習(xí)3.3]能否用一個線性表作為棧的成員變量,入棧方法是add<0,e>,出棧方法是remove<0>？為什么？17[習(xí)3.4]能否將隊列聲明為繼承線性表,入隊方法是add<e>,出隊方法是remove<0>？為什么？17第4章串18[習(xí)4.1]實驗4.6找出兩個字符串中所有共同的字符。18[習(xí)4.2]習(xí)4-9<1>已知目標(biāo)串為"abbaba"、模式串為"aba",畫出其KMP算法的匹配過程,并給出比較次數(shù)。18[習(xí)4.3]習(xí)4-9<2>已知target="ababaab"、pattern="aab",求模式串的next數(shù)組,畫出其KMP算法的匹配過程,并給出比較次數(shù)。18第5章數(shù)組和廣義表20[習(xí)5.1]求一個矩陣的轉(zhuǎn)置矩陣。20第6章樹和二叉樹21[習(xí)6.1]畫出3個結(jié)點的各種形態(tài)的樹和二叉樹。21[習(xí)6.2]找出分別滿足下面條件的所有二叉樹。21[習(xí)6.3]輸出葉子結(jié)點。21[習(xí)6.4]求一棵二叉樹的葉子結(jié)點個數(shù)。22[習(xí)6.5]判斷兩棵二叉樹是否相等。22[習(xí)6.6]復(fù)制一棵二叉樹。23[習(xí)6.7]二叉樹的替換操作。23[習(xí)6.8]后根次序遍歷中序線索二叉樹。24第7章圖25第8章查找26[習(xí)8.1]實驗8.1順序表的查找、刪除、替換、比較操作。26[習(xí)8.2]實驗8.2單鏈表的全部替換操作。28[習(xí)8.3]實驗8.2單鏈表的全部刪除操作。28[習(xí)8.4]折半查找的遞歸算法。29[習(xí)8.5]二叉排序樹查找的遞歸算法。29[習(xí)8.6]二叉排序樹插入結(jié)點的非遞歸算法。30[習(xí)8.7]判斷一棵二叉樹是否為二叉排序樹。31第9章排序32[習(xí)9.1]判斷一個數(shù)據(jù)序列是否為最小堆序列。32[習(xí)9.2]歸并兩條排序的單鏈表。32[習(xí)9.3]說明二叉排序樹與堆的差別。34TOC\h\z\t"圖題,4"圖0.1下標(biāo)和相等的數(shù)字方陣算法描述1圖2.1p.next=p將改變結(jié)點間的鏈接關(guān)系5圖4.1目標(biāo)串"abbaba"和模式串"aba"的KMP算法模式匹配過程18圖4.2目標(biāo)串"ababaab"和模式串"aab"的KMP算法模式匹配過程19圖6.13個結(jié)點樹和二叉樹的形態(tài)21圖6.2單支二叉樹21圖9.2歸并兩條排序的單鏈表33TOC\h\z\t"表題,4"表4.1模式串"aab"的next數(shù)組19-PAGE2-..Java程序設(shè)計基礎(chǔ)實驗0.1哥德巴赫猜想。實驗0.2楊輝三角形。實驗0.3金額的中文大寫形式。實驗0.4下標(biāo)和相等的數(shù)字方陣。輸出下列方陣〔當(dāng)n=4時。1 2 6 7或 1 3 4 103 5 8 13 2 5 9 114 9 12 14 6 8 12 1510 11 15 16 7 13 14 16采用二維數(shù)組實現(xiàn)。二維數(shù)組中,每一條斜線上各元素下標(biāo)和相等,如圖0.1所示。下標(biāo)和相等的數(shù)字方陣算法描述程序如下。publicclassUpmat{publicstaticvoidmain<Stringargs[]>{intn=4; //階數(shù)int[][]mat=newint[n][n];intk=1; //k是自然數(shù),遞增變化booleanup=true; //方向向上for<intsum=0;sum<n;sum++> //左上三角,sum表示行列的下標(biāo)和{if<up>for<inti=sum;i>=0;i-->mat[i][sum-i]=k++; //k先賦值后自加elsefor<inti=0;i<=sum;i++>mat[i][sum-i]=k++;up=!up; //方向求反}for<intsum=n;sum<2*n-1;sum++> //右下三角{if<up>for<intj=sum-n+1;j<n;j++>mat[sum-j][j]=k++;elsefor<intj=n-1;j>sum-n;j-->mat[sum-j][j]=k++;up=!up;}for<inti=0;i<mat.length;i++> //輸出二維數(shù)組元素{for<intj=0;j<mat[i].length;j++> //i、j是行、列下標(biāo)System.out.print<""+mat[i][j]>;System.out.println<>;}}}實驗0.5找出一個二維數(shù)組的鞍點實驗0.6復(fù)數(shù)類。實驗0.8圖形接口與實現(xiàn)圖形接口的類緒論實驗1.1判斷數(shù)組元素是否已按升序排序。程序見例1.4的SortedArray.java。publicstaticbooleanisSorted<int[]table>//判斷整數(shù)數(shù)組是否已按升序排序{//若已排序返回true,否則返回falseif<table==null>returnfalse;for<inti=0;i<table.length-1;i++>if<table[i]>table[i+1]>returnfalse;returntrue;}publicstaticbooleanisSorted<Comparable[]table> //判斷對象數(shù)組是否已按升序排序{ //若已排序返回true,否則返回falseif<table==null>returnfalse;for<inti=0;i<table.length-1;i++>if<table[i].compareTo<table[i+1]>>0>returnfalse;returntrue;}實驗1.3用遞歸算法求兩個整數(shù)的最大公因數(shù)。publicclassGcd{publicstaticintgcd<inta,intb> //返回a,b的最大公因數(shù),遞歸方法{if<b==0>returna;if<a<0>returngcd<-a,b>;if<b<0>returngcd<a,-b>;returngcd<b,a%b>;}publicstaticvoidmain<Stringargs[]>{inta=12,b=18,c=24;System.out.println<"gcd<"+a+","+b+","+c+">="+gcd<gcd<a,b>,c>>;//獲得3個整數(shù)最大公因數(shù)}}線性表習(xí)2-5圖2.19的數(shù)據(jù)結(jié)構(gòu)聲明。table數(shù)組元素為單鏈表,聲明如下：SinglyLinkedList<E>table[]習(xí)2-6如果在遍歷單鏈表時,將p=p.next語句寫成p.next=p,結(jié)果會怎樣？使p.next指向p結(jié)點自己,改變了結(jié)點間的鏈接關(guān)系,丟失后繼結(jié)點,如圖2.1所示。p.next=p將改變結(jié)點間的鏈接關(guān)系實驗2.2由指定數(shù)組中的多個對象構(gòu)造單鏈表。在SinglyLinkedList單鏈表類中,增加構(gòu)造方法如下。publicSinglyLinkedList<E[]element> //由指定數(shù)組中的多個對象構(gòu)造單鏈表{this.head=null;if<element!=null&&element.length>0>{this.head=newNode<element[0]>;Node<E>rear=this.head;inti=1;while<i<element.length>{rear.next=newNode<element[i++]>;rear=rear.next;}}}實驗2.2單鏈表的查找、包含、刪除操作詳見。單鏈表的以下查找、包含、刪除等操作方法詳見順序查找。publicNode<E>search<Eelement,Node<E>start>//從單鏈表結(jié)點start開始順序查找指定對象publicNode<E>search<Eelement> //若查找到指定對象,則返回結(jié)點,否則返回nullpublicbooleancontain<Eelement> //以查找結(jié)果判斷單鏈表是否包含指定對象publicbooleanremove<Eelement> //移去首次出現(xiàn)的指定對象實驗2.2單鏈表的替換操作。在SinglyLinkedList單鏈表類中,增加替換操作方法如下。publicbooleanreplace<Objectobj,Eelement> //將元素值為obj的結(jié)點值替換為element{ //若替換成功返回true,否則返回false,O<n>if<obj==null||element==null>returnfalse;Node<E>p=this.head;while<p!=null>{if<obj.equals<p.data>>{p.data=element;returntrue;}p=p.next;}returnfalse;}實驗2.2首尾相接地連接兩條單鏈表。在SinglyLinkedList單鏈表類中,增加替換操作方法如下。publicvoidconcat<SinglyLinkedListlist> //將指定單鏈表list鏈接在當(dāng)前單鏈表之后{if<this.head==null>this.head=list.head;else{Node<E>p=this.head;while<p.next!=null>p=p.next;p.next=list.head;}}實驗2.2復(fù)制單鏈表。在SinglyLinkedList單鏈表類中,增加構(gòu)造方法如下。publicSinglyLinkedList<SinglyLinkedList<E>list> //以單鏈表list構(gòu)造新的單鏈表{//復(fù)制單鏈表this.head=null;if<list!=null&&list.head!=null>{this.head=newNode<list.head.data>;Node<E>p=list.head.next;Node<E>rear=this.head;while<p!=null>{rear.next=newNode<E><p.data>;rear=rear.next;p=p.next;}}}實驗2.2單鏈表構(gòu)造、復(fù)制、比較等操作的遞歸方法。由指定數(shù)組中的多個對象構(gòu)造單鏈表的操作也可設(shè)計為以下的遞歸方法：publicSinglyLinkedList<E[]element> //由指定數(shù)組中的多個對象構(gòu)造單鏈表{this.head=null;if<element!=null>this.head=create<element,0>;}privateNode<E>create<E[]element,inti> //由指定數(shù)組構(gòu)造單鏈表,遞歸方法{Node<E>p=null;if<i<element.length>{p=newNode<element[i]>;p.next=create<element,i+1>;}returnp;}單鏈表的復(fù)制操作也可設(shè)計為以下的遞歸方法：publicSinglyLinkedList<SinglyLinkedList<E>list> //以單鏈表list構(gòu)造新的單鏈表{this.head=copy<list.head>;}privateNode<E>copy<Node<E>p> //復(fù)制單鏈表,遞歸方法{Node<E>q=null;if<p!=null>{q=newNode<p.data>;q.next=copy<p.next>;}returnq;}比較兩條單鏈表是否相等的操作也可設(shè)計為以下的遞歸方法：publicbooleanequals<Objectobj> //比較兩條單鏈表是否相等{if<obj==this>returntrue;if<objinstanceofSinglyLinkedList>{SinglyLinkedListlist=<SinglyLinkedList>obj;returnequals<this.head,list.head>;}returnfalse;}privatebooleanequals<Node<E>p,Node<E>q> //比較兩條單鏈表是否相等,遞歸方法{if<p==null&&q==null>returntrue;if<p!=null&&q!=null>returnp.data.equals<q.data>&&equals<p.next,q.next>;returnfalse;}建立按升序排序的單鏈表〔不帶頭結(jié)點。采用直接插入排序算法將一個結(jié)點插入到已排序的單鏈表中。importdataStructure.linearList.Node;importdataStructure.linearList.SinglyLinkedList; //不帶頭結(jié)點的單鏈表類publicclassSortedSinglyLinkedList<E>extendsSinglyLinkedList<E>{publicSortedSinglyLinkedList<>{super<>;}publicbooleanadd<Eelement>//根據(jù)指定對象的大小插入在合適位置{if<element==null||!<elementinstanceofComparable>>returnfalse;//不能插入null或非Comparable對象Comparablecmp=<Comparable>element;if<this.head==null||pareTo<this.head.data><=0>this.head=newNode<E><element,this.head>; //頭插入else{Node<E>front=null,p=this.head;while<p!=null&&pareTo<p.data>>0>{front=p; //front是p的前驅(qū)結(jié)點p=p.next;}front.next=newNode<E><element,p>; //中間/尾插入}returntrue;}publicstaticvoidmain<Stringargs[]>{SortedSinglyLinkedList<Integer>list=newSortedSinglyLinkedList<Integer><>;intn=10;System.out.print<"insert：">;for<inti=0;i<n;i++>{intk=<int><Math.random<>*100>;//產(chǎn)生隨機數(shù)if<list.add<newInteger<k>>>System.out.print<k+"">;}System.out.println<"\nlist:"+list.toString<>>;}}程序多次運行結(jié)果如下：insert：2248509717119675080list:<9,19,22,48,50,50,67,71,71,80>insert：42335289131150297834list:<11,13,29,33,34,42,50,52,78,89>insert：6916990206814739076list1:<0,14,16,20,68,69,73,76,90,99>實驗2.6帶頭結(jié)點的循環(huán)雙鏈表類,實現(xiàn)線性表接口。packagedataStructure.linearList;importdataStructure.linearList.DLinkNode; //導(dǎo)入雙鏈表結(jié)點類importdataStructure.linearList.LList; //導(dǎo)入線性表接口publicclassCHDoublyLinkedList<E>implementsLList<E> //帶頭結(jié)點的循環(huán)雙鏈表類{protectedDLinkNode<E>head; //頭指針publicCHDoublyLinkedList<> //構(gòu)造空鏈表{this.head=newDLinkNode<E><>; //創(chuàng)建頭結(jié)點,值為nullthis.head.prev=head;this.head.next=head;}publicbooleanisEmpty<> //判斷雙鏈表是否為空{(diào)returnhead.next==head;}//以下算法同循環(huán)單鏈表,與單鏈表的差別在于,循環(huán)條件不同publicintlength<> //返回雙鏈表長度{inti=0;DLinkNode<E>p=this.head.next; //此句與單鏈表不同while<p!=head> //循環(huán)條件與單鏈表不同{i++;p=p.next;}returni;}publicEget<intindex> //返回序號為index的對象{if<index>=0>{intj=0;DLinkNode<E>p=this.head.next;while<p!=head&&j<index>{j++;p=p.next;}if<p!=head>return<E>p.data;}returnnull;}publicEset<intindex,Eelement> //設(shè)置index序號對象為element{if<index>=0&&element!=null>{intj=0;DLinkNode<E>p=this.head.next;while<p!=head&&j<index>{j++;p=p.next;}if<p!=head>{Eold=<E>p.data;p.data=element;returnold;}}returnnull;}publicStringtoString<>{Stringstr="<";DLinkNode<E>p=this.head.next;while<p!=head>{str+=p.data.toString<>;p=p.next;if<p!=head>str+=",";}returnstr+">";}//雙鏈表的插入、刪除算法與單鏈表不同publicbooleanadd<intindex,Eelement>//插入element對象,插入后對象序號為index{ //若操作成功返回true,O<n>if<element==null>returnfalse; //不能添加空對象〔nullintj=0;DLinkNode<E>front=this.head;while<front.next!=head&&j<index>//尋找插入位置,若i<=0,插入在頭結(jié)點之后{j++;front=front.next;}DLinkNode<E>q=newDLinkNode<E><element,front,front.next>;//插入在front結(jié)點之后front.next.prev=q;front.next=q;returntrue;}publicbooleanadd<Eelement> //在單鏈表最后添加對象,O<1>{if<element==null>returnfalse; //不能添加空對象〔nullDLinkNode<E>q=newDLinkNode<E><element,head.prev,head>;head.prev.next=q; //插入在頭結(jié)點之前,相當(dāng)于尾插入head.prev=q;returntrue;}publicEremove<intindex> //移除指定位置的對象,O<n>{//返回被移除的原對象,指定位置序號錯誤時返回nullEold=null;intj=0;DLinkNode<E>p=this.head.next;while<p!=head&&j<index> //定位到待刪除結(jié)點{j++;p=p.next;}if<p!=head>{old=<E>p.data; //操作成功,返回原對象p.prev.next=p.next; //刪除p結(jié)點自己p.next.prev=p.prev;}returnold;}publicvoidclear<> //清空線性表{this.head.prev=head;this.head.next=head;}//以上實現(xiàn)LList接口publicstaticvoidmain<Stringargs[]>{inti=0;CHDoublyLinkedList<String>list=newCHDoublyLinkedList<String><>;System.out.println<"刪除第"+i+"個結(jié)點"+list.remove<0>>;System.out.println<list.toString<>>;for<i=5;i>=0;i-->list.add<0,newString<<char><'A'+i>+"">>;for<i=0;i<6;i++>list.add<newString<<char><'A'+i>+"">>;//list.add<i,newString<<char><'A'+i>+"">>;System.out.println<list.toString<>>;System.out.println<"刪除第"+i+"個結(jié)點"+list.remove<i>>;System.out.println<list.toString<>>;}}程序運行結(jié)果如下：刪除第0個結(jié)點null<><A,B,C,D,E,F,A,B,C,D,E,F>刪除第6個結(jié)點A<A,B,C,D,E,F,B,C,D,E,F>實驗2.5建立按升序排序的循環(huán)雙鏈表。packagedataStructure.linearList;importdataStructure.linearList.DLinkNode;st; //循環(huán)雙鏈表類publicclassSortedCHDLinkedList<E>extendsCHDoublyLinkedList<E>{ //按升序排序的循環(huán)雙鏈表類publicSortedCHDLinkedList<>{super<>;}publicbooleanadd<Eelement>//根據(jù)指定對象的大小插入在合適位置{//若操作成功返回true,O<n>if<element==null||!<elementinstanceofComparable>>returnfalse;//不能插入null或非Comparable對象Comparablecmp=<Comparable>element;if<this.head.prev!=head&&pareTo<this.head.prev.data>>0>{ //非空雙鏈表,插入在最后,O<1>DLinkNode<E>q=newDLinkNode<E><element,head.prev,head>;head.prev.next=q;//插入在頭結(jié)點之前,相當(dāng)于尾插入head.prev=q;returntrue;}DLinkNode<E>p=this.head.next;while<p!=head&&pareTo<p.data>>0>//尋找插入位置p=p.next;DLinkNode<E>q=newDLinkNode<E><element,p.prev,p>;//插入在p結(jié)點之前p.prev.next=q;p.prev=q;returntrue;}publicbooleanremove<Eelement>//刪除指定對象{//若操作成功返回true,O<n>if<element==null||!<elementinstanceofComparable>>returnfalse;Comparablecmp=<Comparable>element;DLinkNode<E>p=this.head.next;while<p!=head&&pareTo<p.data>>0>//定位到待刪除的結(jié)點p=p.next;if<p!=head>{p.prev.next=p.next;//刪除p結(jié)點自己p.next.prev=p.prev;returntrue;}returnfalse;//未找到指定結(jié)點,刪除不成功}publicstaticvoidmain<Stringargs[]>{SortedCHDLinkedList<Integer>list=newSortedCHDLinkedList<Integer><>;intn=10;System.out.print<"insert：">;for<inti=0;i<n;i++>{intk=<int><Math.random<>*100>;if<list.add<newInteger<k>>>System.out.print<k+"">;}System.out.println<"\nlist:"+list.toString<>>;}}程序運行結(jié)果如下：insert：53192842432739999list:<1,2,3,24,53,73,84,92,99,99>棧和隊列習(xí)3-5棧和隊列有何異同？棧和隊列都是特殊的線性表,兩者的區(qū)別在于：棧的插入和刪除操作只允許在線性表的一端進行,而隊列的插入和刪除操作則分別在線性表的兩端進行。能否將棧聲明為繼承線性表,入棧方法是add<0,e>,出棧方法是remove<0>？為什么？不行。棧不支持中間插入和刪除操作。能否用一個線性表作為棧的成員變量,入棧方法是add<0,e>,出棧方法是remove<0>？為什么？不行。能否將隊列聲明為繼承線性表,入隊方法是add<e>,出隊方法是remove<0>？為什么？不行。隊列不支持中間插入和刪除操作。串實驗4.6找出兩個字符串中所有共同的字符。publicclassSameChar{publicstaticvoidmain<Stringargs[]>{Stringastr="integer",bstr="string";System.out.println<"Twostrings:"+astr+""+bstr>;System.out.print<"SameChar:">;for<inti=0;i<astr.length<>;i++>{for<intj=0;j<bstr.length<>;j++>if<astr.charAt<i>==bstr.charAt<j>>System.out.print<astr.charAt<i>+"">;}System.out.println<>;}}程序運行結(jié)果如下：Twostrings:integerstringSamechar:intgr習(xí)4-9<1>已知目標(biāo)串為"abbaba"、模式串為"aba",畫出其KMP算法的匹配過程,并給出比較次數(shù)。KMP算法模式匹配過程如圖4.1所示,比較6次。目標(biāo)串"abbaba"和模式串"aba"的KMP算法模式匹配過程習(xí)4-9<2>已知target="ababaab"、pattern="aab",求模式串的next數(shù)組,畫出其KMP算法的匹配過程,并給出比較次數(shù)。模式串"aab"的next數(shù)組見表4.1。模式串"aab"的next數(shù)組j012模式串a(chǎn)ab"p0…pj-1"中最長相同的前后綴長度k-101pk與pj比較=≠改進的next[j]-1-11其KMP算法的匹配過程如圖4.2所示,比較7次。目標(biāo)串"ababaab"和模式串"aab"的KMP算法模式匹配過程數(shù)組和廣義表求一個矩陣的轉(zhuǎn)置矩陣。在Matrix類中增加以下方法。publicMatrixtranspose<>//返回轉(zhuǎn)置矩陣{Matrixtrans=newMatrix<value[0].length,value.length>;for<inti=0;i<this.value.length;i++>for<intj=0;j<this.value[i].length;j++>trans.value[j][i]=this.value[i][j];returntrans;}樹和二叉樹畫出3個結(jié)點的各種形態(tài)的樹和二叉樹。3個結(jié)點的樹有2種形態(tài),3個結(jié)點的二叉樹有5種形態(tài),如圖6.1所示。3個結(jié)點樹和二叉樹的形態(tài)找出分別滿足下面條件的所有二叉樹。先根遍歷序列和中根遍歷序列相同：右單支二叉樹,如圖H.5〔a所示。中根遍歷序列和后根遍歷序列相同：左單支二叉樹,如圖H.5〔b所示。先根遍歷序列和后根遍歷序列相同：空樹,只有一個根結(jié)點的二叉樹。單支二叉樹輸出葉子結(jié)點。在BinaryTree類中增加以下方法。publicvoidleaf<> //遍歷輸出葉子結(jié)點{leaf<root>;}publicvoidleaf<BinaryNode<E>p>//先根次序遍歷,輸出葉子結(jié)點,3種遍歷次序結(jié)果一樣{if<p!=null>{if<p.isLeaf<>>System.out.print<p.data+"">;leaf<p.left>;leaf<p.right>;}}求一棵二叉樹的葉子結(jié)點個數(shù)。在BinaryTree類中增加以下方法。publicintcountLeaf<> //求一棵二叉樹中所有葉子結(jié)點個數(shù){returncountLeaf<root>;}publicintcountLeaf<BinaryNode<E>p> //求以p結(jié)點為根的子樹的葉子結(jié)點個數(shù){if<p==null>return0;if<p.isLeaf<>>return1;returncountLeaf<p.left>+countLeaf<p.right>;}判斷兩棵二叉樹是否相等。publicbooleanequals<Objectobj> //比較兩棵二叉樹是否相等,BinaryTree類中方法{if<obj==this>returntrue;if<objinstanceofBinaryTree>{BinaryTree<E>bitree=<BinaryTree>obj;returnequals<this.root,bitree.root>;}returnfalse;}privatebooleanequals<BinaryNode<E>p,BinaryNode<E>q>//判斷兩棵子樹是否相等,遞歸方法{if<p==null&&q==null>returntrue;if<p!=null&&q!=null>return<p.data.equals<q.data>>&&equals<p.left,q.left>&&equals<p.right,q.right>;returnfalse;}復(fù)制一棵二叉樹。在BinaryTree類中增加以下構(gòu)造方法,以已知的bitree構(gòu)造二叉樹構(gòu)造一棵二叉樹。publicBinaryTree<BinaryTree<E>bitree> //以已知的bitree構(gòu)造二叉樹{this.root=copy<bitree.root>;}publicBinaryNode<E>copy<BinaryNode<E>p> //復(fù)制以p根的子二叉樹{BinaryNode<E>q=null;if<p!=null>{q=newBinaryNode<E><p.data>;q.left=copy<p.left>; //復(fù)制左子樹q.right=copy<p.right>; //復(fù)制右子樹}returnq; //返回建立子樹的根結(jié)點}二叉樹的替換操作。publicbooleanreplace<Eold,Evalue> //將首次出現(xiàn)的值為old結(jié)點值替換為value{BinaryNode<E>find=search<old>; //查找值為old的結(jié)點if<find!=null>find.data=value; //替換結(jié)點元素值returnfind!=null;}publicvoidreplaceAll<Eold,Evalue> //將值為old的結(jié)點全部替換為value{replaceAll<root,old,value>;}publicvoidreplaceAll<BinaryNode<E>p,Eold,Evalue> //在以p為根的子樹中實現(xiàn)全部替換{if<p!=null>{if<p.data.equals<old>>p.data=value;replaceAll<p.left,old,value>;replaceAll<p.right,old,value>;}}后根次序遍歷中序線索二叉樹。在中序線索二叉樹類ThreadBinaryTree中,增加以下方法,實現(xiàn)后根次序遍歷。publicThreadBinaryNode<E>postPrevious<ThreadBinaryNode<E>p>//返回p在后根次序下的前驅(qū){if<p.rtag==0> //若右子樹非空p=p.right; //右孩子是p的前驅(qū)結(jié)點else //否則,前驅(qū)是左兄弟或某個中序祖先的左孩子{while<p.ltag==1&&p.left!=null>p=p.left; //尋找其某個中序祖先p=p.left; //左孩子是p的前驅(qū)結(jié)點}returnp;}publicvoidpostOrder_previous<> //后根次序遍歷中序線索二叉樹{ThreadBinaryNode<E>p=root;if<p!=null>{System.out.print<"后根次序遍歷〔反序：">;do{System.out.print<p.data+"">;p=postPrevious<p>; //返回p在后根次序下的前驅(qū)結(jié)點}while<p!=null>;System.out.println<>;}}圖查找實驗8.1順序表的查找、刪除、替換、比較操作。程序見順序表類SeqList.java。publicintlastIndexOf<Eelement> //返回obj對象最后出現(xiàn)位置,若未找到返回-1{if<obj!=null>for<inti=this.n-1;i>=0;i-->if<obj.equals<this.table[i]>>returni;return-1;}publicbooleanremove<Eelement> //移去首次出現(xiàn)的obj對象,若操作成功返回true{if<this.n!=0&&obj!=null>returnthis.remove<this.indexOf<obj>>!=null;returnfalse;}publicbooleanremoveAll<Eelement> //移去線性表中所有obj對象{booleandone=false;if<this.n!=0&&obj!=null>{inti=0;while<i<this.n>if<obj.equals<this.table[i]>>{this.remove<i>;done=true;}elsei++;}returndone;}publicbooleanreplace<Objectobj,Eelement> //將首次出現(xiàn)的obj對象替換為element對象{ //若操作成功返回true,O<n/2>if<obj!=null&&element!=null>{inti=this.indexOf<obj>; //查找obj對象首次出現(xiàn)位置if<i!=-1>{this.table[i]=element;returntrue;}}returnfalse;}publicbooleanreplaceAll<Objectobj,Eelement>//將線性表中所有obj對象替換為element對象{booleandone=false;if<obj!=null&&element!=null>for<inti=0;i<this.n;i++>if<obj.equals<this.table[i]>>{this.table[i]=element;done=true;}returndone;}publicbooleanequals<Objectobj> //比較兩個順序表對象是否相等{//O<n>if<this==obj>returntrue;if<objinstanceofSeqList>{SeqList<E>list=<SeqList<E>>obj;for<inti=0;i<this.length<>;i++>if<!<this.get<i>.equals<list.get<i>>>>returnfalse;returntrue;}returnfalse;}實驗8.2單鏈表的全部替換操作。在SinglyLinkedList單鏈表類中,增加替換操作方法如下。publicbooleanreplace<Objectobj,Eelement> //詳見實驗2.2publicbooleanreplaceAll<Objectobj,Eelement>//將所有元素值為obj的結(jié)點值替換為element{//若替換成功返回true,否則返回falsebooleandone=false;if<obj!=null&&element!=null>{Node<E>p=this.head;while<p!=null>{if<obj.equals<p.data>>{p.data=element;done=true;}p=p.next;}}returndone;}實驗8.2單鏈表的全部刪除操作。在SinglyLinkedList單鏈表類中,增加刪除操作方法如下。publicbooleanremoveAll<Objectobj> //將所有元素值為obj的結(jié)點刪除{if<this.head==null||obj==null>returnfalse;booleandone=false;while<this.head!=null&&obj.equals<this.head.data>>{this.head=this.head.next; //頭刪除done=true;}Node<E>front=this.head,p=front.ne