递归

递归

递归时常用的编程技术，其基本思想就是“自己调用自己”，一个使用递归技术的方法即是直接或间接的调用自身的方法。递归方法实际上体现了“以此类推”、“用同样的步骤重复”这样的思想，它可以用简单的程序来解决某些复杂的计算问题，但是运算量较大。

先来看一个最简单的求阶乘的例子，下面的递归方法将求得参数n的阶乘。

long Factorial(int n){

if（n==1) {

return 1; //递归头

}

return n*Factorial(n-1); //递归调用自身

}

见不是递归的例子NotRecurseFactorial.java

这段程序虽然简单，却体现了递归的基本思想和要素。

（1）递归方法解决问题时划分为两个步骤：一个步骤是求得范围缩小的同性质问题的结果；另一个步骤是利用这个已得到的结果和一个简单的操作求得问题的最后解答。这样一个问题的解答将依赖与一个同性质问题的解答，而解答这个同性质的问题实际上就是用不同的参数（体现范围缩小）来调用递归方法自身。

（2）如果递归方法只是一味地调用自己，则将构成无限循环，永远无法返回。所以在任何一个递归方法都必须有一个“递归头”。即当同性质的问题被简化得足够简单时，将可以直接求得问题的答案，而不必再调用自身。

（3）递归方法的主要内容包含了定义递归头和定义如何从同性质得简化问题求得当前问题两个部分；

下例将求出菲波那契数列。菲波那契数列时一个数据序列，其中每个位置上的数据的数值时固定的，可以通过其前面的数据求得。具体表现如下：

fibonacci(n)=n,n=0,1

fibonacci(n)= fibonacci(n-1)+ fibonacci(n-2)，n为其他整数

可见菲波那契数列的第一、第二个数据分别是0和1，以后的其它数据则是它前面两个数据之和。如第三位的数据是0，1之和1，第四位的数据是1，1之和2，第五位的数据是1，2之和3，等等。用递归方法求菲波那契数列是最自然不过了。

例FibonacciSerial.java

这里为了获得调用和返回的缩进对齐效果使用了几个计数器计算递归方法调用和返回的次数、记录各种调用返回次数；并定义了体各专门方法来计算缩进多少，时程序变得比较复杂。实际上菲波那契方法可以写得非常简单。

long fibonacci(int n){

if(n==0||n==1) {

return n;

}

return(fibonacci(n-1)+fibonacci(n-2));

}

见不是递归的例子UnRecurseFibo.java

见程序FibonacciSerial.java

见效果FibonacciSerial.html

简单的程序是递归方法的优点之一，但是递归调用会占用大量的系统堆栈，内存耗用多，在递归调用层次较多时使用要慎重。

见例程Tower.java

见效果Tower.html



排序

排序是将一个数据序列中的各个元素根据某个给出的关键值进行从大到小（称为降序）或从小到大（称为升序）排列的过程。排序将改变数据序列中各元素的先后顺序，使之按升序或降序排列。这里主要介绍冒泡法、选择排序和插入排序、快速排序桶排序等五种常用的排序算法。

1 冒泡排序

冒泡排序算法的基本思路是把当前数据序列中的各相邻数据两两比较，发现任何一对数据间不符合要求的升序或降序关系则立即调换它们的顺序，从而保证相邻数据间符合升序或将序的关系。

以升序排序为例，经过从头至尾的一次两两比较和交换（称为“扫描”）之后，序列中最大的数据被排列到序列的最后。这样，这个数据的位置就不需要再变动了，因此就可以不再考虑这个数据，而对序列中地其他数据重复两两比较和交换的操作。第二次扫描之后会得到整个序列中次大的数据并将它排在最大数据的前面和其他所有数据的后面，这也是它的最后位置，尚未排序的数据又少了一个。以此类推，每一轮扫描都将使一个数据就位并使未排序的数据数目减一，所以经过若干轮扫描之后，所有的数据都将就位，而整个冒泡排序就完成了。

