java二叉树代码

1、Java 语言课程设计（报告）题题 目：目： 二叉排序树设计与实现 学生姓名：学生姓名： 李倩、赵晶晶李倩、赵晶晶 学学 号：号： 201406014112、201406014144 院院 系：系： 基础科学学院信息技术系基础科学学院信息技术系 专业年级：专业年级： 软件工程软件工程 201401 指导教师：指导教师： 胡霖胡霖 2016 年年 7 月月 4 日日中国石油大学胜利学院java 程序设计课程大作业摘 要二叉树（Binary Tree，BT） ，它的数据模型较为抽象。 它或者是一棵空树；或者是左子树上结点比根节点小，而右子树上节点比根节点大的树。传统的教学方法无法将树的概念、算法和

2、数据模型直观且快速地呈现在课堂中，教师讲授、学生学习，都往往会事倍功半。本文对 BT 操作的过程进行设计，采用 java 语言编写程序，对二叉排序树的插入，删除，查询等操作进行了可视化实现。本文设计帮助初学者理解在算法执行过程中各种要素的变化状态，将 BT 的学习中大量的理论性概念、算法、数据和模型直观而且快速地呈现出来，以活泼、生动、全面的形式提高 BT 学习的环境质量。 关键词：关键词：二叉树；Java；设计中国石油大学胜利学院java 程序设计课程大作业ABSTRACTTree Binary, BT, its data model is more abstract. Maybe it i

3、s a hollow tree; or left sub tree root node node, and node root node on the right subtree of the tree. Traditional teaching methods cannot be tree concept, algorithm and data model is intuitive and fast render in the classroom, teachers teach, students learn, tend to get twice the result with half t

4、he effort. In this paper, the process of BT operation is designed, using java language program, the two fork sort tree insert, delete, query and other operations carried out a visual implementation. This paper designed to help beginners understand the various elements in the process of the change of

5、 state in the execution of the algorithm, the BT learning a lot of theory concept, algorithms, data and model intuitive and fast to show, in form of lively, vivid, comprehensive improve BT learning environment is the quality. Keywords：Binary Tree; Java; Design中国石油大学胜利学院java 程序设计课程大作业目 录第一章 绪论.11.1 课

6、题研究的背景.11.2 课题研究的目的.11.3 论文主要研究要求.1第二章 关键技术介绍.32.1 相关技术介绍.32.1.1 JDK .32.1.2 ECLIPSE.32.2 系统开发环境的配置.32.2.1 JDK 安装及配置.32.2.2 ECLIPSE.3第三章 详细设计.53.1 包层次.53.2 类图.63.3 流程图.73.3.1 查看模块.73.3.2 插入模块.103.3.3 查找模块.133.3.4 删除模块.153.3.5 遍历模块.193.3.6 总流程模块.25第四章 源代码.29第五章 心得体会.37参考文献.39中国石油大学胜利学院java 程序设计课程大作业第

7、 0 页 共 45 页 第一章 绪论1.1 课题研究的背景现实世界中很多算法处理起来比较复杂，这种时候我们就需要用到二叉树来帮助我们实现程序设计语言。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。1.2 课题研究的目的随着各种编程语言的发展，二叉树对学习程序设计、利用计算机解决实际问题特别重要；二叉树的各种复杂运算大都是建立在其三种遍历之上，因此掌握好二叉树的遍历算法是很有必要的。1.3 论文主要

8、研究要求本课题主要采用浏览器/服务器模式开发，通过 Windows 7+ Eclipse 的技术，实现了二叉排序树数据结构，包含二叉排序树的前序、中序和后序遍历，节点的插入、删除和查找等功能。在本课题论文中，第一章主要介绍了二叉树的背景、目的和要求。第二章中介绍了本课题所运用到关键的技术。第三章中主要介绍二叉树的需求分析。第四章中主要介绍数据库的设计。第五章主要对二叉树进行实现。第六章介绍了在编写代码和运行过程中所遇到的问题。中国石油大学胜利学院java 程序设计课程大作业第 1 页 共 45 页中国石油大学胜利学院java 程序设计课程大作业第 2 页 共 45 页第二章 关键技术介绍2.1

