二叉樹(shù)的基本操作課程設(shè)計(jì)

1、<p>　　《JAVA核心技術(shù)》</p><p><b>　　課題設(shè)計(jì)報(bào)告</b></p><p>　　課題名稱： 二叉樹(shù)的基本操作 </p><p>　　專業(yè)： 信息管理與信息系統(tǒng) </p><p>　　班級(jí)： </p><p>　　姓名：

2、 </p><p>　　學(xué)號(hào)： </p><p>　　指導(dǎo)老師： </p><p>　　日期： 2013/10/29 </p><p><b>　　課程序設(shè)計(jì)目的</b></p><p>　　（1

3、）掌握基于Java相關(guān)編程軟件的使用；</p><p>　　（2）掌握基于Java二叉樹(shù)的基本操作；</p><p>　　（3）實(shí)現(xiàn)對(duì)一棵二叉樹(shù)的基本操作。</p><p><b>　　開(kāi)發(fā)環(huán)境</b></p><p>　?。?）系統(tǒng)環(huán)境：Windows XP，Windows 2003 Server，Windows 7；

4、</p><p>　?。?）編程環(huán)境：JDK1.5，JCreator，Eclipse等</p><p><b>　　實(shí)現(xiàn)過(guò)程</b></p><p>　?。?）Java編程基礎(chǔ)知識(shí)介紹</p><p>　　1.Tree(); </p><p>　　Tree buildTree(Stri

5、ng pre, String in); //由嵌套括號(hào)表示法的字 </p><p>　　符串生成鏈接存儲(chǔ)的二叉樹(shù)；</p><p>　　3.void printtree(); //按嵌套括號(hào)表示法打印二叉樹(shù)；</p><p>　　4.void prevorder(); //前序遍歷；</p>

6、<p>　　5.void postorder(); //后序遍歷；</p><p>　　6.void inorder(); //中序遍歷；</p><p>　　7.void levelOrder()；//層次遍歷</p><p>　　8.int leafNum()； //求葉子節(jié)點(diǎn)數(shù)；</p><p>　　9.

7、int treedepth(); //求二叉樹(shù)深度。 </p><p><b>　?。?）概要設(shè)計(jì)</b></p><p>　　二叉樹(shù)： </p><p><b>　　a </b></p><p><b>　　/ \</b></p&

8、gt;<p><b>　　/ \</b></p><p>　　b i </p><p>　　/ \ / \</p><p>　　c f i m </p><p>　　/ \ / \ / \ /\</p><p>　　d e g h k l n o&l

9、t;/p><p><b>　?。?）詳細(xì)設(shè)計(jì)</b></p><p><b>　　類名：Gao</b></p><p><b>　　類功能簡(jiǎn)介：</b></p><p>　　構(gòu)造服務(wù)器界面以及客戶端界面</p><p><b>　　方法1：<

10、/b></p><p><b>　　tree()</b></p><p><b>　　功能：</b></p><p>　　構(gòu)造方法用來(lái)生成實(shí)例時(shí)由系統(tǒng)自動(dòng)調(diào)用</p><p><b>　　方法2：</b></p><p>　　Tree buildT

11、ree(String pre, String in)</p><p><b>　　功能：</b></p><p>　　生成鏈接存儲(chǔ)的二叉樹(shù)</p><p><b>　　方法3：</b></p><p>　　void printtree()</p><p><b>　

12、　功能：</b></p><p>　　按嵌套括號(hào)表示法打印二叉樹(shù)</p><p><b>　　方法4：</b></p><p>　　void prevorder()</p><p><b>　　功能：</b></p><p><b>　　先序遍歷<

13、/b></p><p><b>　　方法5：</b></p><p>　　void postorder()</p><p><b>　　功能：</b></p><p><b>　　后序遍歷</b></p><p><b>　　方法6：&l

14、t;/b></p><p>　　void inorder()</p><p><b>　　功能：</b></p><p><b>　　中序遍歷</b></p><p><b>　　方法7：</b></p><p>　　void levelOrder

15、()</p><p><b>　　功能：</b></p><p><b>　　層次遍歷</b></p><p><b>　　方法8：</b></p><p>　　int leafNum()</p><p><b>　　功能：</b>

16、</p><p><b>　　求葉子節(jié)點(diǎn)數(shù)</b></p><p><b>　　方法9：</b></p><p>　　int treedepth()</p><p><b>　　功能：</b></p><p><b>　　求二叉樹(shù)的深度<

17、/b></p><p><b>　?。?）運(yùn)行程序截圖</b></p><p><b>　　附:程序源代碼</b></p><p>　　import java.util.ArrayDeque; </p><p>　　import java.util.Queue; </p><