BubbleSort.java

见效果BubbleSort.html


2 选择排序

选择排序的基本思想是把数据序列化分成两个子序列，一个子序列中是已经排好序的数据，另一个子序列中是尚未排序的数据；程序开始时有序子列为空，而无序子列包含了全体数据；

从无序子列中选择一个合适的数据，例如，将无序子列中的最小数据放到有序子列中，这样有序子列增长到一，而无序子列减少一个，这就是一次选择过程；重复这个选择过程，每次都在无序子列剩余的未排序数据中选择最小的一个放在有序子列的尾部，使得有序子列不断增长而无序子列不断减少，最终无序子列减少为空，所有数据都在有序子列中按要求的顺序排列，整个排序的操作也就完成了。

见例程SelectSort.java

见效果SelectSort.html

3 插入排序

插入排序同样是把待排序的数据列划分成有序子列和无序子列两部分，程序开始时有序子列为空而无序子列包含了全部数据。与选择排序不同的是插入排序不是从无序子列中选择一个合适的数据（例如无序子列的最小数据）放到有序子列的固定位置（例如有序子列的最后面），而是把无序子列中的固定位置的数据（例如无序子列最前面的数据）插入到有序子列的合适位置中，使得插入这个数据滞后的有序子列仍然能保持有序。插入排序的任务就是找到这个合适的位置。当所有的无序子列中的数据都插入到有序子列中的时候，插入排序就完成了。

见例程InsertSort.java

见效果InsertSort.html

　

4 桶排序

桶排序的基本思想是把待排序的数据放在一个一维数据中，另外设置一个10*n的二位数组（由于每一位数字可以从0到9，故10行），其中n时待排序数据的个数。设待排序数据中最大的为4位数，则排序需要经过四轮扫描，每轮扫描包括分散扫描和集中扫描两步。

1、分散扫描：把一维数组的数据分散保存到二维数组中。求出各待排序数据的个位数，以此个位数为行下标，保存到二维数组的相应行中。例如104和24保存到第三行（行下标为4）90保存到第一行（行下标为0）。如果两数的个位数相同则保存在同一行中。其下标的先后顺序由它们在一维数组中的先后顺序确定。

2、集中扫描：把二维数组中的数据按照下标顺序集中保存回一维数组。例如上面三个数据保存回一维数组后成为90，104，24。

第二轮扫描针对各数据的十位数做分散扫描和集中扫描。扫描后一维数组中数据排列为104，24，90；第三轮针对百位数，扫描后数据排列为24，90，104，排序完成。

与前面几种排序方法相比，桶排序的排序效率较高，需要的扫描次数少，所须时间少，但是这种方法占用内存空间较多。

见例程BucketSort.java

见效果BucketSort.htm

5、快速排序。快速排序的主要原理是先选定一个标志值，对数组进行粗排序，大于这个标志的排在左边，大于这个数的排在右边，再对两边进行粗排序，一直到每个数都被排序。

见例程QuickSort.java

效果见QuickSort.html

上面介绍的几种排序算法各有特点，其中冒泡算法比较简单，使用较广，适合于排序数据数目不是很多的情况，但是它的操作代价较高。如果有n个数据参加排序，则使用冒泡算法的运算次数是n的3次方数量级的量。选择排序和插入排序两个算法的代价比冒泡算法低一个数量级，运算次数在n的2次方数量级。其中选择排序中的比较操作多，数据移动操作少，插入排序的比较操作少，数据移动操作多。综合起来二者的排序效率基本相同。桶排序的扫描次数最少，但是需要一个10*n的大数组。快速排序，它的代价比选择排序和插入排序还要再低一个数量级，与桶排序相同，可以达到n*logn的数量级，但是它要进行多次递归调用，也要花费很多的时间。





链表