9、 相关技术介绍2.1.1 JDK JDK 是 JAVA 语言的软件开发安装包，主要用于移动设备、嵌入式设备上的 java应用程序。JDK 是整个 java 开发的核心，它包含了 java 的运行环境，JAVA 工具和JAVA 基础的类库1。2.1.2 EclipseEclipse 提供了对多重平台特性的支持。开发者可以使用他们感觉最舒适、最熟悉的平台，例如 Windows、Linux、MacOS 等。Eclipse 对每个平台都有其单独的图形工具包，这使得应用程序具有接近本地操作系统的外观和更好的性能2。2.2 系统开发环境的配置系统采用 Windows 7+Eclipse 作为开发环境，主要

10、配置如下：2.2.1 JDK 安装及配置本系统选用了 Windows 平台上的 JDK1.6，文件名为 jdk-6u13-windows-i586-p.exe，选择好安装路径直接安装该文件即可，安装目录为 F:java。接着来设置环境变量，在控制面板系统高级环境变量中设置 JAVA_HOME、Path、Classpath 三个环境变量，JAVA_HOME 的值为 F:java，Path 的值为 F:javabin，Classpath 的值为%JAVA_HOME% libdt.jar;%JAVA_HOME%libtools.jar。2.2.2 Eclipse解压到指定目录 Eclipse 后整合

11、 JDK，Window-Preferences-Java-Installed JREs-Add-Standard VM-指定 JRE home 为 JDK 的根目录-指定 JRE name。整合Tomcat 的 2 种方式，Server 面板-点击 No server are available. Click this link to create a new server.-选择 Apache 的 Tomcat 7.0-指定 Tomcat installation directory 为 Tomcat的根目录-指定 JRE 为安装好的 JDK 名称-Finish。将项目的发布到 webapp

12、s 目录下，双击 Server 面板的 Tomcat 服务器-选择 Use Tomcat installation-设置 Deploy path 为 webapps-关闭该页时保存。指定测试时运行的浏览器为 IE，修改 JSP 文件的字符编码集为 utf-8。最后设置编译和运行前自动存盘。中国石油大学胜利学院java 程序设计课程大作业第 3 页 共 45 页中国石油大学胜利学院java 程序设计课程大作业第 4 页 共 45 页第 3 章 详细设计3.1 包层次Node+iData:int+dData:double+leftChild:Node+righttChild:Node+displa

13、yNode():voidTree+root: Node+Tree():void+find(key:int):Node+insert(id:int;dd:double):void+delete(key:int):boolean+getSuccessor(delNode:Node):Node+traverse(traverseType:int):void+preOrder(localRoot:Node):void+inOrder(localRoot:Node):void+postOrder(localRoot:Node):void+displayTree():voidTreeApp+main():

14、void+getString():String+getChar:char+getInt():int中国石油大学胜利学院java 程序设计课程大作业第 5 页 共 45 页3.2 类图中国石油大学胜利学院java 程序设计课程大作业第 6 页 共 45 页3.3 流程图3.3.1 查看模块功能:主要实现查看二叉树所有结点。代码:public void displayTree() Stack globalStack = new Stack(); globalStack.push(root); int nBlanks = 32; /Blanks 空格 boolean isRowEmpty = fal

15、se ; /行空=flase System.out.println(.); while(isRowEmpty = false) Stack localStack = new Stack(); isRowEmpty = true; for(int j = 0;j nBlanks; j +) System.out.print( ); while(globalStack.isEmpty() = false) Node temp = (Node)globalStack.pop(); if(temp != null) System.out.print(temp.iData); localStack.pu

16、sh(temp.leftChild); localStack.push(temp.rightChild); if(temp.leftChild != null | temp.rightChild != null) isRowEmpty = false; else System.out.print(.); localStack.push(null); localStack.push(null); for(int j = 0; j nBlanks*2 - 2;j +) System.out.print( ); /结束当 globalStack 不为空 System.out.println(); n

