數(shù)據(jù)結(jié)構(gòu)java實(shí)驗(yàn)四

1、《數(shù)據(jù)結(jié)構(gòu)（JAVA）》綜合性、設(shè)計(jì)性實(shí)驗(yàn)成績(jī)單開設(shè)時(shí)間：2012學(xué)年第一學(xué)期班級(jí)11信管4班學(xué)號(hào)1.2011305604152.2011305604183.2011305604194.2011305604205.201130560424姓名1.劉梓明2.王悅3.薛澤展4.楊海龍5.余柏?zé)顚?shí)驗(yàn)題目實(shí)驗(yàn)四樹和二叉樹的基本操作成績(jī)教師簽名2一、實(shí)驗(yàn)報(bào)告撰寫提綱1、實(shí)驗(yàn)?zāi)康?理解二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)等基本概念，掌握二叉樹類的設(shè)計(jì)方法，

2、以及遍歷、插入、刪除等二叉樹操作的算法實(shí)現(xiàn)；掌握采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表達(dá)非線性結(jié)構(gòu)的設(shè)計(jì)方法；掌握采用遞歸算法實(shí)現(xiàn)遞歸數(shù)據(jù)結(jié)構(gòu)基本操作的設(shè)計(jì)方法。2熟悉樹的定義、表示、存儲(chǔ)結(jié)構(gòu)和遍歷，具備使用樹各種操作的能力。2、實(shí)驗(yàn)內(nèi)容（1）在一棵二叉鏈表表示的二叉樹中，實(shí)現(xiàn)以下操作，并說(shuō)明采用哪種遍歷算法，其他遍歷算法是否可行。①輸入葉子結(jié)點(diǎn)。②求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)。③將每個(gè)結(jié)點(diǎn)的左子樹與右子樹交換。④驗(yàn)證二叉樹的性質(zhì)3：n0=n21。⑤輸出值大于k

3、的結(jié)點(diǎn)。⑥已知先根和中根次序遍歷序列構(gòu)造二叉樹。⑦以廣義表表示構(gòu)造二叉樹。⑧判斷兩顆二叉樹是否相等。⑨求結(jié)點(diǎn)所在的層次。⑩求一顆二叉樹在后根次序遍歷下第一個(gè)訪問(wèn)的結(jié)點(diǎn)。復(fù)制一顆二叉樹。判斷一顆二叉樹是否為完全二叉樹。實(shí)現(xiàn)二叉樹后根次序遍歷的非遞歸算法。（2）聲明三叉鏈表表示的二叉樹類，實(shí)現(xiàn)二叉樹的基本操作以及以下操作。①構(gòu)造一顆三叉鏈表表示的二叉樹。②返回指定結(jié)點(diǎn)的父母結(jié)點(diǎn)。③返回指定結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。④返回兩結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)。

4、（3）在一顆中序線索二叉樹中，實(shí)現(xiàn)以下操作。①調(diào)用求結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)算法，按中根次序遍歷一顆中序線索二叉樹。②按后根次序遍歷中序線索二叉樹。③在構(gòu)造二叉樹時(shí)進(jìn)行線索化。④插入、刪除操作。3、實(shí)驗(yàn)步驟與結(jié)果（1）①審題：在一棵二叉鏈表表示的二叉樹中，實(shí)現(xiàn)以下操作，并說(shuō)明采用哪種遍歷算法，其他遍歷算法是否可行。①輸入葉子結(jié)點(diǎn)。②求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)。③將每個(gè)結(jié)點(diǎn)的左子樹與右子樹交換。④驗(yàn)證二叉樹的性質(zhì)3：n0=n21。⑤輸出值大于k的結(jié)點(diǎn)。