除了数据组和向量，程序里还经常用到其它一些重要的线性数据结构，如堆栈、队列、链表等。本届介绍链表这种数据结构的特点及其java实现。

链标与数据相仿，一个链表代表一个线性的数据序列，但是这两种数据结构存在如下的不同之处。

1、创建数组是一次性地开辟一整块内存空间，所有的数组元素都存放在里面，并且必须明确说明数组的固定长度（即其中数组元素的个数）。创建链表则可以先只创建一个链表头，其它的链表中的元素（称为节点）则可以在需要的时候在动态地逐个创建并加入到链表中。链表的这种动态内存申请策略为程序运行提供了很好的灵活性。

2、数组中的各数据元素顺序、连续的存储在内存中，所以在定位数组中的一个元素是值需要知道这个元素在数组中的位置（即元素下标）即可；而链表中的数据在内存中不是连续存放的，每个节点车了保存数据之外，还有一个专门的属性用来指向链表的下一个节点（称为链表的指针），所有的链表节点通过指针相连，访问它们是需要从链表头开始顺序进行。

3、若在数组中插入或删除数据，则需要把插入或删除点后面的所有元素做大规模的集体移动，运算量较大；而链表节点的插入和删除却非常方便，不需要任何数据移动。

从这些分析可知，链表示有节点组成的非连续的动态线性数据结构，适合于处理数据序列中数据数目不定，且插入和删除较多的问题。

1 链表的节点

下面的语句定义了链表的节点类：

class Node {

private Object item;

private Node nextNode;

private void init(Object data,Node next){

item = data;

nextNode = next;

}

public Node(Object data) {

init(data, null);

}

public Node(Object data, Node next) {

init(data, next);

}

public void setData(Object data) {

item = data;

}

public Object getData() {

return item;

}

public void setNext(Node next) {

nextNode = next;

}

public Node getNext() {

return nextNode;

}

}

节点类Node中定义了两个属性，一个是用来保存数据的item，item可以是任何数据类型的对象，另外一个是nextNode，是用来保存下一个节点的引用。

2 创建链表

链表类可以用如下的类定义来表达：

见例程LinkList.java



由图可见，链表由若干节点组成，每个节点包括数据和引用两部分，其中引用是指向下一个节点的对象引用。第一个节点保存在LinkList类中，它可以在创建链表对象时创建（利用第二个构造函数）。我们也可以先创建一个空链表（利用第一个构造函数），再用插入方法动态生成第一个节点。链表中其余的节点都是利用插入方法动态生成后，在加入到链表中的。

6.9.3 遍历链表

LinkList类中定义的方法visitAllNode()就是用来便利链表的方法。从图中可以看出，由于链表不想数据组那样顺序存放，所以访问链表的元素也不能简单地通过下标完成，而需要从链表的第一个元素开始沿着指针逐个查找，方法visitAllNode()中就把链表从第一个元素直到最后一个元素逐个访问了一遍。在这个过程中使用的两个语句应该特别强调，它们分别是：

While(node!=null) //直到最后一个节点

这个语句表明访问循环的中止条件，以为链表的最后一个节点的指针属性为空（null）,所以通常采用这种方法来判断循环的中止条件。不过在创建链表和插入节点适应保证“最后一个节点的指针为空”总是成立，否则上述循环中止条件就会失效。

node=node.getNext();

这个语句使当前访问的节点下移一个。因为每个节点都由一个指向下一个节点的指针属性，利用这个指针，就可以获得下一个节点的对象引用，从而访问下一个节点的属性和方法。

这两个语句代表了链表操作中经常需要使用的手段，希望读者能了解其意义和使用方法。

4 链表的插入操作

LinkList类中定义了两个向连表中插入数据的方法：insertAtBegin()方法根据形参提供的数据创建一个新的包含这个数据的节点，并把这个节点加入在当前链表的第一个节点之前成为新的第一节点；insertAfterId()在链表中序找包含数据等于形参id的节点，将新建的节点插在找到的节点之后，若找不到符合条件的节点，则将新建节点插入到链表的最后面。