17、Blanks /= 2; while(localStack.isEmpty() = false) 中国石油大学胜利学院java 程序设计课程大作业第 7 页 共 45 页 globalStack.push( localStack.pop() ); /结束 当 isRowEmpty false System.out.println(.nnn); /结束 displayTree() /结束 class Tree 截图：流程图：中国石油大学胜利学院java 程序设计课程大作业第 8 页 共 45 页中国石油大学胜利学院java 程序设计课程大作业第 9 页 共 45 页3.3.2 插入模块功能：主要

18、实现在二叉树中插入某个结点。代码： public void insert(int id ,double dd) Node newNode = new Node(); /插入新节点 newNode.iData = id; /新节点数据 newNode.dData = dd; if( root = null ) /根上没有节点 root = newNode; else Node current = root; /从根上 current 查找 Node parent; while( true ) parent = current; if(id current.iData) /到左 current =

19、 current.leftChild; if(current = null) /如果 line 结束 parent.leftChild = newNode; return ; /end if go left else /or go right current = current.rightChild; if(current = null) /如果 line 结束 parent.rightChild = newNode; return ; 中国石油大学胜利学院java 程序设计课程大作业第 10 页 共 45 页 截图：流程图：中国石油大学胜利学院java 程序设计课程大作业第 11 页 共 4

20、5 页中国石油大学胜利学院java 程序设计课程大作业第 12 页 共 45 页3.3.3 查找模块功能：主要实现查找某个结点是否存在。代码： public Node find(int key) /查找给定 key 的节点 Node current = root; /从根开始 while(current.iData != key) /当不匹配时 if(key current.iData) /到左 current = current.leftChild; else /到右 current = current.rightChild; if (current = null) /没找到 return

21、null; return current; /结束 find() 截图： 流程图：中国石油大学胜利学院java 程序设计课程大作业第 13 页 共 45 页中国石油大学胜利学院java 程序设计课程大作业第 14 页 共 45 页3.3.4 删除模块功能:主要实现二叉树结点的删除。代码:public boolean delete(int key) /删除给定 key 的节点 Node current = root; Node parent = root; boolean isLeftChild = true; while(current.iData != key) parent = curre

22、nt; if(key current.iData) isLeftChild = true; current = current.leftChild; else isLeftChild = false; current = current.rightChild; if(current = null) return false; /while 结束 /发现节点去删除 /如果没有子节点，直接删除 if(current.leftChild = null & current.rightChild = null) if (current = root) root = null; else if(i

23、sLeftChild) parent.leftChild = null; else parent.rightChild = null; /如果它没有右孩子，用左子树代替它 else if(current.rightChild = null) 中国石油大学胜利学院java 程序设计课程大作业第 15 页 共 45 页 if (current = root) root = current.leftChild; else if (isLeftChild) parent.leftChild = current.leftChild; else parent.rightChild = current.le

24、ftChild; /如果它没有左孩子，用右子树代替它 else if (current.leftChild = null) if (current = root) root = current.rightChild; else if(isLeftChild) parent.leftChild = current.rightChild; else parent.rightChild = current.rightChild; /两个孩子,所以用 inorder successor 代替 else /得到节点的 successor 删除(current) Node successor = getS

25、uccessor(current); /连接 current 代替父母继承 if(current = root) root = successor; else if (isLeftChild) parent.leftChild = successor; else parent.rightChild = successor; /连接到当前的左孩子的继承 successor.leftChild = current.leftChild; /结束 else two children /(successor 没有左孩子) return true; /end delete() /返回被删除的节点下的最大值

26、的节点 private Node getSuccessor(Node delNode) 中国石油大学胜利学院java 程序设计课程大作业第 16 页 共 45 页 Node successorParent = delNode; Node successor = delNode; Node current = delNode.rightChild; /go to right child while(current != null) /直到 current 没有左孩子 successorParent = successor; successor = current; current = curre

