第6章 常用算法与数据结构 - 副本

第6章

常用算法与数据结构

本章要点：

·排序与查找

·堆栈与队列

·树

在非数值计算应用中，计算机加工的数据对象往往是大量的数据。这些数据存取、查找、插入和删除等等操作效率的提高，仅仅依赖程序设计的技巧已经无法达到目的，必须对这些被加工数据的组织形式加以研究，找出最佳的数据组织形式，并与好的程序设计技巧相配合，才能达到提高效率的目的。

算法（algorithm）就是非空的、有限的指令序列，遵循它就可以完成某一确定的任务。

数据结构是研究计算机中大量数据存储的组织形式，并定义相应的运算以提高计算机的数据处理的能力。

在编制程序程序之前，首先应该选择一个恰当的数据结构和一个好的算法。

6.1 排序与查找

本节介绍一些编程中常用的基本算法,这些算法不但在面向过程的程序设计中经常会用到,也是面向对象编程的重要工具之一。实际上,面向对象的编程中,封装起来的对象之间使用的是面向对象的原则,而被封装的对象内部依然遵循面向过程的编程的原则。

6.1.1 排序

排序是计算机中常用的一种重要的运算，其功能是将一个数据序列中的各个数据元素根据某个给出的关键值按从大到小(称为降序)或从小到大(称为升序)的排列。排序将改变数据序列中各元素的先后顺序,使之成为有序序列。排序分为内部排序和外部排序，内部排序的方法有很多，这里只介绍冒泡排序、选择排序和插入排序三种常用的排序算法。

1、插入排序

插入排序（Insertion Sort）是一种简单的排序方法，它把待排序的数据序列划分成有序子列和无序子列两部分，程序开始时有序子列为空而无序子列包含了全部数据。它的基本操作是把无序子列的固定位置的数据（例如无序子列最前面的数据）插入到有序子列的合适位置中，从而得到一个新的、长度增1的有序子列。

例如，已知待排序的一组序列的初始排列如下所示：

50，32，63，97，75，13，26，45

假设在排序过程中，前4个数已按递增的次序重新排列，构成一个含4个数的有序序列 {32，50，63，97}

现要将第5个数插入到上述序列，以得到一个新的含5个数的有序序列，则首先要在上述序列中进行查找以确定75所应插入的位置，然后进行插入。假设从97起向左进行顺序查找，由于63<75<97，则75应插入到63和97之间，从而得到下列新的有序序列

{32，50，63，75，97}

【例6.1】插入排序

/* Program name InsertSortDemo.java

一个插入排序的例子

*/

class ArrayIns

