二叉樹(shù)的二叉鏈表表示

1、=實(shí)習(xí)報(bào)告二“二叉樹(shù)的二叉鏈表表示”演示程序 =（1） 、程序的功能和特點(diǎn)1. 程序功能：利用鏈表對(duì)非線性二叉樹(shù)進(jìn)行存儲(chǔ)表示和訪問(wèn)。能夠創(chuàng)建二叉樹(shù)，并且能夠按前序遍歷顯示輸出所創(chuàng)建的二叉樹(shù)。2. 程序特點(diǎn)：采用java面向?qū)ο笳Z(yǔ)言，對(duì)二叉樹(shù)用二叉鏈表用類進(jìn)行封裝。能夠創(chuàng)建二叉樹(shù)，并且能夠按前序遍歷顯示輸出所創(chuàng)建的二叉樹(shù)。（2） 、程序的算法設(shè)計(jì)算法一：“按前序遍歷方式建立二叉樹(shù)”算法：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)】 邏輯結(jié)構(gòu)：非線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。頭指針bt 頭結(jié)點(diǎn)指針btaacbcbfedfedgg (a) 帶頭指針的二叉鏈表 (b) 帶頭結(jié)點(diǎn)的二叉鏈表 鏈?zhǔn)?二叉樹(shù)的二叉

2、鏈表表示示意圖開(kāi)始創(chuàng)建2. 【基本操作設(shè)計(jì)】鍵盤輸入二叉樹(shù)的二叉鏈的數(shù)據(jù)if ( item != refvalue ) y n封閉葉子結(jié)點(diǎn)創(chuàng)建二叉鏈表結(jié)點(diǎn) 遞歸生成左右子樹(shù)創(chuàng)建成功返回二叉樹(shù)的頭指針創(chuàng)建結(jié)束3. 【算法設(shè)計(jì)】 創(chuàng)建二叉鏈表文字說(shuō)明： （1）.首先按前序輸入二叉樹(shù)。 （2）.判斷是否是封閉結(jié)點(diǎn)的標(biāo)識(shí)，如果不是則創(chuàng)建二叉鏈表，遞歸生成其左右子樹(shù)。 （3）.如果是封閉結(jié)點(diǎn)標(biāo)識(shí)則結(jié)束; （4）.插入成功返回二叉鏈表的頭指針。4. 【高級(jí)語(yǔ)言代碼】/按前序遍歷方式建立二叉樹(shù)public bintreenode preordercreate ( bintreenode p ) double

3、 item=0.0;system.out.println("按照前序遍歷次序每次輸入一個(gè)結(jié)點(diǎn)值。");try /* 鍵盤接受一個(gè)double數(shù) */ bufferedreader br=new bufferedreader( new inputstreamreader(system.in) ); item=double.parsedouble(br.readline(); catch(ioexception e) if ( item != refvalue ) /讀入的不是參照值p=new bintreenode(item);p.leftchild=preordercrea

4、te(p.leftchild); /遞歸生成左子樹(shù)p.rightchild=preordercreate(p.rightchild); /遞歸生成右子樹(shù)/實(shí)參是空二叉樹(shù),得到返回的子二叉樹(shù)else /讀入的是參照數(shù)p=null; /封閉葉子結(jié)點(diǎn)return p; /返回二叉樹(shù)p 算法二：“按前序遍歷方式輸出二叉樹(shù)”算法：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)】 邏輯結(jié)構(gòu)：非線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。leftchilddatarightchild結(jié)構(gòu)如圖所示：開(kāi)始輸出2. 【基本操作設(shè)計(jì)】判斷鏈表是否為空？ y n輸出該節(jié)點(diǎn)的數(shù)據(jù)輸出該節(jié)點(diǎn)的數(shù)據(jù)遞歸輸出其左，右子樹(shù)輸出結(jié)束3.【算法設(shè)計(jì)】 文

5、字說(shuō)明： （1）.首先取鏈表元素判斷鏈表是否為空。 （2）.鏈表非空先輸出該結(jié)點(diǎn)的值，在遞歸調(diào)用該方法輸出其左右子樹(shù)。 （3）.鏈表為空則結(jié)束，結(jié)束退出。4.【高級(jí)語(yǔ)言代碼】/按前序遍歷方式輸出二叉樹(shù)public void preordertraverse (bintreenode p) if ( p != null ) /輸出根結(jié)點(diǎn)數(shù)據(jù)域 system.out.print(" "+p.getdata();/遞歸輸出p的左子樹(shù) preordertraverse ( p.leftchild );/遞歸輸出p的右子樹(shù) preordertraverse (p.rightchild

6、 );（三）、程序中類的設(shè)計(jì) “bintreenode”類：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)】 邏輯結(jié)構(gòu)：非線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二叉鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如圖(b)所示。頭指針bt 頭結(jié)點(diǎn)指針btaacbcbfedfedgg (a) 帶頭指針的二叉鏈表 (b) 帶頭結(jié)點(diǎn)的二叉鏈表 鏈?zhǔn)?二叉樹(shù)的二叉鏈表表示示意圖2. 【主要成員變量說(shuō)明】 主要成員變量有：data：為結(jié)點(diǎn)的數(shù)據(jù)域，為double類型變量。用于存放節(jié)點(diǎn)的數(shù)據(jù)。leftchild，rightchild：為節(jié)點(diǎn)的指針域，為bintreenode類型變量，存放結(jié)點(diǎn)的指向下一個(gè)節(jié)點(diǎn)的指針。結(jié)構(gòu)如圖所示：leftchil