在链表中插入节点一般包括两个操作：

1、创建新节点，新建节点包括的数据一般由形参提供。

2、把新建节点插入链表合适的位置，保证链表各节点依然继续可达，这可以通过把插入为之前的节点指针赋值给新建节点，并使插入为之前节点的指针指向新建节点。



5 链表的删除操作

LinkList类中定义类两个删除链表中节点的方法：removeAtId（）和removeAll()。

RemoveAtId（）方法将删除链表第Id的节点。这个方法看似复杂，实际只是考虑了链表为空和链表只有一个节点两种情况，然后再利用两对象引用逐一探查链表中的各节点。



removeAll（）方法将删除整个链表，只需令第一个节点为空就可以达到这个目的，以为没有第一个节点，其后的所有其它链表的节点就找不到了，也无法访问了。

整个见效果演示UseLinkList.html

具体程序见UseLinkList.java



列队

列队（Queue）与链表相似，也是重要的线性数据结构。队列遵循“先进先出”（FIFO）的原则，固定在一端输入数据（称为加队），另一端输出数据（称为减队）



可见队列中数据的插入和删除都必须在队列的头尾处进行，而不能相链表一样直接在任何位置插入和删除数据。

计算机系统的很多操作都要用到队列这种数据结构。例如当需要在只有一个CPU的计算机系统中运行多个任务时，因为计算机一次只能处理一个任务，其它的任务就被安排在一个专门的队列中排队等候。当前任务处理完毕时，CPU就从队列的输出端取出一个任务执行（减队过程）；而每当产生一个新的任务时，它都被送到队列的输入端（加队过程），恰似日常生活中的队列，每个任务都必须等待它前面的所有任务都执行完毕之后才能执行，最先进入队列的也最先出队被服务，这就是“先进先出”的原则。另外打印缓冲池中的等待作业队列、网络服务器中待处理的客户机请求队列，也就是使用队列数据结构的例子。

队列可以使用链表来实现。



import java.awt.*;
import java.awt.event.*;
import java.applet.*;
public class UseQueue extends Applet {
private Button enQueue, delQueue;
private Panel north;
private int index;
private Queue myqueue;
public void init() {
setFont(new Font("SanSerif",Font.BOLD,30));
index = 0;
myqueue = new Queue();
setLayout(new BorderLayout());
north = new Panel();
north.setLayout(new GridLayout(1,2));
add(north, BorderLayout.NORTH);
enQueue = new Button("enQueue");
delQueue = new Button("delQueue");
north.add(enQueue);
enQueue.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
index++;
myqueue.enQueue(new Integer(index));
repaint();
}
});
delQueue.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
myqueue.delQueue();
repaint();
}
});
north.add(delQueue);
}
public void paint(Graphics g) {
g.drawString(myqueue.visitAllNode(), 20, 150);
}
}
class Queue {
private LinkList queue;
public Queue() {
queue = new LinkList();
}
public boolean isEmpty() {
return queue.isEmpty();
}
public Object delQueue() {
return queue.removeAtId(0);
}
public void enQueue(Object data) {
queue.append(data);
}
public String visitAllNode() {
return queue.visitAllNode();
}
}
class LinkList {
private Node first;
public LinkList() {
first = null;
}
public LinkList(Object data) {
first = new Node(data);
}
public String visitAllNode() {
Node node = first;
String str="";
while(node != null) {
str += ((node.getData()).toString()+" ");
node = node.getNext();
}
return str;
}
public void insertAfterId(Object data, int index) {
Node node = first;
if(first == null) {
first = new Node(data);
return ;
}
int ind = 0;
while(node.getNext() != null && ind <index) {
node = node.getNext();
ind++;
}
Node temp = new Node(data);
temp.setNext(node.getNext());
node.setNext(temp);
return ;
}
public Object removeAtId(int index) {
if(first == null) return null;
Node temp;
if(index == 0 ) {
temp = first;
first = first.getNext();
return temp.getData();
}
Node node = first;
int ind = 1;
while(node.getNext() != null && ind <= index) {
if(ind == index) {
temp = node.getNext();
node.setNext(temp.getNext());
return temp.getData();
}
node = node.getNext();
ind++;
}
return null;
}
public boolean isEmpty() {
return first==null;
}
public void removeAll() {
while(!isEmpty()) {
removeAtId(0);
}
}
public void insertAtBegin(Object data) {
if(first == null) {
first = new Node(data);
return;
}
first = new Node(data, first);
}
public void append(Object data) {
if(first == null) {
first = new Node(data);
return;
}
Node node=first;
while(node.getNext() != null) {
node = node.getNext();
}
node.setNext(new Node(data));
}
}