{

private double[] a; // 定义double类型的数组

private int nElems; // 变量nElems存储数据项数

public ArrayIns(int max) // 构造器

{

a = new double[max];

nElems = 0;

}

public void insert(double value) // 插入数据到数组中

{

a[nElems] = value;

nElems++;

}

public void display() // 显示数组中的数据

{

for(int j=0; j

System.out.print(a[j] + " ");

System.out.println("");

}

public void insertionSort()

{

int in, out;

for(out=1; out

{

double temp = a[out];

in = out;

while(in>0 && a[in-1] >= temp) // 查找插入的位置

{

a[in] = a[in-1]; // 数据在数组中右移一个位置

--in;

}

a[in] = temp; // 插入到正确位置

}

} // end insertionSort()

} // end class ArrayIns

class InsertSortDemo {

public static void main(String[] args)

{

int maxSize = 100; // 数组初始大小为100

ArrayIns arr;

arr = new ArrayIns(maxSize); // 建立排序数组

arr.insert(50); // 插入8个数

arr.insert(32);

arr.insert(63);

arr.insert(97);

arr.insert(75);

arr.insert(13);

arr.insert(26);

arr.insert(45);

System.out.println("排序前：");

arr.display();

arr.insertionSort(); // 进行插入排序

System.out.println("排序后：");

arr.display();

} // end main()

} // end class InsertSortDemo

在main()方法中通过调用方法insert(double value)插入了8个数，然后调用方法insertSort()进行排序，display()方法用来输出数据，其结果输出如图6-1所示。

图6-1 【例6.1】的运行结果

2、冒泡排序

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

冒泡排序的过程很简单。首先将序列中的第一个数和第二个数进行比较，若为逆序（即第一个数>第二个数），则将两个数交换之，然后比较第二个数和第三个数。依次类推，直至第n-1个数和第n个数进行过比较为止。上述过程称为第一趟冒泡排序，其结果使得序列中的最大数被安置到最后一个数的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行相同的操作，其结果是使序列中次大的数被安置到第n-1个数的位置上。依此类推,每一趟两两比较和交换(称为“扫描”)都将使一个数据就位并使未排序的数据数目减一,所以经过k 趟〔1≤k＜n〕扫描之后,所有的数据都将就位,未排序数据数目为零,而整个冒泡排序就完成了。显然，判别冒泡排序结束的条件应该是“在一趟排序过程中没有进行过交换数的操作”。

例如，已知待排序的一组序列的初始排列如下所示：

50，32，63，97，75，13，26，45

则经过第一趟冒泡排序后其序列如下所示：

32，50，63，75，13，26，45，97

【例6.2】冒泡排序

/* Program name BubbleSortDemo.java

一个冒泡排序的例子

*/

class ArrayBub

{

private int[] a; // 定义int类型的数组

private int nElems; // 变量nElems存储数据项数

public ArrayBub(int max) // 构造器

{

a = new int[max];

nElems = 0;

}

public void insert(int value) // 插入数据到数组中

{

a[nElems] = value;

nElems++; // 数据项增1

}

public void display() // 显示数组中的数据

{

for(int j=0; j

System.out.print(a[j] + " ");

System.out.println("");

}

public void bubbleSort()

{

int out, in;

for(out=nElems-1; out>1; out--)

for(in=0; in

if( a[in] > a[in+1] ) //若第in个数大于第in+1个数，则

swap(in, in+1); // 交换这两个数据

}

private void swap(int one, int two)

{

double temp = a[one];

a[one] = a[two];// 实现交换

a[two] = temp;

}

} // end class ArrayBub

class BubbleSortDemo {

public static void main(String[] args)

{

int maxSize = 100; // 数组初始大小为100

ArrayBub arr;

arr = new ArrayBub(maxSize); // 建立排序数组

arr.insert(50); // 插入8个数

arr.insert(32);

arr.insert(63);

arr.insert(97);

arr.insert(75);

arr.insert(13);

arr.insert(26);

arr.insert(45);

System.out.println("排序前：");

arr.display();

arr.bubbleSort(); // 进行冒泡排序

System.out.println("排序后：");

arr.display();

} // end main()

} // end class BubbleSortDemo

在main()方法中通过调用方法insert(double value)插入了8个数，然后调用方法bubbleSort()进行排序，display()方法用来输出数据，其结果输出如图6-2所示。

图6-2 【例6.2】的运行结果

在程序中，swap（int one, int two）方法用来交换下标为one与下标为two的两个

数的位置，其中用临时变量temp暂存数据。

冒泡排序的一种改进方法是，在排序过程中，记下每次扫描时最后依次交换序列中的数发生的下标，显然，低于此下标的数都已排好了序，因而，扫描在此数位置处终止，而不必进行到预先确定的下限。

3、选择排序

选择排序（Select Sort）的基本思想也是把数据序列划分成两个子序列，一个子序列是已经排好序的数据，另一个子序列中是尚未排序的数据。程序开始时有序子列为空，而无序子列包含了全体数据。从无序子列中选择一个合适的数据，例如，选择无序子列中的最小数据放到有序子列中，这样有序子列长度增长一，而无序子列减少一，这就是一次选择过程。重复这个选择过程，每次都在无序子列剩余的未排序数据中选择最小的一个放在有序子列的尾部，使得有序子列不断增长而无序子列不断减少，最终无序子列减少为空，所有的数据都在有序子列中按要求的顺序排列，整个排序的操作也就完成了。

【例6.3】选择排序

/* Program name SelectSortDemo.java

一个选择排序的例子

*/

class ArraySel

{

private double[] a; // 定义double类型的数组

private int nElems; // 变量nElems存储数据项数

public ArraySel(int max) // 构造器

{

a = new double[max];

nElems = 0;

}

public void insert(double value) // 插入数据到数组中

{

a[nElems] = value;

nElems++; // 数据项增1

}

public void display() // 显示数组中的数据

{

for(int j=0; j

System.out.print(a[j] + " ");

System.out.println("");

}

public void selectionSort()

{

int out, in, min;

for(out=0; out

{

min = out; // 选择最小数

for(in=out+1; in

if(a[in] < a[min] ) // 若a[min]大于a[in]

min = in; // 则得到一个更小的数

swap(out, min); // 且交换之

} // end for(outer)

} // end selectionSort()

private void swap(int one, int two)

{

double temp = a[one];

a[one] = a[two];// 实现交换

a[two] = temp;

}

} // end class ArraySel

class SelectSortDemo {

public static void main(String[] args)

{

int maxSize = 100; // 数组初始大小为100

ArraySel arr;

arr = new ArraySel(maxSize);; // 建立排序数组

arr.insert(50); // 插入8个数

arr.insert(32);

arr.insert(63);

arr.insert(97);

arr.insert(75);

arr.insert(13);

arr.insert(26);

arr.insert(45);

System.out.println("排序前：");

arr.display();

arr.selectionSort(); // 进行冒泡排序

System.out.println("排序后：");

arr.display();

} // end main()

} // end class SelectSortDemo

在main()方法中通过调用方法insert(double value)插入了8个数，然后调用方法selectionSort()进行排序，display()方法用来输出数据，其结果输出如图6-3所示。

图6-3 【例6.3】的运行结果

上面介绍的几种排序算法各有特点，其中插入排序最简单，当序列中的数“基本有序”或n值较小时，它是最佳的排序方法，因此长将它和其它的排序方法结合在一起使用。冒泡排序适合于排序数据数目不是很多的情况，但是它的操作代价较高，如果有N个数据参加排序，则使用冒泡算法的运算次数是N3数量级的量；选择排序和插入排序两个算法的代价比冒泡算法低一个数量级，运算次数在N2数量级。除了上述讲的三种方法外，还有其它许多种排序方法，例如快速排序、归并排序、堆排序等。

6.1.2 查找

查找（Searching）是根据给定的某个值，在一个数据集合或数据序列中确定一个其关键字等于给定值的数据元素。若数据集合或数据序列中存在这样的一个数据元素，则称查找是成功的，此时查找的结果为给出整个数据元素的信息，或指示该数据元素在数据集合或数据序列中的位置；若数据集合或数据序列中不存在关键字等于给定值的数据元素，则称查找不成功。

例如，表6-1为某学生自然班情况，学生的学号为关键字。假设给定值为20020115，则通过查找可得该学生的姓名、性别等，此时查找是成功的。若给定值为20020136，则由于表中没有关键字为20020136的记录，则查找不成功。

由于查找需要处理大量的数据，所以查找过程可能会占用较多的系统时间和系统内存；为了提高查找操作的效率，需要精心设计查找算法来降低执行查找操作的时间和空间代价。较常用的查找算法有顺序查找、折半查找等。

1、顺序查找

顺序查找（Sequential Search）是最简单的查找算法，它的查找过程为：从数据序列的第一个数据开始，若某个关键字和给定值比较相等，则查找成功；反之，若直至最后一个数据，其关键字和给定值比较都不等，则表明数据序列中没有所查关键字，查找不成功。

顺序查找对于数据序列没有特殊的要求，这个序列可以是排好序的，也可以是未排好序的，对于查找操作都没有影响。在数据序列中数据数目不多时，使用顺序查找非常方便。

当然，顺序查找也可以从数据序列的最后一个数据开始。

【例6.4】顺序查找

/* Program name SqSearch.java

一个顺序查找的例子

*/

public class SqSearch {

//数据数组

public static int[] data={50,32,63,97,75,13,26,45};

public static void main(String[] args)

{ if(sequence(63)) //查找63

System.out.println("The data 63 found.");

else

System.out.println("The data 63 no found!");

if(sequence(25)) //查找25

System.out.println("The data 25 found.");

else

System.out.println("The data 25 no found!");

}

public static boolean sequence(int key){

int i;//数组下标变量

for (i=0;i<8;i++)

{

System.out.print(" ["+data[i]+"]"); //输出数据

if (key==data[i]){ //若查找到数据

System.out.println("");

return true; //则返回true

}

}

System.out.println("");

return false; //否则返回false

}

}

输出结果如图6-4所示。

图6-4 【例6.4】的运行结果

2、折半查找

如果数据序列中有N个数据，顺序查找的运算次数是N的数量级，如果N很大，使用顺序查找的代价也相应增大；如果希望大幅度降低运算次数，可以考虑使用折半查找算法。使用折半查找要求数据序列必须是已经排好序（升序、降序均可）的有序序列。

折半查找（Binary Search）的查找过程是：先确定待查关键字所在的范围（区间），然后逐步缩小范围直到找到或找不到该关键字为止。它先让待查关键值与有序序列中间的一个数据比较，并利用这个中间数据把有序序列划分成一前一后两个子列；如果待查关键值大于中间数据，说明序列中如果存在欲查找的数据，那么这个数据必然保存在后一个子列中，因

为只有这个子列中的所有数据都大于中间数据；相反，如果待查关键值小于中间数据，说明欲查找的数据存在于前一个子列中。这样，通过一次比较，把查找的范围缩小了一半，从整个序列变成一个子列。同理，继续使用对分方法不断划分更小的子列，缩小查找范围，直至目标子列中只剩余了一个数据；如果这个数据与待查关键值相匹配，则查找成功；否则说明原来的整个数据序列中并不存在一个与待查关键值相匹配的数据，查找失败。

现要查找数据63和25。假设指针low和high分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即mid=(low+high)/2，在本例中，low和high的初值分别为0及7，mid=7/2=3（取不大于该数的最大整数）。查找数据63的过程如下：步骤1：

63>data[3]=45，则low=mid+1=3+1=4，high=7，mid=(4+7)/2=5。

步骤2：

63=data[5]，找到数据。

查找数据25的过程如下：

步骤1：

25

步骤2：

25

步骤3：

25>data[0]，则low=mid+1=0+1=1，high=0,因为low>high，所以未能找到数据。

【例6.5】折半查找

/* Program name BSearch.java

一个折半查找的例子

*/

public class BSearch {

public static int max=8;

public static int[] data={13,26,32,45,50,63,75,97};

public static int counter=1;//计算查找的次数的变量

public static void main(String[] args)

{

for(int i=0;i<8;i++)

System.out.print(" ["+data[i]+"]"); //输出数据

System.out.println("");//换行

if(BinarySearch(63)) //查找63

System.out.println("Search time="+counter);

else

System.out.println("The data 63 no found!");

if(BinarySearch(25)) //查找25

System.out.println("Search time="+counter);

else

System.out.println("The data 25 no found!");

}

public static boolean BinarySearch(int key) {

int low; //下界

int high; //上界

int mid; //中间位置

low=0;

high=max-1;

while(low<=high)

{

mid=(low+high)/2;

if(key

high=mid-1; //查找前半段

else if(key>data[mid]) //待查找值较大

low=mid+1; //查找后半段

else if(key==data[mid]){ //查找到数据

System.out.println("data["+mid+"] = "+data[mid]);

return true;

}

counter++;

}

return false;

}

}

输出结果如图6-5所示。

图6-5 【例6.5】的运行结果

折半查找算法的运算次数为log2N，比顺序查找要低，而且算法本身也不复杂，如果数据序列是有序序列，使用折半查找比较合适。

6.2 堆栈与队列

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表的子集，它们是操作受限的线性表，因此，可称为限定性

数据结构。由于它们应用在各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。

6.2.1 堆栈

堆栈（Stack）又称为栈，是数据元素的有序集合，其数据只能从这个有序集合的一端插入和删除，这一端称为堆栈的栈顶（top），而另一端称为堆栈的栈底（bottom）。

假设栈S=(A，B，C，D)，则称A为栈底元素，D为栈顶元素（如图6-6所示）。栈中元素按A，B，C，D的次序进栈，退栈的第一个元素应为栈顶元素D，退栈的元素的顺序是D，C，B，A，与放入时的顺序恰好相反，故也称栈为后进先出（Last In First Out）的线性表（简称LIFO结构）或先进后出（First In Last Out）的线性表（简称FILO结构）。在Java 中，Stack是java.util

图 6-6 栈示意图

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

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

（1）检查堆栈是否为空

public Boolean empty();

若堆栈中没有对象元素，则此方法返回true，否则返回false。

（2）构造函数

public Stack();

是栈类唯一的构造函数，创建堆栈时可以直接调用它。

（3）压栈操作

public Object push(Object item);

将指定对象压入栈中。

（4）弹栈操作

public Object pop();

将堆栈最上面的元素从栈中取出，并返回这个对象。

当然我们可以自己编写堆栈的方法，如例6.6。

【例6.6】定义和使用堆栈

/* Program name StackDemo.java

demonstrate stacks

*/

class StackInit

{

private int maxSize;

private double[] stackArray;

private int top;

public StackInit(int s) //构造器

{

maxSize = s; // 设置数组大小

stackArray = new double[maxSize]; // 建立数组

top = -1; // 没有数据

}

public void push(double j) // 数据压栈

{

stackArray[++top] = j; // 栈顶指针加1，数据入栈

}

public double pop() // 数据出栈

{

return stackArray[top--]; // 弹出数据,栈顶指针减1 }

public boolean isEmpty() // 判断堆栈是否为空

{

return (top == -1);//若为空则返回true

}

public boolean isFull() // true if stack is full

{

return (top == maxSize-1);

}

} // end class StackInit

class StackDemo

{

public static void main(String[] args)

{

StackInit theStack = new StackInit(10);

theStack.push(20); // 数据进栈

theStack.push(40);

theStack.push(60);

theStack.push(80);

while( !theStack.isEmpty() ) // 数据出栈，直到堆栈为空 {

double value = theStack.pop();

System.out.print(value);

System.out.print(" ");

} // end while

System.out.println("");

}

} // end class StackApp

StackDemo类中的main()方法创建了一个大小为10的堆栈，一开始把4个数压入堆栈，然后再出栈。输出结果如图6-7所示。

图6-7 【例6.6】的运行结果

注意数据输出的顺序刚好与数据入栈的顺序相反。

在这里，StackInit类中数据的类型为double型，你可以改变为其它需要的类型。用数组实现堆栈时，需要指定堆栈的初始大小，如果是链表实现，则可以不需要。

堆栈最大的特点就是“后进先出”，例如假设压栈的数据依次为“1，2，3，4，5”，则弹栈的顺序为“5，4，3，2，1”，压栈和弹栈操作也可以交叉进行，如弹出几个数据后又压入几个数据等。堆栈的应用有括号匹配的检验及递归方法的调用和返回等。

6.2.2 队列

队列(Queue)与堆栈相似，也是重要的线性数据结构，但堆栈是一种“先进先出”(FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。插入元素的一端称为队尾（rear），删除元素的一端称为队首（front）。如图6-8所示。

入队列

队列的例子在生活中有很多。例如，一条生产线；读卡片机上卡片信息的读入；排队购物等等都是队列的例子。在计算机操作系统中也存在着队列这种数据结构,例如当需要在只有一个CPU的计算机系统中运行多个任务时，因为计算机一次只能处理一个任务,其他的任务就被安排在一个专门的队列中排列等候；当前处理完毕时，CPU就从队列的输入端取出一个任务执行(减队过程)；而每当产生一个新的任务时，它都被送到队列的输入端等候(加队过程)，恰似我们日常生活中的排队，每一个任务都必须等候它前面的所有任务都执行完毕之后才能执行，最先进入队列的也最先出队服务，这就是“先进先出”的原则。另外打印机

缓冲池中的等待作业、网络服务中待处理的客户请求队列，也都是使用队列数据结构的例子。

队列的运算主要有：

（1）元素的入队运算enqueue(x)

它是在队列的尾部加入元素x。

（2）元素的出队运算dequeue()

它是从队列的头端删除一个元素，并返回出队元素的值或地址指针。

（3）判断队列空函数isEmpty()

它是判定队列中有无元素的函数，当队列为空时，返回真值，否则返回假值。

队列可以用顺序存储和链式存储两种存储结构实现，如果用顺序存储，则在存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。假设当前为队列分配的最大空间为7，则在队列的入队和出队过程中使得当队列处于图6-9所示时就不可插入新的队尾元素，否则会因数组的越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。一个较好的办法是将顺序队列臆造为一个环状的空间，称之为循环队列。

图6-9 队列未空但无法插入元素

【例6.7】定义和使用循环队列

/* Program name QueueDemo.java

demonstrate queue

*/

class Queue

{

private int maxSize;

private int[] queArray;

private int front;

private int rear;

private int nItems;

public Queue(int s) // 构造器

{

maxSize = s;

queArray = new int[maxSize];

front = 0;

rear = -1;

nItems = 0;

}

public void enqueue(int x) // 入队

{

if(nItems!=maxSize) // 判断循环队列是否已满

{if(rear == maxSize-1)

rear = -1;

queArray[++rear] = x; // 队尾指针增1，元素x插入队列

nItems++; // 队列元素增1

}

else

System.out.println("队列已满！");

}

public int dequeue() // 出队

{

int temp = queArray[front++]; // 删除队头元素，队头指针增1 if(front == maxSize)

front = 0;

nItems--; // 队列元素减1

return temp;

}

public boolean isEmpty() // true if queue is empty

{

return (nItems==0);

}

} // end class Queue

class QueueDemo

{

public static void main(String[] args)

{

Queue theQueue = new Queue(5);

theQueue.enqueue(10); //入队

theQueue.enqueue(20);

theQueue.enqueue(30);

theQueue.enqueue(40);

theQueue.dequeue(); // 出队

theQueue.dequeue(); // (10, 20, 30)

theQueue.dequeue();

theQueue.enqueue(50); // 再入队

theQueue.enqueue(60);

theQueue.enqueue(70);

theQueue.enqueue(80);

while( !theQueue.isEmpty() ) // 出队且显示

{

int n = theQueue.dequeue(); // (40, 50, 60, 70, 80)

System.out.print(n);

System.out.print(" ");

}

System.out.println("");

} // end main()

} // end class QueueDemo

QueueDemo类中的main()方法创建了一个大小为5的队列，一开始插入数10，20，30，40到队列中，然后10，20，30出队，接着再把50，60，70，80入队，最后输出如图6-10所示。

图6-10 【例6.7】的运行结果

6.3 树

前面介绍的堆栈和队列都是线性数据，所谓线性数据结构是指其中的每个结点都只有一个前接结点和一个后续结点，这样所有的结点就排列成了线状的一列。但是在我们面临的实际问题和应用中，除了线性数据结构，还存在着大量的非线性数据结构，树就是非线性数据结构的典型代表。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在在数据库系统中，树形结构也是信息的重要组织形式之一。

树（Tree）是n（n≥0）个结点的有限集。在任意一棵非空树中：

（1）有且仅有一个特定的称为根（Root）的结点；

（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,…,T m，其中每一个集合本身又是一棵树，称为根的子树。

由定义可知，一棵树的每个结点都是某个子树的根。一个结点的子树的个数称为该结点的度，度为零的结点称为终端结点或叶结点，度不为零的结点称为分枝结点。

6.3.1 二叉树

一棵二叉树（Binary Tree）是有限元素的集合，它可以为空或者是包含一个称为树的根结点的元素，并且剩余的元素被分成两个不相交的子集，每个子集又是一棵二叉树，这两个子集被称为根的左右子树。二叉树的各结点只有一个前接结点，且最多能有两个后续结点。

图6-11 二叉树

图6-11显示了一棵简单的二叉树，它的形状像一棵倒长的树，其中的每个结点都只有一个前接结点，例如数据B结点的前接结点是数据A结点；每个结点可以有最多两个后续结点，例如数据C有数据F和数据G两个后续结点，数据D有数据H一个后续结点，而数据E、F、H、I都没有后续结点，称为叶结点，它们是二叉树的树叶。每一棵二叉树中都只有且只有一个特殊的没有前接结点的结点，称为根结点，图6-11中的数据A结点就是根结点，它就是二叉树的树根，通过它可以访问二叉树的所有其他结点。

与其它数据结构一样，树也有两种存储结构：顺序存储结构及链式存储结构。

1、顺序存储结构

顺序存储结构是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树（所有的结点其度数或者为零或者为2）上的结点元素。对于一般二叉树，应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。由于多数的二叉树不是完全二叉树，因此顺序存储方式将会导致存储空间的浪费。

2、链式存储结构

由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分之构成，表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域。下面的程序定义了一个TreeNode类来实现二叉树的链式存储。

class TreeNode //二叉树的结点类

{

TreeNode m_LeftChild; //左指针

TreeNode m_RightChild; //右指针

private int m_Data; //数据域

TreeNode (int newdata) //构造函数

{

m_Data = newdata;

m_LeftChild = null;

m_RightChild = null;

}

int getData()

{

return m_Data;

}

6.3.2 遍历二叉树

遍历（Traversing）就是按一定的规律和秩序访问树中的每一个结点，且仅仅只访问一次，在访问每个结点时，可以修改它的内容，打印信息或做其它的工作。

由二叉树的定义可知，二叉树是由三个基本单元组成：根结点、左子树和由子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有LDR、LRD、DLR、DRL、RLD、RDL六种遍历二叉树的方案。若限定先左后右，则只剩下三种情况：DLR、LDR、LRD，分别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历。遍历二叉树的操作定义如下：

1、先序遍历二叉树

若二叉树为空，则空操作；否则

（1）访问根结点

（2）先序遍历左子树

（3）先序遍历右子树

2、中序遍历二叉树

若二叉树为空，则空操作；否则

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

3、后序遍历二叉树

若二叉树为空，则空操作；否则

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点

对于图6-11所示的二叉树，其先序遍历的结果为ABDHECFGI；中序遍历的结果为DHBEAFCIG；后序遍历的结果为HDEBFIGCA。下面是中序遍历的递归算法：private void inOrder(TreeNode localRoot)

{

if(localRoot != null)

{

inOrder(localRoot.getLeftChild); //先访问左子树

localRoot.getData();//再访问当前根结点

inOrder(localRoot.getRightChild); //最后访问右子树

}

}

先序遍历及后序遍历的算法读者可以类似地写出，此处不一一列举。

6.3.3 二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树，对于二叉树中的任何一个结点，其左子树中的所有数据都小于该结点的数据，而其右子树中的所有数据都大于该结点的数据。

例如图6-12所示为一棵二叉排序树。

图 6-12 二叉排序树

由图可见，二叉排序树中右子树的所有数据都大于根结点的数据，也大于左子树的数据，这样，当我们利用二叉排序树查找一个数据时只要把该数据与根结点的数据相比较，若大于根结点的数据，则可以排除掉左子树而到右子树中继续查找；若小于根结点的数据则应到左子树中查找……，可以看出它的原理与折半查找是一致的，例6.8定义了二叉排序树。

【例6.8】创建及遍历二叉排序树，利用二叉排序树进行查找

/* Program name BSTree.java

一个二叉排序树的例子

*/

public class BSTree //定义主类，创建、遍历、查找二叉树

{

public static void main(String args[])

{

int[] data = {50,32,63,97,75,13,26,45}; //欲放入二叉树中的数据

int key1,key2; //欲查找的数据

BinaryTree searchTree = new BinaryTree(data[0]); //创建二叉树

if (args.length<2) //要求提供二命令行参数

{

System.out.println("请同时输入2个整型命令行参数");

System.exit(0);

}

for (int i=1;i

searchTree.insertToTree(data[i]); //将数据加入二叉树 System.out.println("先序遍历结果：");

System.out.println(searchTree.preOrder());

System.out.println("中序遍历结果：");

System.out.println(searchTree.inOrder());

System.out.println("后序遍历结果：");

System.out.println(searchTree.postOrder());

key1 = Integer.parseInt(args[0]);

key2 = Integer.parseInt(args[1]);

System.out.println("在树中查找数据" +key1+ ":"