18、;p>　　public class Gao { </p><p>　　public static void main(String[] args) { </p><p>　　// 測(cè)試Tree </p><p>　　Tree node = buildTree(null, 1); </p><p>　　System.out.print(&

19、quot;先序遍歷："); </p><p>　　preOrder(node); </p><p>　　System.out.println(); </p><p>　　System.out.print("中序遍歷："); </p><p>　　inOrder(node); </p><p&g

20、t;　　System.out.println(); </p><p>　　System.out.print("后序遍歷："); </p><p>　　postOrder(node); </p><p>　　System.out.println(); </p><p>　　System.out.print("層次遍

21、歷："); </p><p>　　levelOrder(node); </p><p>　　System.out.println(); </p><p>　　System.out.print("葉子節(jié)點(diǎn)數(shù)目："); </p><p>　　System.out.println(leafNum(node)); <

22、;/p><p>　　System.out.print("二叉樹(shù)的深度："); </p><p>　　System.out.println(deep(node)); </p><p><b>　　} </b></p><p>　　static char i = 'a';// 節(jié)點(diǎn) </

23、p><p>　　public static Tree buildTree(Tree node, int k) { </p><p>　　if (k > 4) </p><p>　　return null; </p><p>　　if (node == null) { </p><p>　　node = new Tre

24、enode(" " + i++); </p><p><b>　　} </b></p><p>　　node.lChild = buildTree(node.lChild, k + 1); </p><p>　　node.rChild = buildTree(node.rChild, k + 1); </p>

25、<p>　　return node; </p><p><b>　　} </b></p><p>　　// 根據(jù)先序和中序來(lái)構(gòu)建二叉樹(shù) </p><p>　　public Tree buildTree(String pre, String in) { </p><p>　　if (pre.length() &l

26、t;= 0) </p><p>　　return null; </p><p>　　Treenode root = new Tree(pre.charAt(0) + ""); </p><p>　　// 以根節(jié)點(diǎn)為中心，將中序分為兩個(gè)子序列 </p><p>　　String leftin = "";

27、</p><p>　　String rightin = ""; </p><p>　　// 根所左中序的長(zhǎng)度，將先序分為左右兩個(gè)子先序 </p><p>　　String leftpre = ""; </p><p>　　String rightpre = ""; </p>

28、;<p>　　root.lChild = buildTree(leftpre, leftin); </p><p>　　root.rChild = buildTree(rightpre, rightin); </p><p>　　return root; </p><p><b>　　} </b></p><p

29、><b>　　// 先序遍歷 </b></p><p>　　public static void preOrder(Tree node) { </p><p>　　if (node != null) { </p><p>　　System.out.print(node.data); </p><p>　　preOr

30、der(node.lChild); </p><p>　　preOrder(node.rChild); </p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　// 中序遍歷 </b></p><p&

31、gt;　　public static void inOrder(Tree node) { </p><p>　　if (node != null) { </p><p>　　inOrder(node.lChild); </p><p>　　System.out.print(node.data); </p><p>　　inOrder(node

32、.rChild); </p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　// 后序遍歷 </b></p><p>　　public static void postOrder(Tree node) { </p&

33、gt;<p>　　if (node != null) { </p><p>　　postOrder(node.lChild); </p><p>　　postOrder(node.rChild); </p><p>　　System.out.print(node.data); </p><p><b>　　} <

34、/b></p><p><b>　　} </b></p><p><b>　　// 層次遍歷 </b></p><p>　　public static void levelOrder(Tree node) { </p><p>　　if (node == null) </p>&

35、lt;p><b>　　return; </b></p><p>　　Queue<Tree> queue = new ArrayDeque<Tree>(); </p><p>　　queue.add(node); </p><p>　　while (!queue.isEmpty()) { </p>&l

36、t;p>　　Tree temp = queue.poll(); </p><p>　　System.out.print(temp.data); </p><p>　　if (temp.lChild != null) </p><p>　　queue.add(temp.lChild); </p><p>　　if (temp.rChild

37、 != null) </p><p>　　queue.add(temp.rChild); </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　// 求樹(shù)的葉子節(jié)點(diǎn)數(shù) </p><p>　　public static int

38、 leafNum(Tree node) { </p><p>　　if (node != null) { </p><p>　　if (node.lChild == null && node.rChild == null) { </p><p>　　return 1; </p><p><b>　　} </b&

39、gt;</p><p>　　return leafNum(node.lChild)+leafNum(node.rChild); </p><p><b>　　} </b></p><p>　　return 0; </p><p><b>　　} </b></p><p>　　

40、//求二叉樹(shù)的深度 </p><p>　　public static int deep(Tree node){ </p><p>　　if(node == null)return 0; </p><p>　　if(node.lChild==null&&node.rChild==null)return 1; </p><p>　

41、　return leafNum(node.lChild)+leafNum(node.rChild); </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　class Tree { </p><p>　　public String data; &l

42、t;/p><p>　　public Tree lChild; </p><p>　　public Tree rChild; </p><p><b>　　// 構(gòu)造函數(shù) </b></p><p>　　public Tree(String data) { </p><p>　　this.data = d

43、ata; </p><p>　　this.lChild = null; </p><p>　　this.rChild = null; </p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　四、課題總結(jié)<

44、;/b></p><p><b>　?。?）主要問(wèn)題</b></p><p>　　本程序的實(shí)現(xiàn)還比較簡(jiǎn)單不夠完善，從中，我知道了自己的不足之處，決心 </p><p>　　增長(zhǎng)自己的知識(shí)，設(shè)計(jì)更加好的程序，實(shí)現(xiàn)各種更加復(fù)雜的功能。</p><p><b>　　收獲</b></p>

45、;<p>　　通過(guò)本次課程設(shè)計(jì)，使得自己懂得理論和實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正掌握這門(mén)技術(shù)，也提高了自己獨(dú)立思考的能力，以前在本子上寫(xiě)二叉樹(shù)，而現(xiàn)在用JAVA基礎(chǔ)就能實(shí)現(xiàn)。在設(shè)計(jì)的過(guò)程中，可以自己解決。組員們積極參與本課程設(shè)計(jì)的程序編寫(xiě)，身為組長(zhǎng)倍感欣慰。這次實(shí)訓(xùn)對(duì)我很有幫助,讓我學(xué)會(huì)了不只是實(shí)現(xiàn)二叉樹(shù)的基本操作，更讓我學(xué)會(huì)主動(dòng)學(xué)習(xí)，而不是被動(dòng)接收。這樣才能更好的運(yùn)用自己所學(xué)到的知識(shí)。</p>