27、nt.leftChild; /go to left child if (successor != delNode.rightChild) /如果 successor 没有右孩子 , make connections successorParent.leftChild = successor.rightChild; /s 与p 断掉 successor.rightChild = delNode.rightChild; /s 与被删除的右孩子连接 return successor; 截图：流程图：中国石油大学胜利学院java 程序设计课程大作业第 17 页 共 45 页 root=current.

28、leftChild;root = current.rightChild;开始是否有子节点是否有两节点是否有左孩子successorParent = successor;successor = current;current = current.leftChild;删除成功Sr 是否=drsuccessorParent.leftChild = successor.rightChild; successor.rightChild= delNode.rightChild;结束否否否否是是是是current = rootisLeftChildparent.leftChild = current.lef

29、tChild;parent.rightChild = current.leftChild;current = rootisLeftChildparent.rightChild = current.rightChild;parent.leftChild = current.rightChild;否否否否是是是是中国石油大学胜利学院java 程序设计课程大作业第 18 页 共 45 页3.3.5 遍历模块功能：实现二叉树的前中后序遍历。3.3.5.1 前序遍历代码：private void preOrder(Node localRoot) if (localRoot != null) System

30、.out.print(localRoot.iData + ); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); 截图：中国石油大学胜利学院java 程序设计课程大作业第 19 页 共 45 页流程图：开始根节点是否为空System.out.print(localRoot.iData + ); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); 结束前序遍历完成否是中国石油大学胜利学院java 程序设计课程大作业第 20 页 共 45 页3.3.

31、5.23.3.5.2 中序遍历中序遍历代码：private void inOrder(Node localRoot) if(localRoot != null) inOrder(localRoot.leftChild); System.out.print(localRoot.iData + ); inOrder(localRoot.rightChild); 中国石油大学胜利学院java 程序设计课程大作业第 21 页 共 45 页截图：流程图：开始根节点是否为空preOrder(localRoot.leftChild); System.out.print(localRoot.iData + )

32、;preOrder(localRoot.rightChild); 结束中序遍历完成否是中国石油大学胜利学院java 程序设计课程大作业第 22 页 共 45 页3.3.5.3 后序遍历代码： private void postOrder(Node localRoot) if (localRoot != null) postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); System.out.print(localRoot.iData + ); 中国石油大学胜利学院java 程序设计课程大作业第 23 页 共 45 页截图

33、：流程图：开始根节点是否为空preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); System.out.print(localRoot.iData + );结束后序遍历完成否是中国石油大学胜利学院java 程序设计课程大作业第 24 页 共 45 页3.3.6 总流程模块功能：实现功能的选择。代码： public static void main(String args) throws IOException int value ; Tree theTree = new Tree(); theTree.insert(49,

34、 1.0); theTree.insert(25, 2.0); theTree.insert(77, 3.0); theTree.insert(12, 4.0); theTree.insert(37, 5.0); theTree.insert(43, 6.0); theTree.insert(30, 7.0); theTree.insert(33, 8.0); 中国石油大学胜利学院java 程序设计课程大作业第 25 页 共 45 页 theTree.insert(88, 9.0); theTree.insert(93, 10.0); theTree.insert(100, 11.0); wh

35、ile( true ) System.out.println(*欢迎来到二叉树的世界*n); System.out.println(请选择运行方式：); System.out.println(1.显示二叉树请输入“s”：); System.out.println(2.插入二叉树请输入“i”：); System.out.println(3.查找二叉树请输入“f”：); System.out.println(4.删除二叉树请输入“d”：); System.out.println(5.遍历二叉树请输入“t”：); int choice = getChar(); switch( choice ) ca

36、se s: theTree.displayTree(); break; case i: System.out.print(输入要插入的值：); value = getInt(); theTree.insert(value, value + 0.5); break; case f: System.out.print(输入要查找的值：); value = getInt(); Node found = theTree.find(value); if(found != null) System.out.print(找到:); found.displayNode(); System.out.printl

