蔡少云數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-二叉樹的基本操作

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 學(xué)院： 管理學(xué)院 班級(jí)： 13電商1班 姓名： 蔡少云 學(xué)號(hào)： 321300- 2014年 12 月1 日目錄一、需求分析 問題描述 基本要求 實(shí)現(xiàn)說明二、設(shè)計(jì)目的三、概要設(shè)計(jì)基本框架圖設(shè)計(jì)想法四、詳細(xì)設(shè)計(jì) 結(jié)點(diǎn)類 二叉樹接口 二叉樹類 測(cè)試類五、測(cè)試結(jié)果 基本數(shù)據(jù) 操作截圖六、用戶使用說明七、心得體會(huì)題目：二叉樹的基本操作一、需求分析【問題描述】在一棵二叉鏈表表示的二叉樹中，實(shí)現(xiàn)以下操作，并說明采用哪種遍歷算法，其他遍歷算法是否可行。1. 二叉樹的先根次序遍歷2. 輸出以p結(jié)點(diǎn)為根的子樹的所有葉子結(jié)點(diǎn)，先根次序遍歷算法3. 將每個(gè)結(jié)點(diǎn)的左子樹與右子樹交換4. 由中根和后根次

2、序遍歷序列構(gòu)造二叉樹5. 二叉樹深拷貝，復(fù)制一棵二叉樹【基本要求】建立結(jié)點(diǎn)類，二叉樹接口。實(shí)現(xiàn)二叉樹的先根次序遍歷，中根次序遍歷和后根次序遍歷?！緦?shí)現(xiàn)說明】可以利用利用二叉樹的先根次序遍歷完成相應(yīng)功能。二、設(shè)計(jì)目的1、達(dá)到熟悉掌握java和數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和技能；2、能夠利用所學(xué)的基本知識(shí)和技能，解決簡(jiǎn)單的面向?qū)ο蟮脑O(shè)計(jì)問題；3、把課本上的知識(shí)應(yīng)用到實(shí)際生活中，達(dá)到學(xué)以致用的目的；4、復(fù)習(xí)學(xué)過的知識(shí)，思考新的問題；三、概要設(shè)計(jì)(1)基本框架圖：結(jié)點(diǎn)類屬性：data、left、right、構(gòu)造函數(shù)方法：輸出方法、判斷是否葉子結(jié)點(diǎn)方法判斷二叉樹是否為空isEmpty()二叉樹接口先根、中根、后根

3、次序遍歷二叉樹遍歷輸出葉子結(jié)點(diǎn)lrTran();將每個(gè)結(jié)點(diǎn)的左子樹與右子樹交換leaf1()二叉樹深拷貝，復(fù)制一棵二叉樹抽象方法實(shí)現(xiàn)二叉樹類 (2)設(shè)計(jì)想法:1、建立結(jié)點(diǎn)類BinaryNode；2、建立二叉樹接口BinaryTTree<T>3、建立二叉樹類，實(shí)現(xiàn)二叉樹接口BinaryTree<T>4、建立主類，創(chuàng)建二叉樹，進(jìn)行測(cè)試。四、詳細(xì)設(shè)計(jì)1、結(jié)點(diǎn)類/結(jié)點(diǎn)類public class BinaryNode<T> /二叉樹的二叉鏈表結(jié)點(diǎn)類，泛型T指定結(jié)點(diǎn)的元素類型 public T data; /數(shù)據(jù)域，存儲(chǔ)數(shù)據(jù)元素 public BinaryNode<

4、;T> left, right; /鏈域，分別指向左、右孩子結(jié)點(diǎn) /構(gòu)造結(jié)點(diǎn)，參數(shù)分別指定元素和左、右孩子結(jié)點(diǎn) public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) this.data = data; this.left = left; this.right = right; public BinaryNode(T data) /構(gòu)造指定值的葉子結(jié)點(diǎn) this(data, null, null); public BinaryNode() this(null, null, null);

5、/可聲明以下方法 public String toString() return this.data.toString(); public boolean equals(Object obj) /比較兩個(gè)結(jié)點(diǎn)值是否相等，覆蓋Object類的equals(obj)方法 return obj=this | obj instanceof BinaryNode && this.data.equals(BinaryNode<T>)obj).data); public boolean isLeaf() /判斷是否葉子結(jié)點(diǎn) return this.left=null &&

6、amp; this.right=null; 2、二叉樹接口：/二叉樹接口public interface BinaryTTree<T> /二叉樹接口，二叉樹抽象數(shù)據(jù)類型boolean isEmpty(); /判斷二叉樹是否空void preOrder(); /先根次序遍歷二叉樹void inOrder(); /中根次序遍歷二叉樹void postOrder(); /后根次序遍歷二叉樹 void lrTran(); void leaf1();BinaryNode<T> copy(BinaryNode<T> p); 3、二叉樹類：/二叉樹類，實(shí)現(xiàn)BinaryTT