class Node {
private Object item;
private Node nextNode;
private void init(Object data, Node next) {
item = data;
nextNode = next;
}
public Node(Object data) {
init(data, null);
}
public Node(Object data, Node next) {
init(data, next);
}
public void setData(Object data) {
item = data;
}
public Object getData() {
return item;
}
public void setNext(Node next) {
nextNode = next;
}
public Node getNext() {
return nextNode;
}
}

堆栈

堆栈又称为栈，也是线性数据结构，并且是遵循“后进先出”（LIFO）原则的重要线性数据结构。在Java中，Stack是java.util包中专门用来实现栈的工具类。

栈只能在一端输入输出，它由一个固定的栈底和一个浮动的栈顶。栈顶可以理解未是一个永远指向栈最上面元素的指针。向栈中输入数据的操作称为“压栈”，被压入的数据保存在栈顶，并同时使栈顶指针向上浮一格。从栈中输出数据的操作称为“弹栈”，被弹出的总是栈顶指针指向的位于栈顶的元素。如果栈顶指针指向了栈底，则说明当前的堆栈是空的。

Stack是Java用来实现栈的工具类，它的主要方法如下：

1、构造函数

public Stack():是栈类唯一的构造函数，创建堆栈可以直接调用它。

2、压栈与弹栈操作

public Object push(Object item):将指定对象压入栈中。

public Object pop()：将堆栈最上面的元素从栈中取出，并返回这个对象。

3、检查栈是否为空

public Boolean empty()：若堆栈中没有对象元素，则此方法返回true，否则返回false。

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
public class UseStack extends Applet {
private Button pop, push, restore;
private Panel north;
private int index;
private Stack mystack;
private String msg;
public void init() {
msg = "";
setFont(new Font("SanSerif",Font.BOLD,30));
index = 0;
mystack = new Stack();
setLayout(new BorderLayout());
north = new Panel();
north.setLayout(new GridLayout(1,3));
add(north, BorderLayout.NORTH);
pop = new Button("Pop");
push = new Button("Push");
restore = new Button("Restore");
north.add(pop);
pop.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
Object data = mystack.pop();
if(data != null) {
msg += data.toString()+" ";
repaint();
}
}
});
push.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
index++;
mystack.push(new Integer(index));
repaint();
}
});
north.add(push);
north.add(restore);
restore.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
index = 0;
msg = "";
mystack.clearAll();
repaint();
}
});
}
public void paint(Graphics g) {
g.drawString(mystack.visitAllNode(), 20, 100);
g.drawString(msg, 20, 140);
}
}
class Stack {
private LinkList stack;
public Stack() {
stack = new LinkList();
}
public String visitAllNode() {
return stack.visitAllNode();
}
public void push(Object data) {
stack.insertAtBegin(data);
}
public Object pop() {
return stack.removeAtId(0);
}
public boolean isEmpty() {
return stack.isEmpty();
}
public void clearAll() {
stack.removeAll();
}
}
class LinkList {
private Node first;
public LinkList() {
first = null;
}
public LinkList(Object data) {
first = new Node(data);
}
public String visitAllNode() {
Node node = first;
String str="";
while(node != null) {
str += ((node.getData()).toString()+" ");
node = node.getNext();
}
return str;
}
public void insertAfterId(Object data, int index) {
Node node = first;
if(first == null) {
first = new Node(data);
return ;
}
int ind = 0;
while(node.getNext() != null && ind <index) {
node = node.getNext();
ind++;
}
Node temp = new Node(data);
temp.setNext(node.getNext());
node.setNext(temp);
return ;
}
public Object removeAtId(int index) {
if(first == null) return null;
Node temp;
if(index == 0 ) {
temp = first;
first = first.getNext();
return temp.getData();
}
Node node = first;
int ind = 1;
while(node.getNext() != null && ind <= index) {
if(ind == index) {
temp = node.getNext();
node.setNext(temp.getNext());
return temp.getData();
}
node = node.getNext();
ind++;
}
return null;
}
public boolean isEmpty() {
return first==null;
}
public void removeAll() {
while(!isEmpty()) {
removeAtId(0);
}
}
public void insertAtBegin(Object data) {
if(first == null) {
first = new Node(data);
return;
}
first = new Node(data, first);
}
public void append(Object data) {
if(first == null) {
first = new Node(data);
return;
}
Node node=first;
while(node.getNext() != null) {
node = node.getNext();
}
node.setNext(new Node(data));
}
}

