《数据结构实验三.doc》由会员分享，可在线阅读，更多相关《数据结构实验三.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验报告项目名称 专业班级 学 号 姓 名 实验成绩：批阅教师：年 月 日实验3二叉树的基本操作实验学时： 实验地点： 实验日期： 实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下7个内容：实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下7个内容：1 需求分析以二叉链表作存储结构，编写程序，实现如下的功能：1、根据输入的数据建立一个二叉树；2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果3、采用非递归的编程方法，分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和最小值。2概要设计创建节点，二叉树，实现前序、中序、
2、后序遍历，写节点，度数1，度数2和叶子节点数程序，写主程序3详细设计节点有数据，左右孩子指针，二叉树创建采用递归，遍历程序等依据书上的算法写4调试分析大小写错误，少些后括号等低级错误5用户使用说明按照提示输入数据，无左孩子或右孩子的输入#号6测试结果 从键盘上输入一个字符a从键盘上输入一个字符b从键盘上输入一个字符#从键盘上输入一个字符#从键盘上输入一个字符c从键盘上输入一个字符d从键盘上输入一个字符#从键盘上输入一个字符#从键盘上输入一个字符e从键盘上输入一个字符#从键盘上输入一个字符#Pre Order a b c d eIn Order b a d c ePost Order b d e
3、 c anumbersOfNode:5numbersOfLeafs:3numbersOfDegree2:2numbersOfDegree1:0maxOfNode:eminOfNode:aProcess completed.7附录/* * (#)BTree.java * * * author * version 1.00 2013/4/22 */import java.util.Scanner;public class BTree public BNode root; public BTree() public BNode createBTree()char ch;BNode bt;System
4、.out.println(从键盘上输入一个字符);Scanner scanner = new Scanner(System.in);String s1 = scanner.nextLine();ch=s1.charAt(0);/从键盘上输入一个字符if (ch = #) return null;/空格作为结束标志elsebt= new BNode();/产生新结点bt.data=ch;bt.lChild= createBTree();bt.rChild= createBTree();return (bt); public void preTravel(BNode t)if (t != null
5、) System.out.println( +t.data);preTravel(t.lChild);preTravel(t.rChild); /前序 public void inTravel(BNode t)if (t != null) inTravel(t.lChild);System.out.println( +t.data);inTravel(t.rChild); /中序 public void postTravel(BNode t)if (t != null) postTravel(t.lChild);postTravel(t.rChild);System.out.println(
6、+t.data); /后序 public int numbersOfNode(BNode t) int i; if(t=null) i=0; else if(t.lChild=null&t.rChild=null) i=1; else i=numbersOfNode(t.lChild)+numbersOfNode(t.rChild)+1; return i; /节点个数 public int numbersOfLeafs(BNode t) int i; if(t=null) i=0; else if(t.lChild=null&t.rChild=null) i=1; else i=number
7、sOfLeafs(t.lChild)+numbersOfLeafs(t.rChild); return i; /叶子个数 public int numbersOfDegree2(BNode t) int i=numbersOfLeafs(t)-1; return i; /度为二的个数 public int numbersOfDegree1(BNode t) int i=numbersOfNode(t)-2*numbersOfLeafs(t)+1; return i; /度为一的个数 public char maxOfNode(BNode t) char max=u0000; if(t!=nul
8、l) max=t.data; if(maxmaxOfNode(t.lChild) max=maxOfNode(t.lChild); if(maxminOfNode(t.lChild) min=minOfNode(t.lChild); if(minminOfNode(t.rChild) min=minOfNode(t.rChild); return min; /最小值public static void main(String args)BTree tt = new BTree();tt.root = tt.createBTree();System.out.println(Pre Order);
9、tt.preTravel(tt.root);System.out.println(In Order);tt.inTravel(tt.root);System.out.println(Post Order);tt.postTravel(tt.root);System.out.println(numbersOfNode:+tt.numbersOfNode(tt.root);System.out.println(numbersOfLeafs:+tt.numbersOfLeafs(tt.root);System.out.println(numbersOfDegree2:+tt.numbersOfDeg
10、ree2(tt.root);System.out.println(numbersOfDegree1:+tt.numbersOfDegree1(tt.root);System.out.println(maxOfNode:+tt.maxOfNode(tt.root); System.out.println(minOfNode:+tt.minOfNode(tt.root);/* * (#)BNode.java * * * author * version 1.00 2013/4/22 */public class BNode public char data;public BNode lChild;public BNode rChild; public BNode() public BNode(char data)this.data = data;this.lChild = null;this.rChild = null;public BNode(char data,BNode l,BNode r)this.data = data;this.lChild = l;this.rChild = r;