數(shù)據(jù)結構java實驗四

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

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

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

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