class Node {
private Object item;
private Node nextNode;
private void init(Object data, Node next) {
item = data;
nextNode = next;
}
public Node(Object data) {
init(data, null);
}
public Node(Object data, Node next) {
init(data, next);
}
public void setData(Object data) {
item = data;
}
public Object getData() {
return item;
}
public void setNext(Node next) {
nextNode = next;
}
public Node getNext() {
return nextNode;
}
}

二叉树

前面介绍的堆栈、链表、和队列都是线性数据结构。所谓线性数据结构试制其中的每个节点都只有一个前接节点和一个后继节点，这样所有的节点就排列成了线状的一列。但是在我们面临的实际问题和实际应用中，除了线性数据结构，还存在着大量的非线性数据结构。树就是非线性数据结构的典型代表。

树中每一个节点只有一个前接节点，但是可以有多个后继节点。最简单的树，其中各节点只有一个前接节点，而且最多只能有两个后继节点，称为二叉树。



上图显示了一棵最简单的二叉树。

（1）它的形状像一棵倒长的树，其中每个节点都只有一个前接节点。

（2）每个节点都可以有最多两个后继节点。

（3）每一棵二叉树中都有且只有一个特殊的没有前接节点的节点，称为根节点。

（4）二叉树中还有一些没有后继节点的特殊节点。称为叶节点。它们是二叉树的叶。

二叉树的节点与链表等线性数据结构的节点不同。除了数据属性之外，它还有两个指针分别指向它的两个后继节点，称为左指针和右指针。对于二叉树的任何一个节点来说，以其左指针指向的后继节点为根节点的二叉树称为当前节点的左子树，以其右指针指向的后继节点为根节点的二叉树称为当前节点的右子树。二叉树的所有叶节点的左右指针都为空，所以也节点没有左右子树。

1、创建二叉树



相对与链表等线性数据结构，创建二叉树要复杂的多。这里指介绍其中的一种：搜索二叉树。上图是一棵搜索二叉树的例子。对于搜索二叉树的任何一个节点来说，其左子树中的所有数据都小于该节点的数据，而其右子树中的所有数据都大于该节点的数据。

由上图可见，搜索二叉树中右子树的所有数据都大于根节点的数据，也大于左子树的数据。这样，利用搜索二叉树查找一个数据时，只要把该数据与根节点的数据相比较。若该数据大于根节点的数据，则可以排除掉左子树而到右子树中继续查找；若小于根节点的数据则应到左子树中查找。搜索二叉树就因此而得名。可以看出她的原理与对分查找是一致的。