37、n(); else 中国石油大学胜利学院java 程序设计课程大作业第 26 页 共 45 页 System.out.print(未找到 ); System.out.print(value); break; case d: System.out.print(输入要删除的值：); value = getInt(); boolean didDelete = theTree.delete(value); if(didDelete) System.out.println(删除 + value); else System.out.print(未删除 ); System.out.println(value

38、); break; case t: System.out.print(请输入需要遍历的类型:/n1：前序遍历n2：中序遍历n3：后序遍历n); value = getInt(); theTree.traverse(value); break; default: System.out.print(无效的输入/n); /结束 switch 循环 /结束 while 循环 /结束 main() 截图：中国石油大学胜利学院java 程序设计课程大作业第 27 页 共 45 页总流程图：中国石油大学胜利学院java 程序设计课程大作业第 28 页 共 45 页中国石油大学胜利学院java 程序设计课程大

39、作业第 29 页 共 45 页中国石油大学胜利学院java 程序设计课程大作业第 30 页 共 45 页第四章 源代码 import java.io.*; import java.util.*; class Node public int iData; /数据项（key） public double dData; /数据项 public Node leftChild; /节点的左孩子 public Node rightChild; /节点的右孩子 public void displayNode() /显示自己 System.out.print(); System.out.print(iData

40、); System.out.print(,); System.out.print(dData); System.out.print(); /结束 class Node class Tree private Node root; /树的第一个节点 public Tree() root = null; /树上没有节点 public Node find(int key) /查找给定 key 的节点 Node current = root; /从根开始 while(current.iData != key) /当不匹配时 if(key current.iData) /到左 current = curr

41、ent.leftChild; else /到右 current = current.rightChild; if (current = null) /没找到 return null; return current; /结束 find() public void insert(int id ,double dd) Node newNode = new Node(); /插入新节点 中国石油大学胜利学院java 程序设计课程大作业第 31 页 共 45 页 newNode.iData = id; /新节点数据 newNode.dData = dd; if( root = null ) /根上没有节

42、点 root = newNode; else Node current = root; /从根上 current 查找 Node parent; while( true ) parent = current; if(id current.iData) /到左 current = current.leftChild; if(current = null) /如果 line 结束 parent.leftChild = newNode; return ; /end if go left else /or go right current = current.rightChild; if(curren

43、t = null) /如果 line 结束 parent.rightChild = newNode; return ; public boolean delete(int key) /删除给定 key 的节点 Node current = root; Node parent = root; boolean isLeftChild = true; while(current.iData != key) parent = current; if(key current.iData) isLeftChild = true; current = current.leftChild; 中国石油大学胜利学

44、院java 程序设计课程大作业第 32 页 共 45 页 else isLeftChild = false; current = current.rightChild; if(current = null) return false; /while 结束 /发现节点去删除 /如果没有子节点，直接删除 if(current.leftChild = null & current.rightChild = null) if (current = root) root = null; else if(isLeftChild) parent.leftChild = null; else pare

45、nt.rightChild = null; /如果它没有右孩子，用左子树代替它 else if(current.rightChild = null) if (current = root) root = current.leftChild; else if (isLeftChild) parent.leftChild = current.leftChild; else parent.rightChild = current.leftChild; /如果它没有左孩子，用右子树代替它 else if (current.leftChild = null) if (current = root) ro

46、ot = current.rightChild; else if(isLeftChild) parent.leftChild = current.rightChild; else parent.rightChild = current.rightChild; /两个孩子,所以用 inorder successor 代替 else /得到节点的 successor 删除(current) 中国石油大学胜利学院java 程序设计课程大作业第 33 页 共 45 页 Node successor = getSuccessor(current); /连接 current 代替父母继承 if(curre

47、nt = root) root = successor; else if (isLeftChild) parent.leftChild = successor; else parent.rightChild = successor; /连接到当前的左孩子的继承 successor.leftChild = current.leftChild; /结束 else two children /(successor 没有左孩子) return true; /end delete() /返回被删除的节点下的最大值的节点 private Node getSuccessor(Node delNode) No

