(此文档为word 格式，下载后您可任意编辑修改！)
山东建筑大学计算机科学与技术学院
课程设计说明书
题 目： 双向链表的创建和操作的实现
树的创建及相关操作的实现
课 程： 数据结构与算法
院 （部）： 计算机学院
专 业： 网络工程
班 级： 网络101
学生姓名： 王天未
指导教师： 伊静
目 录
课程设计任务书1 .............................................. II 课程设计任务书2 ............................................. III
双向循环链表的创建及相关操作的实现 ............................. 5
一、问题描述 ............................................... 5
二、数据结构 ............................................... 5
三、逻辑设计 ............................................... 5
四、编码 ................................................... 6
五、 测试数据 ............................................. 11
六、测试情况 .............................................. 12
树的创建及相关操作的实现 ...................................... 15
一、问题描述 .............................................. 15
二、数据结构 .............................................. 15
三、逻辑设计 .............................................. 16
四、编码 .................................................. 18
五、 测试数据 ............................................. 27
六、测试情况 .............................................. 27
结 论 ........................................................ 29
参考文献 ..................................................... 30
课程设计指导教师评语 . ......................................... 31
山东建筑大学计算机科学与技术学院
课程设计任务书1
指导教师（签字）： 教研室主任（签字）
山东建筑大学计算机科学与技术学院
课程设计任务书2
指导教师（签字）： 教研室主任（签字）
双向循环链表的创建及相关操作的实现
一、问题描述
1、每个节点的next 域构成了一个循环单链表
2、每个节点的prev 域构成了另一个循环单链表
二、数据结构
针对所处理的树：
1、画出双向循环链表的存储结构
2、使用所选用语言的功能，描述该存储结构的实现
private static class Node {
} AnyType data; Node prev; Node next;
三、逻辑设计
1、总体思路
对于双向循环链表，建立一个空表，然后实现双向循环链表的插入，删除操作。
为了便于逆置的操作，选择建立一个带头节点的双向循环链表，插入第一个节点和插入最后一个节点，只需要在0号位置和size()位置插入节点就行。
2、模块划分（以图示的方法给出各个函数的调用关系）
3、函数或类的具体定义和功能
class Node//节点类定义
public class DlList //循环链表主类
public boolean add(int idex, AnyType x)//链表插入操作
public AnyType remove(int idex )//链表删除操作
private void inverse()//链表逆置
四、编码
import java.util.Scanner;
class Node{
public AnyType data ;
public Node prev ;
public Node next ;
public Node(){
data =null ;
prev =null ;
next =null ;
}
public Node(AnyType d){
data =d;
prev =null ;
next =null ;
}
public Node(AnyType d,Node p,Node n){ data =d;
prev =p;
next =n;
}
}//节点类
public class DlList {
private Node theSize ;
}//设定表的长度
public boolean add(AnyType x) {
add(theSize , x); return true ; }//链表输入操作 public boolean add(int idex, AnyType x) { } private void addBefore(Node p, AnyType x) { boolean flag; if (idex theSize ) {//判断插入的位置是否大于0 System. out .println(" 您输入的要插入元素的位置不正确!" ); flag = false ; } else { } if (flag) { Node p; p = getNode(idex); addBefore(p, x); flag = true ; }//插入操作 return flag;
Node newNode = new Node(x, p.prev , p); newNode. prev . next = newNode; p. prev = newNode; theSize ++; }//插入方法
public AnyType remove(int idex ) {
return remove(getNode(idex));
}
private AnyType remove( Node p ){
p. prev . next =p.next ;
p. next . prev =p.prev ;
theSize --;
return p.data ;
}//删除操作
private void inverse(){
Node p,q,l;
p=("getNode idex:"+idex+";size:"+size());
if (idex
{
p= p;
}//查找结点位置
public void print(){
for (int i=0;i
System. out .print(getNode(i).data +" ");
System. out .println();
}//结果输出
public void choose(){
System. out .println("1. 插入第i 个节点" );
System. out .println("2. 删除第i 个节点" );
System. out .println("3. 插入第一个节点" );
System. out .println("4. 插入最后一个节点" );
System. out .println("5. 逆置" );
}//选择操作项
public static void main(String[] args){
DlList dl=new DlList();
Scanner sc=new Scanner(System.in );
int xuanze;
System. out .println(" 请输入链表的元素的个数(大于0个) ：" ); int n=sc.nextInt();
System. out .println(" 请输入链表的" +n+" 个元素：" );
for (int i=1;i
} int l=sc.nextInt(); dl.add(l);//链表元素输入
System. out .println(" 您输入的链表为：" );
dl.print();//调用print 方法，提示操作。
System. out .println(" 请选择操作项：" );
dl.choose();//调用choose ，选择操作。
while (true ){
xuanze=sc.nextInt();
switch (xuanze){
case 1:
System. out .println(" 请输入要插入的位置下标和数据：" ); int idex=sc.nextInt();
int data=sc.nextInt();
dl.add(idex, data);
dl.print();
break ;
case 2:
System. out .println(" 请输入要删除节点的下标：" ); int idex1=sc.nextInt();
dl.remove(idex1);
dl.print();
break ;
case 3:
System. out .println(" 请输入插入第一个节点的元素：" ); int data1=sc.nextInt();
dl.add(0,data1);
dl.print();
break ;
case 4:
System. out .println(" 请输入插入最后位置的元素：" ); int data2=sc.nextInt();
dl.add(dl.size(), data2);
dl.print();
break ;
case 5:
dl.inverse();
dl.print();
break ;
default :
System. out .println(" 你的输入有误，请重新输入！" ); break ;
}
}
}
}
五、测试数据
1、对每个函数的测试数据
链表中的元素插入为1、2、3、4、5
插入第二个结点的元素为6
删除第二个节点的位置的元素6
插入第一个节点的元素为7
插入最后一个节点的元素为6
逆置链表
2、对程序整体的测试数据
输入元素为1、2、3、4、5的双向循环链表
六、测试情况
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
1
请输入要插入的位置下标和数据：
2
6
1 2 6 3 4 5
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
2
请输入要删除的位置下标和数据：
2
6
1 2 3 4 5
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
请输入插入第一个节点的元素：
7
7 1 2 3 4 5
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
4
请输入插入最后位置的元素：
6
1 2 3 4 5 6
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
5
5 4 3 2 1
树的创建及相关操作的实现
一、问题描述
1. 先遍序遍历建树
2、遍历方法举例：
二、数据结构
针对所处理的树：
1、画出存储结构
2、使用所选用语言的功能，实现上述的该存储结构
public static class BTNode {
}
private AnyType data; private BTNode parent; private BTNode leftNode; private BTNode rightNode;
三、逻辑设计
1、总体思路
首先建立节点类，然后构造BinaryTree （），再构造先序遍历建树方法，层次遍历建树方法，层次遍历树的方法，统计叶子结点个数方法，交换子树方法，再调试。
2、模块划分（以图示的方法给出各个函数的调用关系）
3、函数或类的具体定义和功能
BiTNode()//节点类定义
public BiTNode creatTree(AnyType[] a)//先序建树方法定义 private void creatPathBinaryTree(AnyType[] a)//层次遍历建树定义
public void pathOrder()//层次遍历方法定义 public int countLeafNode()// 统计叶子节点个数方法定义
四、编码
1. 结点类定义
package kcsj;
public class BiTNode implements Comparable {
AnyType data ; BiTNode left , right ; int weight ; BiTNode() {
data = null ;
left = right = null ;
}
BiTNode(AnyType thedata) {
data = thedata;
left = right = null ;
}
BiTNode(AnyType thedata, BiTNode lt, BiTNode rt) { data = thedata;
left = lt;
right = rt;
}
public BiTNode getLeft() {
return left ;
}
public BiTNode getRight() {
return right ;
}
public Object getData() {
return data ;
}
public double getWight() {
return weight ;
}
@Override
public int compareTo(BiTNode o) {
if (o.getWight() > this .getWight())
return 1;
if (o.getWight()
} } return -1; return 0;
2.BinaryTree()构造
package kcsj;
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree> {
AnyType[] pre , in ; BiTNode rootNode = new BiTNode(); int count = 0; public BinaryTree() { } public BinaryTree(AnyType rootNodeItem) { } public BinaryTree(BiTNode t) { } rootNode = t; rootNode . data = rootNodeItem; rootNode . left = rootNode . right = null ; rootNode = null ;
//1. 先序遍历建树
public BiTNode creatTree(AnyType[] a) { } return rootNode = creatBinaryTree(a);
private BiTNode creatBinaryTree(AnyType[] a) {
BiTNode p = null ; if (count
} } count ++; if (data != null ) { } p = new BiTNode((AnyType) data); p. left = creatTree(a); p. right = creatTree(a); return p;
//1.层次遍历排序建树
public void creatPathTree(AnyType[] a) { } private void creatPathBinaryTree(AnyType[] a) { Queue q = new LinkedList(); BiTNode node = new BiTNode(a[0]); rootNode = node; q.offer(node); int i = 1; while (i
} } } } node = new BiTNode(a[i]); q.element().right = node; q.offer(q.element().right ); q.poll(); i++; //2.实现二叉树的层次遍历 public void pathOrder() { } public void pathOrder(BiTNode t) { } // 先序遍历 public void preOrder() { Queue q = new LinkedList(); q.offer(t); while (!q.isEmpty()) { } if (q.element().left != null ) q.offer(q.element().left ); if (rootNode != null ) pathOrder(rootNode ); if (q.element().right != null ) q.offer(q.element().right ); System. out .print(q.poll().data + " ");
} preOrder(rootNode );
private void preOrder(BiTNode t) {
if (t != null ) {
System. out .print(t.data +" ");
preOrder(t.left );
preOrder(t.right );
}
}
// 统计节点的个数
public int countNode() {
return countNode(rootNode );
}
private int countNode(BiTNode t) {
int m, n;
if (t == null )
return 0;
m = countNode(t.left );
n = countNode(t.right );
return m + n + 1;
}
// 3.统计叶子节点个数（递归）
public int countLeafNode() {
return countLeafNode(rootNode );
}
private int countLeafNode(BiTNode t) {
int m = 0, n = 0;
if (t == null )
return 0;
if (t.left == null && t.right == null ) {
return 1;
}
m = countLeafNode(t.left );
n = countLeafNode(t.right );
return m + n;
}
// 4.将二叉树左+右子树相互交换（递归）
public void exchangeTree() {
if (rootNode != null ) {
exchangeTree(rootNode );
}
}
private BiTNode exchangeTree(BiTNode t) { if (t != null ) {
BiTNode p = t.right ;
t. right = t.left ;
t. left = p;
exchangeTree(t.right );
exchangeTree(t.left );
}
return t;
}
// 计算树的深度
public int depth() {
return depth(rootNode );
private int depth(BiTNode t) { // 返回二叉树的深度 } //横向输出树状图 int depthleft, depthright; if (t == null ) return 0; depthleft = depth(t.left ); depthright = depth(t.right ); return Math.max (depthleft, depthright) + 1;
public void showTree(BiTNode t,int n){
}
}
3. 测试函数
package kcsj;
public class Test {
public static void pln(Object o) { } public static void main(String[] args) { System. out .println(o); if (t==null ) return ; showTree(t.right ,++n); for (int i = 0; i
Character[] charsPre = { 'a' , 'b' , 'd' , null , null , null , 'c' , 'e' ,
null , null , 'f' }; Character[] charsPath = { 'a' , 'b' , 'c' , 'd' , null , 'e' , 'f' }; pln (" 先序建树：{'a','b','d',null,null,null,'c','e',null,null,'f'}");
bt.creatTree(charsPre); pln (" 层序遍历结果：" ); bt.pathOrder(); pln (" "); pln (" 树图为(横向) ：" ); bt.showTree(bt.rootNode , 1); pln (" "); pln (" 层序建树：{'a','b','c','d',null,'e','f'}"); bt.creatPathTree(charsPath); pln (" 先序遍历结果：" ); bt.preOrder(); pln (" "); pln (" 树图为(横向) ：" ); bt.showTree(bt.rootNode , 1); pln (" "); pln (" 叶子节点数：" + bt.countLeafNode()); pln (" 交换后层次遍历结果：" ); bt.exchangeTree(); bt.pathOrder(); pln (" ");
} pln bt.showTree(bt.rootNode , 1); pln (" "); pln (" 深度为：" + bt.depth()); }
五、测试数据
1、对每个函数的测试数据
利用线序遍历和层次遍历分别建树a b c d e f
2、对程序整体的测试数据
a b c d e f
六、测试情况
先序建树：{'a','b','d',null,null,null,'c','e',null,null,'f'} 层序遍历结果：
a b c d e f
树图为(横向) ：
f
c
e
a
b
d
层序建树：{'a','b','c','d',null,'e','f'}
先序遍历结果：
a b d c e f
树图为(横向) ：
f
c
e
a
b
d
叶子节点数：3
交换后层次遍历结果：
a c b f e d
树图为(横向) ：
d
b
a
e
c
f
深度为：3
结 论
在课程设计中，遇到最多的问题便是对一个方法思想的转换。在这两周的课程设计中，让我学会如何思考一个树的存储结构，如何创建，各种遍历的思想需要怎样的代码实现。总而言之，两个字，思考。
在课程设计时，思想问题一直是我进度缓慢的原因，对于层次遍历建树的时候的思想一直拐不过弯，不知道该以什么样的方式建立左右子树。最终在同学的讲解下，理解了建树的方法。首先以队列的形式，传进根节点。再判断输入数组中是否存在根节点的左子树，如果存在则创建左孩子并将数据压入队列中。而右子树为左子树加一，故而在设置右子树的范围时，需要小于输入数组的长度减一，再以同样的方法判断是否存在右子树，存在则建立右孩子并将数据压入队列。
这次课程设计明白的远远不止这些，对于子树的交换，是我对于数据结构的认知茅塞顿开，发现原来自己以前真的一点都没明白这门课程到底是干嘛的，如今才清晰地明白这门课程要的是对数据的结构的思考。
发现自己的数据结构设计还是很弱，对于很多方法都不熟悉，以后希望能有更多的机会联系数据结构，让自己得到提升。
参考文献
[1] 王世民 JAVA 数据结构与算法分析[M] 北京：清华大学出版社, 2004-
山东建筑大学计算机科学与技术学院
课程设计指导教师评语
指导教师评语（包括工作态度，遵守纪律；基本理论、知识、技能；独立工作能力和分析解决问题的能力；完成任务情况及水平）：
学生成绩（百分制）：
指导教师签名： 年 月 日
(此文档为word 格式，下载后您可任意编辑修改！)
山东建筑大学计算机科学与技术学院
课程设计说明书
题 目： 双向链表的创建和操作的实现
树的创建及相关操作的实现
课 程： 数据结构与算法
院 （部）： 计算机学院
专 业： 网络工程
班 级： 网络101
学生姓名： 王天未
指导教师： 伊静
目 录
课程设计任务书1 .............................................. II 课程设计任务书2 ............................................. III
双向循环链表的创建及相关操作的实现 ............................. 5
一、问题描述 ............................................... 5
二、数据结构 ............................................... 5
三、逻辑设计 ............................................... 5
四、编码 ................................................... 6
五、 测试数据 ............................................. 11
六、测试情况 .............................................. 12
树的创建及相关操作的实现 ...................................... 15
一、问题描述 .............................................. 15
二、数据结构 .............................................. 15
三、逻辑设计 .............................................. 16
四、编码 .................................................. 18
五、 测试数据 ............................................. 27
六、测试情况 .............................................. 27
结 论 ........................................................ 29
参考文献 ..................................................... 30
课程设计指导教师评语 . ......................................... 31
山东建筑大学计算机科学与技术学院
课程设计任务书1
指导教师（签字）： 教研室主任（签字）
山东建筑大学计算机科学与技术学院
课程设计任务书2
指导教师（签字）： 教研室主任（签字）
双向循环链表的创建及相关操作的实现
一、问题描述
1、每个节点的next 域构成了一个循环单链表
2、每个节点的prev 域构成了另一个循环单链表
二、数据结构
针对所处理的树：
1、画出双向循环链表的存储结构
2、使用所选用语言的功能，描述该存储结构的实现
private static class Node {
} AnyType data; Node prev; Node next;
三、逻辑设计
1、总体思路
对于双向循环链表，建立一个空表，然后实现双向循环链表的插入，删除操作。
为了便于逆置的操作，选择建立一个带头节点的双向循环链表，插入第一个节点和插入最后一个节点，只需要在0号位置和size()位置插入节点就行。
2、模块划分（以图示的方法给出各个函数的调用关系）
3、函数或类的具体定义和功能
class Node//节点类定义
public class DlList //循环链表主类
public boolean add(int idex, AnyType x)//链表插入操作
public AnyType remove(int idex )//链表删除操作
private void inverse()//链表逆置
四、编码
import java.util.Scanner;
class Node{
public AnyType data ;
public Node prev ;
public Node next ;
public Node(){
data =null ;
prev =null ;
next =null ;
}
public Node(AnyType d){
data =d;
prev =null ;
next =null ;
}
public Node(AnyType d,Node p,Node n){ data =d;
prev =p;
next =n;
}
}//节点类
public class DlList {
private Node theSize ;
}//设定表的长度
public boolean add(AnyType x) {
add(theSize , x); return true ; }//链表输入操作 public boolean add(int idex, AnyType x) { } private void addBefore(Node p, AnyType x) { boolean flag; if (idex theSize ) {//判断插入的位置是否大于0 System. out .println(" 您输入的要插入元素的位置不正确!" ); flag = false ; } else { } if (flag) { Node p; p = getNode(idex); addBefore(p, x); flag = true ; }//插入操作 return flag;
Node newNode = new Node(x, p.prev , p); newNode. prev . next = newNode; p. prev = newNode; theSize ++; }//插入方法
public AnyType remove(int idex ) {
return remove(getNode(idex));
}
private AnyType remove( Node p ){
p. prev . next =p.next ;
p. next . prev =p.prev ;
theSize --;
return p.data ;
}//删除操作
private void inverse(){
Node p,q,l;
p=("getNode idex:"+idex+";size:"+size());
if (idex
{
p= p;
}//查找结点位置
public void print(){
for (int i=0;i
System. out .print(getNode(i).data +" ");
System. out .println();
}//结果输出
public void choose(){
System. out .println("1. 插入第i 个节点" );
System. out .println("2. 删除第i 个节点" );
System. out .println("3. 插入第一个节点" );
System. out .println("4. 插入最后一个节点" );
System. out .println("5. 逆置" );
}//选择操作项
public static void main(String[] args){
DlList dl=new DlList();
Scanner sc=new Scanner(System.in );
int xuanze;
System. out .println(" 请输入链表的元素的个数(大于0个) ：" ); int n=sc.nextInt();
System. out .println(" 请输入链表的" +n+" 个元素：" );
for (int i=1;i
} int l=sc.nextInt(); dl.add(l);//链表元素输入
System. out .println(" 您输入的链表为：" );
dl.print();//调用print 方法，提示操作。
System. out .println(" 请选择操作项：" );
dl.choose();//调用choose ，选择操作。
while (true ){
xuanze=sc.nextInt();
switch (xuanze){
case 1:
System. out .println(" 请输入要插入的位置下标和数据：" ); int idex=sc.nextInt();
int data=sc.nextInt();
dl.add(idex, data);
dl.print();
break ;
case 2:
System. out .println(" 请输入要删除节点的下标：" ); int idex1=sc.nextInt();
dl.remove(idex1);
dl.print();
break ;
case 3:
System. out .println(" 请输入插入第一个节点的元素：" ); int data1=sc.nextInt();
dl.add(0,data1);
dl.print();
break ;
case 4:
System. out .println(" 请输入插入最后位置的元素：" ); int data2=sc.nextInt();
dl.add(dl.size(), data2);
dl.print();
break ;
case 5:
dl.inverse();
dl.print();
break ;
default :
System. out .println(" 你的输入有误，请重新输入！" ); break ;
}
}
}
}
五、测试数据
1、对每个函数的测试数据
链表中的元素插入为1、2、3、4、5
插入第二个结点的元素为6
删除第二个节点的位置的元素6
插入第一个节点的元素为7
插入最后一个节点的元素为6
逆置链表
2、对程序整体的测试数据
输入元素为1、2、3、4、5的双向循环链表
六、测试情况
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
1
请输入要插入的位置下标和数据：
2
6
1 2 6 3 4 5
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
2
请输入要删除的位置下标和数据：
2
6
1 2 3 4 5
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
请输入插入第一个节点的元素：
7
7 1 2 3 4 5
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
4
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
4
请输入插入最后位置的元素：
6
1 2 3 4 5 6
请输入链表的元素的个数(大于0个) ：
5
请输入链表的5个元素：
1
2
3
5
您输入的链表为：
1 2 3 4 5
请选择操作项：
1. 插入第i 个节点
2. 删除第i 个节点
3. 插入第一个节点
4. 插入最后一个节点
5. 逆置
5
5 4 3 2 1
树的创建及相关操作的实现
一、问题描述
1. 先遍序遍历建树
2、遍历方法举例：
二、数据结构
针对所处理的树：
1、画出存储结构
2、使用所选用语言的功能，实现上述的该存储结构
public static class BTNode {
}
private AnyType data; private BTNode parent; private BTNode leftNode; private BTNode rightNode;
三、逻辑设计
1、总体思路
首先建立节点类，然后构造BinaryTree （），再构造先序遍历建树方法，层次遍历建树方法，层次遍历树的方法，统计叶子结点个数方法，交换子树方法，再调试。
2、模块划分（以图示的方法给出各个函数的调用关系）
3、函数或类的具体定义和功能
BiTNode()//节点类定义
public BiTNode creatTree(AnyType[] a)//先序建树方法定义 private void creatPathBinaryTree(AnyType[] a)//层次遍历建树定义
public void pathOrder()//层次遍历方法定义 public int countLeafNode()// 统计叶子节点个数方法定义
四、编码
1. 结点类定义
package kcsj;
public class BiTNode implements Comparable {
AnyType data ; BiTNode left , right ; int weight ; BiTNode() {
data = null ;
left = right = null ;
}
BiTNode(AnyType thedata) {
data = thedata;
left = right = null ;
}
BiTNode(AnyType thedata, BiTNode lt, BiTNode rt) { data = thedata;
left = lt;
right = rt;
}
public BiTNode getLeft() {
return left ;
}
public BiTNode getRight() {
return right ;
}
public Object getData() {
return data ;
}
public double getWight() {
return weight ;
}
@Override
public int compareTo(BiTNode o) {
if (o.getWight() > this .getWight())
return 1;
if (o.getWight()
} } return -1; return 0;
2.BinaryTree()构造
package kcsj;
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree> {
AnyType[] pre , in ; BiTNode rootNode = new BiTNode(); int count = 0; public BinaryTree() { } public BinaryTree(AnyType rootNodeItem) { } public BinaryTree(BiTNode t) { } rootNode = t; rootNode . data = rootNodeItem; rootNode . left = rootNode . right = null ; rootNode = null ;
//1. 先序遍历建树
public BiTNode creatTree(AnyType[] a) { } return rootNode = creatBinaryTree(a);
private BiTNode creatBinaryTree(AnyType[] a) {
BiTNode p = null ; if (count
} } count ++; if (data != null ) { } p = new BiTNode((AnyType) data); p. left = creatTree(a); p. right = creatTree(a); return p;
//1.层次遍历排序建树
public void creatPathTree(AnyType[] a) { } private void creatPathBinaryTree(AnyType[] a) { Queue q = new LinkedList(); BiTNode node = new BiTNode(a[0]); rootNode = node; q.offer(node); int i = 1; while (i
} } } } node = new BiTNode(a[i]); q.element().right = node; q.offer(q.element().right ); q.poll(); i++; //2.实现二叉树的层次遍历 public void pathOrder() { } public void pathOrder(BiTNode t) { } // 先序遍历 public void preOrder() { Queue q = new LinkedList(); q.offer(t); while (!q.isEmpty()) { } if (q.element().left != null ) q.offer(q.element().left ); if (rootNode != null ) pathOrder(rootNode ); if (q.element().right != null ) q.offer(q.element().right ); System. out .print(q.poll().data + " ");
} preOrder(rootNode );
private void preOrder(BiTNode t) {
if (t != null ) {
System. out .print(t.data +" ");
preOrder(t.left );
preOrder(t.right );
}
}
// 统计节点的个数
public int countNode() {
return countNode(rootNode );
}
private int countNode(BiTNode t) {
int m, n;
if (t == null )
return 0;
m = countNode(t.left );
n = countNode(t.right );
return m + n + 1;
}
// 3.统计叶子节点个数（递归）
public int countLeafNode() {
return countLeafNode(rootNode );
}
private int countLeafNode(BiTNode t) {
int m = 0, n = 0;
if (t == null )
return 0;
if (t.left == null && t.right == null ) {
return 1;
}
m = countLeafNode(t.left );
n = countLeafNode(t.right );
return m + n;
}
// 4.将二叉树左+右子树相互交换（递归）
public void exchangeTree() {
if (rootNode != null ) {
exchangeTree(rootNode );
}
}
private BiTNode exchangeTree(BiTNode t) { if (t != null ) {
BiTNode p = t.right ;
t. right = t.left ;
t. left = p;
exchangeTree(t.right );
exchangeTree(t.left );
}
return t;
}
// 计算树的深度
public int depth() {
return depth(rootNode );
private int depth(BiTNode t) { // 返回二叉树的深度 } //横向输出树状图 int depthleft, depthright; if (t == null ) return 0; depthleft = depth(t.left ); depthright = depth(t.right ); return Math.max (depthleft, depthright) + 1;
public void showTree(BiTNode t,int n){
}
}
3. 测试函数
package kcsj;
public class Test {
public static void pln(Object o) { } public static void main(String[] args) { System. out .println(o); if (t==null ) return ; showTree(t.right ,++n); for (int i = 0; i
Character[] charsPre = { 'a' , 'b' , 'd' , null , null , null , 'c' , 'e' ,
null , null , 'f' }; Character[] charsPath = { 'a' , 'b' , 'c' , 'd' , null , 'e' , 'f' }; pln (" 先序建树：{'a','b','d',null,null,null,'c','e',null,null,'f'}");
bt.creatTree(charsPre); pln (" 层序遍历结果：" ); bt.pathOrder(); pln (" "); pln (" 树图为(横向) ：" ); bt.showTree(bt.rootNode , 1); pln (" "); pln (" 层序建树：{'a','b','c','d',null,'e','f'}"); bt.creatPathTree(charsPath); pln (" 先序遍历结果：" ); bt.preOrder(); pln (" "); pln (" 树图为(横向) ：" ); bt.showTree(bt.rootNode , 1); pln (" "); pln (" 叶子节点数：" + bt.countLeafNode()); pln (" 交换后层次遍历结果：" ); bt.exchangeTree(); bt.pathOrder(); pln (" ");
} pln bt.showTree(bt.rootNode , 1); pln (" "); pln (" 深度为：" + bt.depth()); }
五、测试数据
1、对每个函数的测试数据
利用线序遍历和层次遍历分别建树a b c d e f
2、对程序整体的测试数据
a b c d e f
六、测试情况
先序建树：{'a','b','d',null,null,null,'c','e',null,null,'f'} 层序遍历结果：
a b c d e f
树图为(横向) ：
f
c
e
a
b
d
层序建树：{'a','b','c','d',null,'e','f'}
先序遍历结果：
a b d c e f
树图为(横向) ：
f
c
e
a
b
d
叶子节点数：3
交换后层次遍历结果：
a c b f e d
树图为(横向) ：
d
b
a
e
c
f
深度为：3
结 论
在课程设计中，遇到最多的问题便是对一个方法思想的转换。在这两周的课程设计中，让我学会如何思考一个树的存储结构，如何创建，各种遍历的思想需要怎样的代码实现。总而言之，两个字，思考。
在课程设计时，思想问题一直是我进度缓慢的原因，对于层次遍历建树的时候的思想一直拐不过弯，不知道该以什么样的方式建立左右子树。最终在同学的讲解下，理解了建树的方法。首先以队列的形式，传进根节点。再判断输入数组中是否存在根节点的左子树，如果存在则创建左孩子并将数据压入队列中。而右子树为左子树加一，故而在设置右子树的范围时，需要小于输入数组的长度减一，再以同样的方法判断是否存在右子树，存在则建立右孩子并将数据压入队列。
这次课程设计明白的远远不止这些，对于子树的交换，是我对于数据结构的认知茅塞顿开，发现原来自己以前真的一点都没明白这门课程到底是干嘛的，如今才清晰地明白这门课程要的是对数据的结构的思考。
发现自己的数据结构设计还是很弱，对于很多方法都不熟悉，以后希望能有更多的机会联系数据结构，让自己得到提升。
参考文献
[1] 王世民 JAVA 数据结构与算法分析[M] 北京：清华大学出版社, 2004-
山东建筑大学计算机科学与技术学院
课程设计指导教师评语
指导教师评语（包括工作态度，遵守纪律；基本理论、知识、技能；独立工作能力和分析解决问题的能力；完成任务情况及水平）：
学生成绩（百分制）：
指导教师签名： 年 月 日