2、二叉树的遍历与查找

遍历二叉树就是要访问二叉树中的所有节点。通常遍历二叉树有先序、中序和后序三种不同的算法。

（1）先序的遍历是按照“根节点，左子树，右子树 ”的顺序访问二叉树。

（2）中序遍历按照“左子树，根节点，右子树”的顺序访问二叉树的所有节点。

（3）后序遍历按照“左子树，右子树，根节点”的顺序访问二叉树的所有节点。

（4）按层来访问所有节点。

可见三种按序访问算法的差别主要表现在对根节点的访问顺序上，而左子树中诸节点的访问顺序永远在右子树的前面。



import java.lang.*;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
public class UseBinaryTree extends Applet {
private Button insert, preorder, inorder;
private Button postorder, layerorder, search;
private TextField input;
private Panel north;
private Integer data;
private Label result;
private BinaryTree mytree=new BinaryTree();
private String msg;
public void init() {
msg = "";
data = null;
setFont(new Font("SanSerif",Font.BOLD,30));
north = new Panel();
setLayout(new BorderLayout());
add(north, BorderLayout.NORTH);
north.setLayout(new GridLayout(2,4));
insert = new Button("InsertNode");
insert.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
mytree.insertToTree(data);
}
});
preorder = new Button("PreOrder");
preorder.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
msg = mytree.preOrderReview();
repaint();
}
});
inorder = new Button("InOrder");
inorder.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
msg = mytree.inOrderReview();
repaint();
}
});
postorder = new Button("PostOrder");
postorder.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
msg = mytree.postOrderReview();
repaint();
}
});
layerorder = new Button("LayerOrder");
layerorder.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
msg = mytree.LayerOrderReview();
repaint();
}
});
search = new Button("Search");
search.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e) {
if(mytree.SearchData(data)) {
result.setText("I am found!");
}
else {
result.setText("I am lost!");
}
}
});
input = new TextField(6);
input.addTextListener(new TextListener(){
public void textValueChanged(TextEvent e) {
try {
data = Integer.valueOf(input.getText());
}
catch(NumberFormatException ex) {
}
}
});
result = new Label();
north.add(insert);
north.add(preorder);
north.add(inorder);
north.add(postorder);
north.add(layerorder);
north.add(search);
north.add(input);
north.add(result);
}
public void paint(Graphics g) {
g.drawString(msg,10,150);
}
}
class BinaryTree {
private TreeNode root;
public BinaryTree(Comparable data) {
root = new TreeNode(data);
}
public BinaryTree() {
root = null;
}
public String preOrderReview() {
if(root == null ) {
return "the tree is null";
}
return myPreOrderReview(root);
}
private String myPreOrderReview(TreeNode node) {
String msg="";
msg += node.getData().toString()+" ";
if(node.getLeft() != null) {
msg += myPreOrderReview(node.getLeft());
}
if(node.getRight() != null ) {
msg += myPreOrderReview(node.getRight());
}
return msg;
}
public String inOrderReview() {
if(root == null ) {
return "the tree is null";
}
return myInOrderReview(root);
}
private String myInOrderReview(TreeNode node) {
String msg="";
if(node.getLeft() != null) {
msg += myInOrderReview(node.getLeft());
}
msg += node.getData().toString()+" ";
if(node.getRight() != null ) {
msg += myInOrderReview(node.getRight());
}
return msg;
}
public String postOrderReview() {
if(root == null ) {
return "the tree is null";
}
return myPostOrderReview(root);
}
private String myPostOrderReview(TreeNode node) {
String msg = "";
if(node.getLeft() != null) {
msg += myPostOrderReview(node.getLeft());
}
if(node. getRight() != null ) {
msg += myPostOrderReview(node.getRight());
}
msg += node.getData().toString()+" ";
return msg;
}
public String LayerOrderReview() {
if(root == null ) {
return "the tree is null";
}
Queue myqueue = new Queue();
myqueue.enQueue(root);
TreeNode node;
String msg = "";
while(!myqueue.isEmpty()) {
node = (TreeNode)(myqueue.delQueue());
msg += node.getData().toString()+" ";
if(node.getLeft() != null) {
myqueue.enQueue(node.getLeft());
}
if(node.getRight() != null) {
myqueue.enQueue(node.getRight());
}
}
return msg;
}
public boolean SearchData(Comparable data) {
if(root == null ) {
return false;
}
TreeNode node = root;
int index;
while(node != null) {
index = node.getData().compareTo(data);
if(index == 0) return true;
if(index > 0) {
node = node.getLeft();
}
else {
node = node.getRight();
}
}
return false;
}
public void insertToTree(Comparable data) {
if(root == null) {
root = new TreeNode(data);
return ;
}
TreeNode node = root;
int index;
while(node != null) {
index = node.getData().compareTo(data);
if(index > 0) {
if(node.getLeft() != null) {
node = node.getLeft();
}
else {
node.setLeft(new TreeNode(data));
return;
}
}
else if(index <0) {
if(node.getRight() != null) {
node = node.getRight();
}
else {
node.setRight(new TreeNode(data));
return;
}
}
else {
return;
}
}
}
}
class TreeNode {
private TreeNode left;
private TreeNode right;
private Comparable item;
public TreeNode(Comparable data) {
item = data;
left = null;
right = null;
}
public Comparable getData() {
return item;
}
public void setData(Comparable data) {
item = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode ptr) {
left = ptr;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode ptr) {
right = ptr;
}
}
class Queue {
private LinkList queue;
public Queue() {
queue = new LinkList();
}
public boolean isEmpty() {
return queue.isEmpty();
}
public Object delQueue() {
return queue.removeAtId(0);
}
public void enQueue(Object data) {
queue.append(data);
}
public String visitAllNode() {
return queue.visitAllNode();
}
}
class LinkList {
private Node first;
public LinkList() {
first = null;
}
public LinkList(Object data) {
first = new Node(data);
}
public String visitAllNode() {
Node node = first;
String str="";
while(node != null) {
str += ((node.getData()).toString()+" ");
node = node.getNext();
}
return str;
}
public void insertAfterId(Object data, int index) {
Node node = first;
if(first == null) {
first = new Node(data);
return ;
}
int ind = 0;
while(node.getNext() != null && ind <index) {
node = node.getNext();
ind++;
}
Node temp = new Node(data);
temp.setNext(node.getNext());
node.setNext(temp);
return ;
}
public Object removeAtId(int index) {
if(first == null) return null;
Node temp;
if(index == 0 ) {
temp = first;
first = first.getNext();
return temp.getData();
}
Node node = first;
int ind = 1;
while(node.getNext() != null && ind <= index) {
if(ind == index) {
temp = node.getNext();
node.setNext(temp.getNext());
return temp.getData();
}
node = node.getNext();
ind++;
}
return null;
}
public boolean isEmpty() {
return first==null;
}
public void removeAll() {
while(!isEmpty()) {
removeAtId(0);
}
}
public void insertAtBegin(Object data) {
if(first == null) {
first = new Node(data);
return;
}
first = new Node(data, first);
}
public void append(Object data) {
if(first == null) {
first = new Node(data);
return;
}
Node node=first;
while(node.getNext() != null) {
node = node.getNext();
}
node.setNext(new Node(data));
}
}

class Node {
private Object item;
private Node nextNode;
private void init(Object data, Node next) {
item = data;
nextNode = next;
}
public Node(Object data) {
init(data, null);
}
public Node(Object data, Node next) {
init(data, next);
}
public void setData(Object data) {
item = data;
}
public Object getData() {
return item;
}
public void setNext(Node next) {
nextNode = next;
}
public Node getNext() {
return nextNode;
}
}