7、ddatarightchild3. 【主要成員方法說(shuō)明】 public bintreenode ( double item)： 為bintreenode的構(gòu)造函數(shù)：一個(gè)葉子結(jié)點(diǎn) 。參數(shù)為該結(jié)點(diǎn)的數(shù)據(jù)。 public bintreenode ( double item, bintreenode left,bintreenode right)：構(gòu)造函數(shù)：非一個(gè)葉子結(jié)點(diǎn)。含有三個(gè)參數(shù)，分別為該結(jié)點(diǎn)的數(shù)據(jù)，左子樹(shù)和右子樹(shù)。public double getdata()：返回?cái)?shù)據(jù)域的值。4.【高級(jí)語(yǔ)言代碼】 / /定義“二叉鏈表結(jié)點(diǎn)”類class bintreenode private double d

8、ata; /結(jié)點(diǎn)數(shù)據(jù)域bintreenode leftchild; /結(jié)點(diǎn)左右指針域bintreenode rightchild;/構(gòu)造函數(shù)：一個(gè)葉子結(jié)點(diǎn)public bintreenode ( double item) data=item; /左右指針域自動(dòng)為null/構(gòu)造函數(shù)：一個(gè)非葉子結(jié)點(diǎn)public bintreenode ( double item, bintreenode left,bintreenode right) data=item;leftchild=left;rightchild=right;/返回結(jié)點(diǎn)數(shù)據(jù)域的值public double getdata() return

9、 data; /定義“二叉鏈表結(jié)點(diǎn)”類完畢 “cbinarytree”類：1. 【邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)】 邏輯結(jié)構(gòu)：非線性結(jié)構(gòu)。 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二叉鏈表可以有不帶頭結(jié)點(diǎn)（a）和帶都結(jié)點(diǎn)（b）。頭指針bt 頭結(jié)點(diǎn)指針btaacbcbfedfedgg (a) 帶頭指針的二叉鏈表 (b) 帶頭結(jié)點(diǎn)的二叉鏈表 2. 【主要成員變量說(shuō)明】 主要成員變量為：root：表示根節(jié)點(diǎn)，為bintreenode類型。refvalue：參照值為double類型。3. 【主要成員方法說(shuō)明】 public cbinarytree ( double v)：構(gòu)造函數(shù)：建立一棵空樹(shù)，并設(shè)定參照值。 public vo

10、id createbintree() ：以root為根建立二叉樹(shù)。 public bintreenode preordercreate ( bintreenode p,string s) ：按前序遍歷方式建立二叉樹(shù)。public bintreenode getroot()：得到二叉樹(shù)的根。public void preordertraverse (bintreenode p)：前序遍歷方式輸出二叉樹(shù)。public static void main(string args) ：主函數(shù)。 4.【高級(jí)語(yǔ)言代碼】 /*定義“二叉鏈表”類*public class cbinarytree private

11、 bintreenode root; /根節(jié)點(diǎn)private double refvalue; /參照值：在建立二叉樹(shù)之前，/給定一個(gè)結(jié)點(diǎn)數(shù)據(jù)域中不可能出現(xiàn)的數(shù)，/用來(lái)標(biāo)記二叉樹(shù)的一條分支到此封閉。/構(gòu)造函數(shù)：建立一棵空樹(shù)，并設(shè)定參照值public cbinarytree ( double v) refvalue=v;root=null;/以root為根建立二叉樹(shù)public void createbintree()root=preordercreate(root); /實(shí)參是空二叉樹(shù)/根root得到返回的二叉樹(shù)根節(jié)點(diǎn)/按前序遍歷方式建立二叉樹(shù)public bintreenode preord

12、ercreate ( bintreenode p ) double item=0.0;system.out.println("按照前序遍歷次序每次輸入一個(gè)結(jié)點(diǎn)值。");try /* 鍵盤接受一個(gè)double數(shù) */ bufferedreader br=new bufferedreader( new inputstreamreader(system.in) ); item=double.parsedouble(br.readline(); catch(ioexception e) if ( item != refvalue ) /讀入的不是參照值p=new bintreeno

13、de(item);p.leftchild=preordercreate(p.leftchild); /遞歸生成左子樹(shù)p.rightchild=preordercreate(p.rightchild); /遞歸生成右子樹(shù)/實(shí)參是空二叉樹(shù),得到返回的子二叉樹(shù)else /讀入的是參照數(shù)p=null; /封閉葉子結(jié)點(diǎn)return p; /返回二叉樹(shù)p/輸出以root為根的二叉樹(shù)public void outputbintree()preordertraverse(root);/按前序遍歷方式輸出二叉樹(shù)public void preordertraverse (bintreenode p) if ( p != null ) /輸出根結(jié)點(diǎn)數(shù)據(jù)域 system.out.print(" "+p.getdata();/遞歸輸出p的左子樹(shù) preordertraverse ( p.leftchild );/