7、ree<T>接口，泛型T指定結(jié)點(diǎn)的元素類型public class BinaryTree<T> implements BinaryTTree<T> public BinaryNode<T> root; /根結(jié)點(diǎn)，結(jié)點(diǎn)結(jié)構(gòu)為二叉鏈表 public BinaryTree() /構(gòu)造空二叉樹 this.root=null; public boolean isEmpty() /判斷二叉樹是否空 return this.root=null; /* 1.先根次序遍歷* public void preOrder() /先根次序遍歷二叉樹 System.out.

8、print("先根次序遍歷二叉樹： "); preOrder(root); /調(diào)用先根次序遍歷二叉樹的遞歸方法 System.out.println(); public void preOrder(BinaryNode<T> p) /先根次序遍歷以p結(jié)點(diǎn)為根的子二叉樹，遞歸方法 if (p!=null) /若二叉樹不空 System.out.print(p.data.toString()+" "); /訪問當(dāng)前結(jié)點(diǎn) preOrder(p.left); /按先根次序遍歷當(dāng)前結(jié)點(diǎn)的左子樹，遞歸調(diào)用 preOrder(p.right); /按先根次

9、序遍歷當(dāng)前結(jié)點(diǎn)的右子樹，遞歸調(diào)用 public String toString() /返回先根次序遍歷二叉樹所有結(jié)點(diǎn)的描述字符串 return toString(root); private String toString(BinaryNode<T> p) /返回先根次序遍歷以p為根的子樹描述字符串，遞歸算法 if (p=null) return "" return p.data.toString()+" " + toString(p.left) + toString(p.right);/遞歸調(diào)用 /2.輸出以p結(jié)點(diǎn)為根的子樹的所有葉子結(jié)點(diǎn)，

10、先根次序遍歷算法 public void leaf1() /遍歷輸出葉子結(jié)點(diǎn) leaf1(root); private void leaf1(BinaryNode<T> p) int sum = 0; if(p!=null) if (p.left=null && p.right=null) /p.isLeaf() System.out.print(p.data.toString()+" "); leaf1(p.left); /遞歸 leaf1(p.right); /*3.將每個(gè)結(jié)點(diǎn)的左子樹與右子樹交換* public void lrTran()

11、lrTran(root); public void lrTran(BinaryNode<T> p) if (!(p.left=null&&p.right=null) BinaryNode<T> temp = p.left; p.left = p.right; p.right = temp; /*4.由中根和后根次序遍歷序列構(gòu)造二叉樹* /* 中根次序遍歷* public void inOrder() /中根次序遍歷二叉樹 System.out.print("中根次序遍歷二叉樹： "); inOrder(root); System.ou

12、t.println(); public void inOrder(BinaryNode<T> p) /中根次序遍歷以p結(jié)點(diǎn)為根的子二叉樹，遞歸方法 if (p!=null) inOrder(p.left); /中根次序遍歷左子樹，遞歸調(diào)用 System.out.print(p.data.toString()+" "); inOrder(p.right); /中根次序遍歷右子樹，遞歸調(diào)用 /* 后根次序遍歷* public void postOrder() /后根次序遍歷二叉樹 System.out.print("后根次序遍歷二叉樹： ");

13、postOrder(root); System.out.println(); public void postOrder(BinaryNode<T> p) /后根次序遍歷以p結(jié)點(diǎn)為根的子二叉樹，遞歸方法 if (p!=null) postOrder(p.left); postOrder(p.right); System.out.print(p.data.toString()+" "); /*5.二叉樹深拷貝，復(fù)制一棵二叉樹* public BinaryNode<T> copy(BinaryNode<T> p) if (p=null) re

14、turn null; BinaryNode<T> q = new BinaryNode<T>(p.data); q.left = copy(p.left); /復(fù)制左子樹，遞歸調(diào)用 q.right = copy(p.right); /復(fù)制右子樹，遞歸調(diào)用 return q; /返回建立子樹的根結(jié)點(diǎn) 4.測(cè)試類：/主類public class BinaryTree_make public static BinaryTree<String> make() /構(gòu)造給定的一棵二叉樹 /* A / B C / / D E F / G H */ BinaryTree&l

15、t;String> bitree=new BinaryTree<String>(); /創(chuàng)建空二叉樹 BinaryNode<String> child_f, child_d, child_b, child_c; child_d = new BinaryNode<String>("D", null, new BinaryNode<String>("G"); child_b = new BinaryNode<String>("B", child_d, null); chil

16、d_f = new BinaryNode<String>("F", new BinaryNode<String>("H"), null); child_c = new BinaryNode<String>("C", new BinaryNode<String>("E"), child_f); bitree.root = new BinaryNode<String>("A", child_b, child_c); return bitre

17、e; public static void main(String args) BinaryTree<String> bitree = make(); bitree.leaf1(); System.out.println("n"+"先根次序遍歷為："); bitree.preOrder(bitree.root); bitree.lrTran(); System.out.println("n"+"左右子樹交換后的先根次序遍歷為："); bitree.preOrder(bitree.root); System.out.println("n"+"中根次序遍歷為："); bitree.inOrder(bitree.root); System.out.println("n"+"后根次序遍歷為："); bitree.postOrder(bitree.root)