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

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

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

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

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