48、de successorParent = delNode; Node successor = delNode; Node current = delNode.rightChild; /go to right child while(current != null) /直到 current 没有左孩子 successorParent = successor; successor = current; current = current.leftChild; /go to left child if (successor != delNode.rightChild) /如果 successor 没

49、有右孩子 , make connections successorParent.leftChild = successor.rightChild; /s 与 p 断掉 successor.rightChild = delNode.rightChild; /s 与被删除的右孩子连接 return successor; public void traverse(int traverseType) switch(traverseType) case 1: System.out.print(/n 前序遍历:); preOrder(root); break; case 2: System.out.pri

50、nt(/n 中序遍历: ); inOrder(root); 中国石油大学胜利学院java 程序设计课程大作业第 34 页 共 45 页 break; case 3: System.out.print(/n 后序遍历:); postOrder(root); break; System.out.println(); private void preOrder(Node localRoot) if (localRoot != null) System.out.print(localRoot.iData + ); preOrder(localRoot.leftChild); preOrder(loca

51、lRoot.rightChild); private void inOrder(Node localRoot) if(localRoot != null) inOrder(localRoot.leftChild); System.out.print(localRoot.iData + ); inOrder(localRoot.rightChild); private void postOrder(Node localRoot) if (localRoot != null) postOrder(localRoot.leftChild); postOrder(localRoot.rightChil

52、d); System.out.print(localRoot.iData + ); public void displayTree() Stack globalStack = new Stack(); globalStack.push(root); int nBlanks = 32; /Blanks 空格 boolean isRowEmpty = false ; /行空=flase System.out.println(.); while(isRowEmpty = false) 中国石油大学胜利学院java 程序设计课程大作业第 35 页 共 45 页 Stack localStack = n

53、ew Stack(); isRowEmpty = true; for(int j = 0;j nBlanks; j +) System.out.print( ); while(globalStack.isEmpty() = false) Node temp = (Node)globalStack.pop(); if(temp != null) System.out.print(temp.iData); localStack.push(temp.leftChild); localStack.push(temp.rightChild); if(temp.leftChild != null | te

54、mp.rightChild != null) isRowEmpty = false; else System.out.print(.); localStack.push(null); localStack.push(null); for(int j = 0; j nBlanks*2 - 2;j +) System.out.print( ); /结束当 globalStack 不为空 System.out.println(); nBlanks /= 2; while(localStack.isEmpty() = false) globalStack.push( localStack.pop()

55、); /结束 当 isRowEmpty false System.out.println(.nnn); /结束 displayTree() /结束 class Tree class TreeApp public static void main(String args) throws IOException int value ; Tree theTree = new Tree(); theTree.insert(49, 1.0); theTree.insert(25, 2.0); theTree.insert(77, 3.0); theTree.insert(12, 4.0); theTre

56、e.insert(37, 5.0); 中国石油大学胜利学院java 程序设计课程大作业第 36 页 共 45 页 theTree.insert(43, 6.0); theTree.insert(30, 7.0); theTree.insert(33, 8.0); theTree.insert(88, 9.0); theTree.insert(93, 10.0); theTree.insert(100, 11.0); while( true ) System.out.println(*欢迎来到二叉树的世界*n); System.out.println(请选择运行方式：); System.out.

57、println(1.显示二叉树请输入“s”：); System.out.println(2.插入二叉树请输入“i”：); System.out.println(3.查找二叉树请输入“f”：); System.out.println(4.删除二叉树请输入“d”：); System.out.println(5.遍历二叉树请输入“t”：); int choice = getChar(); switch( choice ) case s: theTree.displayTree(); break; case i: System.out.print(输入要插入的值：); value = getInt()

58、; theTree.insert(value, value + 0.5); break; case f: System.out.print(输入要查找的值：); value = getInt(); Node found = theTree.find(value); if(found != null) System.out.print(找到:); found.displayNode(); System.out.println(); else System.out.print(未找到 ); System.out.print(value); break; case d: System.out.print(输入要删除的值：); 中国石油大学胜利学院java 程序设计课程大作业第 37 页 共 45 页 value = getInt(); boolean didDelete = theTree.delete(val