二叉索引树java代码 二叉搜索树代码

Java中HashMap和TreeMap的区别深入理解

首先介绍一下什么是Map。在数组中二叉索引树java代码我们是通过数组下标来对其内容索引二叉索引树java代码的，而在Map中二叉索引树java代码我们通过对象来对对象进行索引，用来索引的对象叫做key，其对应的对象叫做value

首先介绍一下什么是Map。在数组中我们是通过数组下标来对其内容索引的，而在Map中我们通过对象来对对象进行索引，用来索引的对象叫做key，其对应的对象叫做value。这就是我们平时说的键值对。

HashMap通过hashcode对其内容进行快速查找，而

TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

HashMap 非线程安全 TreeMap 非线程安全

线程安全

在Java里，线程安全一般体现在两个方面二叉索引树java代码：

1、多个thread对同一个java实例的访问（read和modify）不会相互干扰，它主要体现在关键字synchronized。如ArrayList和Vector，HashMap和Hashtable

（后者每个方法前都有synchronized关键字）。如果你在interator一个List对象时，其它线程remove一个element，问题就出现二叉索引树java代码了。

2、每个线程都有自己的字段，而不会在多个线程之间共享。它主要体现在java.lang.ThreadLocal类，而没有Java关键字支持，如像static、transient那样。

1.AbstractMap抽象类和SortedMap接口

AbstractMap抽象类：(HashMap继承AbstractMap)覆盖了equals()和hashCode()方法以确保两个相等映射返回相同的哈希码。如果两个映射大小相等、包含同样的键且每个键在这两个映射中对应的值都相同，则这两个映射相等。映射的哈希码是映射元素哈希码的总和，其中每个元素是Map.Entry接口的一个实现。因此，不论映射内部顺序如何，两个相等映射会报告相同的哈希码。

SortedMap接口：（TreeMap继承自SortedMap）它用来保持键的有序顺序。SortedMap接口为映像的视图(子集)，包括两个端点提供了访问方法。除了排序是作用于映射的键以外，处理SortedMap和处理SortedSet一样。添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现。TreeMap类是它的唯一一份实现。

2.两种常规Map实现

HashMap：基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子。

(1)HashMap(): 构建一个空的哈希映像

(2)HashMap(Map m): 构建一个哈希映像，并且添加映像m的所有映射

(3)HashMap(int initialCapacity): 构建一个拥有特定容量的空的哈希映像

(4)HashMap(int

initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子的空的哈希映像

TreeMap：基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。

(1)TreeMap():构建一个空的映像树

(2)TreeMap(Map m): 构建一个映像树，并且添加映像m中所有元素

(3)TreeMap(Comparator c):

构建一个映像树，并且使用特定的比较器对关键字进行排序

(4)TreeMap(SortedMap s):

构建一个映像树，添加映像树s中所有映射，并且使用与有序映像s相同的比较器排序

3.两种常规Map性能

HashMap：适用于在Map中插入、删除和定位元素。

Treemap：适用于按自然顺序或自定义顺序遍历键(key)。

4.总结

HashMap通常比TreeMap快一点(树和哈希表的数据结构使然)，建议多使用HashMap，在需要排序的Map时候才用TreeMap。

复制代码

代码如下:

import java.util.HashMap;

import

java.util.Hashtable;

import java.util.Iterator;

import java.util.Map;

import java.util.TreeMap;

public class HashMaps {

public static void

main(String[] args) {

MapString, String map = new HashMapString,

String();

map.put("a", "aaa");

map.put("b", "bbb");

map.put("c",

"ccc");

map.put("d", "ddd");

IteratorString iterator =

map.keySet().iterator();

while (iterator.hasNext()) {

Object key =

iterator.next();

System.out.println("map.get(key) is :" + map.get(key));

}

// 定义HashTable,用来测试

HashtableString, String tab = new

HashtableString, String();

tab.put("a", "aaa");

tab.put("b",

"bbb");

tab.put("c", "ccc");

tab.put("d", "ddd");

IteratorString iterator_1 = tab.keySet().iterator();

while

(iterator_1.hasNext()) {

Object key = iterator_1.next();

System.out.println("tab.get(key) is :" + tab.get(key));

}

TreeMapString, String tmp = new TreeMapString, String();

tmp.put("a", "aaa");

tmp.put("b", "bbb");

tmp.put("c", "ccc");

tmp.put("d", "cdc");

IteratorString iterator_2 =

tmp.keySet().iterator();

while (iterator_2.hasNext()) {

Object key =

iterator_2.next();

System.out.println("tmp.get(key) is :" + tmp.get(key));

}

}

}

运行结果如下：

map.get(key) is :ddd

map.get(key) is :bbb

map.get(key) is :ccc

map.get(key) is :aaa

tab.get(key) is :bbb

tab.get(key) is :aaa

tab.get(key) is :ddd

tab.get(key) is :ccc

tmp.get(key) is :aaa

tmp.get(key) is :bbb

tmp.get(key) is :ccc

tmp.get(key) is :cdc

HashMap的结果是没有排序的，而TreeMap输出的结果是排好序的。

下面就要进入本文的主题了。先举个例子说明一下怎样使用HashMap:

复制代码

代码如下:

import java.util.*;

public class Exp1 {

public static void main(String[] args){

HashMap h1=new HashMap();

Random r1=new Random();

for (int i=0;i1000;i++){

Integer t=new

Integer(r1.nextInt(20));

if (h1.containsKey(t))

((Ctime)h1.get(t)).count++;

else

h1.put(t, new Ctime());

}

System.out.println(h1);

}

}

class Ctime{

int count=1;

public String toString(){

return Integer.toString(count);

}

}

在HashMap中通过get()来获取value，通过put()来插入value，ContainsKey()则用来检验对象是否已经存在。可以看出，和ArrayList的操作相比，HashMap除了通过key索引其内容之外，别的方面差异并不大。

前面介绍了，HashMap是基于HashCode的，在所有对象的超类Object中有一个HashCode()方法，但是它和equals方法一样，并不能适用于所有的情况，这样我们就需要重写自己的HashCode()方法。下面就举这样一个例子：

复制代码

代码如下:

import java.util.*;

public class Exp2 {

public static void main(String[] args){

HashMap h2=new HashMap();

for (int i=0;i10;i++)

h2.put(new Element(i), new Figureout());

System.out.println("h2:");

System.out.println("Get the result for

Element:");

Element test=new Element(5);

if (h2.containsKey(test))

System.out.println((Figureout)h2.get(test));

else

System.out.println("Not found");

}

}

class Element{

int

number;

public Element(int n){

number=n;

}

}

class

Figureout{

Random r=new Random();

boolean

possible=r.nextDouble()0.5;

public String toString(){

if (possible)

return "OK!";

else

return "Impossible!";

}

}

在这个例子中，Element用来索引对象Figureout,也即Element为key，Figureout为value。在Figureout中随机生成一个浮点数，如果它比0.5大，打印"OK!"，否则打印"Impossible!"。之后查看Element(3)对应的Figureout结果如何。

结果却发现，无论你运行多少次，得到的结果都是"Not found"。也就是说索引Element(3)并不在HashMap中。这怎么可能呢？

原因得慢慢来说：Element的HashCode方法继承自Object，而Object中的HashCode方法返回的HashCode对应于当前的地址，也就是说对于不同的对象，即使它们的内容完全相同，用HashCode（）返回的值也会不同。这样实际上违背了我们的意图。因为我们在使用

HashMap时，希望利用相同内容的对象索引得到相同的目标对象，这就需要HashCode()在此时能够返回相同的值。在上面的例子中，我们期望 new

Element(i) (i=5)与

Elementtest=newElement(5)是相同的，而实际上这是两个不同的对象，尽管它们的内容相同，但它们在内存中的地址不同。因此很自然的，上面的程序得不到我们设想的结果。下面对Element类更改如下：

复制代码

代码如下:

class Element{

int number;

public

Element(int n){

number=n;

}

public int hashCode(){

return

number;

}

public boolean equals(Object o){

return (o instanceof

Element) (number==((Element)o).number);

}

}

在这里Element覆盖了Object中的hashCode()和equals()方法。覆盖hashCode()使其以number的值作为

hashcode返回，这样对于相同内容的对象来说它们的hashcode也就相同了。而覆盖equals()是为了在HashMap判断两个key是否相等时使结果有意义（有关重写equals()的内容可以参考我的另一篇文章《重新编写Object类中的方法》）。修改后的程序运行结果如下：

h2:

Get the result for Element:

Impossible!

请记住：如果你想有效的使用HashMap，你就必须重写在其的HashCode()。

还有两条重写HashCode()的原则：

[list=1]

不必对每个不同的对象都产生一个唯一的hashcode，只要你的HashCode方法使get()能够得到put()放进去的内容就可以了。即"不为一原则"。

生成hashcode的算法尽量使hashcode的值分散一些，不要很多hashcode都集中在一个范围内，这样有利于提高HashMap的性能。即"分散原则"。至于第二条原则的具体原因，有兴趣者可以参考Bruce

Eckel的《Thinking in Java》，在那里有对HashMap内部实现原理的介绍，这里就不赘述了。

掌握了这两条原则，你就能够用好HashMap编写自己的程序了。不知道大家注意没有，java.lang.Object中提供的三个方法：clone()，equals()和hashCode()虽然很典型，但在很多情况下都不能够适用，它们只是简单的由对象的地址得出结果。这就需要我们在自己的程序中重写它们，其实java类库中也重写了千千万万个这样的方法。利用面向对象的多态性——覆盖，Java的设计者很优雅的构建了Java的结构，也更加体现了Java是一门纯OOP语言的特性。

二叉树索引原理是什么？

索引是为检索而存在的。如一些书籍的末尾就专门附有索引，指明二叉索引树java代码了某个关键字在正文中的出现的页码位置，方便我们查找，但大多数的书籍只有目录，目录不是索引，只是书中内容的排序，并不提供真正的检索功能。可见建立索引要单独占用空间；索引也并不是必须要建立的，它们只是为更好、更快的检索和定位关键字而存在。

再进一步说，我们要在图书馆中查阅图书，该怎么办呢？图书馆的前台有很多叫做索引卡片柜的小柜子，里面分了若干的类别供我们检索图书，比如二叉索引树java代码你可以用书名的笔画顺序或者拼音顺序作为查找的依据，二叉索引树java代码你还可以从作者名的笔画顺序或拼音顺序去查询想要的图书，反正有许多检索方式，但有一点很明白，书库中的书并没有按照这些卡片柜中的顺序排列——虽然理论上可以这样做，事实上，所有图书的脊背上都人工的粘贴了一个特定的编号①，它们是以这个顺序在排列。索引卡片中并没有指明这本书摆放在书库中的第几个书架的第几本，仅仅指明了这个特定的编号。管理员则根据这一编号将请求的图书返回到读者手中。这是很形象的例子，以下的讲解将会反复用到它。

JAVA题目

J2EE Java2平台企业版

string是引用数据类型

如何取得年月日，小时分秒

public static void main(String[] args)

{

ActionListener time = new ActionListener() { // 监听事件,不然实现不了动态改变时间

public void actionPerformed(ActionEvent e) {

//date对象代表当前的系统时间(毫秒)

Date date = new Date();

//format对象是用来以指定的时间格式格式化时间的

SimpleDateFormat from = new SimpleDateFormat(

"yyyy-MM-dd HH:mm:ss"); //这里的格式可以自己设置

//format()方法是用来格式化时间的方法

String times = from.format(date);

System.out.println(times); }

};

Timer tim = new Timer(1000, time); //这里表示1000毫秒更新一下时间

tim.start(); //启动

}

我这个答案肯定正确啊

下面帮你解释你的答案吧

Date //是在java.util.Date;里面

SimpleDateForma //这个是java.text.SimpleDateFormat;用来输出问本格式的

DateFormat //应该是在java.util.*;里面吧..应该是的

你那个错误是编译就没通过啊

public class Test

那你那个编译写的因该是

javac Test.java 编译的应该是类啊而不是javac time.java 请问你的time什么意思呢,所以你报的异常是找不到time类啊

呵呵...你是初学java吧该答的我都答完了拉!还特地帮你每句都写

如何读写文件

StringBuffer sb = new StringBuffer();

//File file = new FileWindow().load();

File file;

file = new File("F:/jtest/from.txt");

TextReader tr = new TextReader(file);

sb.append(tr.readAll());

Out.println(sb.toString());

String [] tags = {"\"", " ", "'"};

String str;

str = sb.toString();

for(String reg: tags) {

Out.println(reg);

str = str.replaceAll(reg, "");

}

Out.println(str);

抽象类和接口的区别

声明方法的存在而不去实现它的类被叫做抽象类（abstract class），它用于要创建一个体现某些基本行为的类，并为该类声明方法，但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量，其类型是一个抽象类，并让它指向具体子类的一个实例。不能有抽象构造函数或抽象静态方法。Abstract 类的子类为它们父类中的所有抽象方法提供实现，否则它们也是抽象类为。取而代之，在子类中实现该方法。知道其行为的其它类可以在类中实现这些方法。

接口（interface）是抽象类的变体。在接口中，所有方法都是抽象的。多继承性可通过实现这样的接口而获得。接口中的所有方法都是抽象的，没有一个有程序体。接口只可以定义static final成员变量。接口的实现与子类相似，除了该实现类不能从接口定义中继承行为。当类实现特殊接口时，它定义（即将程序体给予）所有这种接口的方法。然后，它可以在实现了该接口的类的任何对象上调用接口的方法。由于有抽象类，它允许使用接口名作为引用变量的类型。通常的动态联编将生效。引用可以转换到接口类型或从接口类型转换，instanceof 运算符可以用来决定某对象的类是否实现了接口。

主键是确定数据库中的表的记录的唯一标识字段，可以是表中的一个字段，也可以是表中的多个字段组成的。一旦确定为主键，则该字段不可为空也不可以重复。比如学生表中的学号就可以定义成该表的字段

外键的定义是相对于主键而言的，比如另有一张成绩表，表中也出现了学生表中的对应学号字段，则相对于学生表，学号就是成绩表的外键

String和StringBuffer的区别

STRING的长度是不可变的，STRINGBUFFER的长度是可变的。如果你对字符串中的内容经常进行操作，特别是内容要修改时，那么使用StringBuffer，如果最后需要String，那么使用StringBuffer的toString()方法

try{}catch(){}finally{}结构，try{}内出现异常，try{}内剩下尚未执行的代码还执行吗，finally{}内的代码呢？finally{}后面的代码呢

执行 finally{}内的代码最后执行

排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

分类

在计算机科学所使用的排序算法通常被分类为：

计算的复杂度（最差、平均、和最好表现），依据串列（list）的大小（n）。一般而言，好的表现是O。(n log n)，且坏的行为是Ω(n2)。对於一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。

记忆体使用量（以及其他电脑资源的使用）

稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。

一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。

当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7) (5, 6)

在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：

(3, 1) (3, 7) (4, 1) (5, 6) (维持次序)

(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个物件间之比较，就会被决定使用在原先资料次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

排列算法列表

在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。

稳定的

冒泡排序（bubble sort） — O(n2)

鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)

插入排序 （insertion sort）— O(n2)

桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体

计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体

归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体

原地归并排序 — O(n2)

二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体

鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体

基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体

Gnome sort — O(n2)

Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体

不稳定

选择排序 （selection sort）— O(n2)

希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本

Comb sort — O(n log n)

堆排序 （heapsort）— O(n log n)

Smoothsort — O(n log n)

快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序

Introsort — O(n log n)

Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）

不实用的排序算法

Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。

Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体

Bead sort — O(n) or O(√n), 但需要特别的硬体

Pancake sorting — O(n), 但需要特别的硬体

排序的算法

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

插入排序

冒泡排序

选择排序

快速排序

堆排序

归并排序

基数排序

希尔排序

插入排序

插入排序是这样实现的：

首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。

从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。

重复2号步骤，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。

冒泡排序

冒泡排序是这样实现的：

首先将所有待排序的数字放入工作列表中。

从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。

重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。

选择排序

选择排序是这样实现的：

设数组内存放了n个待排数字，数组下标从1开始，到n结束。

i=1

从数组的第i个元素开始到第n个元素，寻找最小的元素。

将上一步找到的最小元素和第i位元素交换。

如果i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n²)的。

快速排序

现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。

堆排序

堆排序与前面的算法都不同，它是这样的：

首先新建一个空列表，作用与插入排序中的"有序列表"相同。

找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。

重复2号步骤，直至原数列为空。

堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。

看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。

平均时间复杂度

插入排序 O(n2)

冒泡排序 O(n2)

选择排序 O(n2)

快速排序 O(n log n)

堆排序 O(n log n)

归并排序 O(n log n)

基数排序 O(n)

希尔排序 O(n1.25)

一、术语session

在我的经验里，session这个词被滥用的程度大概仅次于transaction，更加有趣的是transaction与session在某些语境下的含义是相同的。

session，中文经常翻译为会话，其本来的含义是指有始有终的一系列动作/消息，比如打电话时从拿起电话拨号到挂断电话这中间的一系列过程可以称之为一个session。有时候我们可以看到这样的话“在一个浏览器会话期间，...”，这里的会话一词用的就是其本义，是指从一个浏览器窗口打开到关闭这个期间①。最混乱的是“用户（客户端）在一次会话期间”这样一句话，它可能指用户的一系列动作（一般情况下是同某个具体目的相关的一系列动作，比如从登录到选购商品到结账登出这样一个网上购物的过程，有时候也被称为一个transaction），然而有时候也可能仅仅是指一次连接，也有可能是指含义①，其中的差别只能靠上下文来推断②。

然而当session一词与网络协议相关联时，它又往往隐含了“面向连接”和/或“保持状态”这样两个含义，“面向连接”指的是在通信双方在通信之前要先建立一个通信的渠道，比如打电话，直到对方接了电话通信才能开始，与此相对的是写信，在你把信发出去的时候你并不能确认对方的地址是否正确，通信渠道不一定能建立，但对发信人来说，通信已经开始了。“保持状态”则是指通信的一方能够把一系列的消息关联起来，使得消息之间可以互相依赖，比如一个服务员能够认出再次光临的老顾客并且记得上次这个顾客还欠店里一块钱。这一类的例子有“一个TCP session”或者“一个POP3 session”③。

而到了web服务器蓬勃发展的时代，session在web开发语境下的语义又有了新的扩展，它的含义是指一类用来在客户端与服务器之间保持状态的解决方案④。有时候session也用来指这种解决方案的存储结构，如“把xxx保存在session里”⑤。由于各种用于web开发的语言在一定程度上都提供了对这种解决方案的支持，所以在某种特定语言的语境下，session也被用来指代该语言的解决方案，比如经常把Java里提供的javax.servlet.http.HttpSession简称为session⑥。

鉴于这种混乱已不可改变，本文中session一词的运用也会根据上下文有不同的含义，请大家注意分辨。

在本文中，使用中文“浏览器会话期间”来表达含义①，使用“session机制”来表达含义④，使用“session”表达含义⑤，使用具体的“HttpSession”来表达含义⑥

二、HTTP协议与状态保持

HTTP协议本身是无状态的，这与HTTP协议本来的目的是相符的，客户端只需要简单的向服务器请求下载某些文件，无论是客户端还是服务器都没有必要纪录彼此过去的行为，每一次请求之间都是独立的，好比一个顾客和一个自动售货机或者一个普通的（非会员制）大卖场之间的关系一样。

然而聪明（或者贪心？）的人们很快发现如果能够提供一些按需生成的动态信息会使web变得更加有用，就像给有线电视加上点播功能一样。这种需求一方面迫使HTML逐步添加了表单、脚本、DOM等客户端行为，另一方面在服务器端则出现了CGI规范以响应客户端的动态请求，作为传输载体的HTTP协议也添加了文件上载、cookie这些特性。其中cookie的作用就是为了解决HTTP协议无状态的缺陷所作出的努力。至于后来出现的session机制则是又一种在客户端与服务器之间保持状态的解决方案。

让我们用几个例子来描述一下cookie和session机制之间的区别与联系。笔者曾经常去的一家咖啡店有喝5杯咖啡免费赠一杯咖啡的优惠，然而一次性消费5杯咖啡的机会微乎其微，这时就需要某种方式来纪录某位顾客的消费数量。想象一下其实也无外乎下面的几种方案：

1、该店的店员很厉害，能记住每位顾客的消费数量，只要顾客一走进咖啡店，店员就知道该怎么对待了。这种做法就是协议本身支持状态。

2、发给顾客一张卡片，上面记录着消费的数量，一般还有个有效期限。每次消费时，如果顾客出示这张卡片，则此次消费就会与以前或以后的消费相联系起来。这种做法就是在客户端保持状态。

3、发给顾客一张会员卡，除了卡号之外什么信息也不纪录，每次消费时，如果顾客出示该卡片，则店员在店里的纪录本上找到这个卡号对应的纪录添加一些消费信息。这种做法就是在服务器端保持状态。

由于HTTP协议是无状态的，而出于种种考虑也不希望使之成为有状态的，因此，后面两种方案就成为现实的选择。具体来说cookie机制采用的是在客户端保持状态的方案，而session机制采用的是在服务器端保持状态的方案。同时我们也看到，由于采用服务器端保持状态的方案在客户端也需要保存一个标识，所以session机制可能需要借助于cookie机制来达到保存标识的目的，但实际上它还有其他选择。

三、理解cookie机制

cookie机制的基本原理就如上面的例子一样简单，但是还有几个问题需要解决：“会员卡”如何分发；“会员卡”的内容；以及客户如何使用“会员卡”。

正统的cookie分发是通过扩展HTTP协议来实现的，服务器通过在HTTP的响应头中加上一行特殊的指示以提示浏览器按照指示生成相应的cookie。然而纯粹的客户端脚本如JavaScript或者VBScript也可以生成cookie。

而cookie的使用是由浏览器按照一定的原则在后台自动发送给服务器的。浏览器检查所有存储的cookie，如果某个cookie所声明的作用范围大于等于将要请求的资源所在的位置，则把该cookie附在请求资源的HTTP请求头上发送给服务器。意思是麦当劳的会员卡只能在麦当劳的店里出示，如果某家分店还发行了自己的会员卡，那么进这家店的时候除了要出示麦当劳的会员卡，还要出示这家店的会员卡。

cookie的内容主要包括：名字，值，过期时间，路径和域。

其中域可以指定某一个域比如.google.com，相当于总店招牌，比如宝洁公司，也可以指定一个域下的具体某台机器比如或者froogle.google.com，可以用飘柔来做比。

路径就是跟在域名后面的URL路径，比如/或者/foo等等，可以用某飘柔专柜做比。

路径与域合在一起就构成了cookie的作用范围。

如果不设置过期时间，则表示这个cookie的生命期为浏览器会话期间，只要关闭浏览器窗口，cookie就消失了。这种生命期为浏览器会话期的cookie被称为会话cookie。会话cookie一般不存储在硬盘上而是保存在内存里，当然这种行为并不是规范规定的。如果设置了过期时间，浏览器就会把cookie保存到硬盘上，关闭后再次打开浏览器，这些cookie仍然有效直到超过设定的过期时间。

存储在硬盘上的cookie可以在不同的浏览器进程间共享，比如两个IE窗口。而对于保存在内存里的cookie，不同的浏览器有不同的处理方式。对于IE，在一个打开的窗口上按Ctrl-N（或者从文件菜单）打开的窗口可以与原窗口共享，而使用其他方式新开的IE进程则不能共享已经打开的窗口的内存cookie；对于Mozilla Firefox0.8，所有的进程和标签页都可以共享同样的cookie。一般来说是用javascript的window.open打开的窗口会与原窗口共享内存cookie。浏览器对于会话cookie的这种只认cookie不认人的处理方式经常给采用session机制的web应用程序开发者造成很大的困扰。

下面就是一个goolge设置cookie的响应头的例子

HTTP/1.1 302 Found

Location:

Set-Cookie: PREF=ID=0565f77e132de138:NW=1:TM=1098082649:LM=1098082649:S=KaeaCFPo49RiA_d8; expires=Sun, 17-Jan-2038 19:14:07 GMT; path=/; domain=.google.com

Content-Type: text/html

这是使用HTTPLook这个HTTP Sniffer软件来俘获的HTTP通讯纪录的一部分

浏览器在再次访问goolge的资源时自动向外发送cookie

使用Firefox可以很容易的观察现有的cookie的值

使用HTTPLook配合Firefox可以很容易的理解cookie的工作原理。

IE也可以设置在接受cookie前询问

这是一个询问接受cookie的对话框。

四、理解session机制

session机制是一种服务器端的机制，服务器使用一种类似于散列表的结构（也可能就是使用散列表）来保存信息。

当程序需要为某个客户端的请求创建一个session的时候，服务器首先检查这个客户端的请求里是否已包含了一个session标识 - 称为session id，如果已包含一个session id则说明以前已经为此客户端创建过session，服务器就按照session id把这个session检索出来使用（如果检索不到，可能会新建一个），如果客户端请求不包含session id，则为此客户端创建一个session并且生成一个与此session相关联的session id，session id的值应该是一个既不会重复，又不容易被找到规律以仿造的字符串，这个session id将被在本次响应中返回给客户端保存。

保存这个session id的方式可以采用cookie，这样在交互过程中浏览器可以自动的按照规则把这个标识发挥给服务器。一般这个cookie的名字都是类似于SEEESIONID，而。比如weblogic对于web应用程序生成的cookie，JSESSIONID=ByOK3vjFD75aPnrF7C2HmdnV6QZcEbzWoWiBYEnLerjQ99zWpBng!-145788764，它的名字就是JSESSIONID。

由于cookie可以被人为的禁止，必须有其他机制以便在cookie被禁止时仍然能够把session id传递回服务器。经常被使用的一种技术叫做URL重写，就是把session id直接附加在URL路径的后面，附加方式也有两种，一种是作为URL路径的附加信息，表现形式为;jsessionid=ByOK3vjFD75aPnrF7C2HmdnV6QZcEbzWoWiBYEnLerjQ99zWpBng!-145788764

另一种是作为查询字符串附加在URL后面，表现形式为

这两种方式对于用户来说是没有区别的，只是服务器在解析的时候处理的方式不同，采用第一种方式也有利于把session id的信息和正常程序参数区分开来。

为了在整个交互过程中始终保持状态，就必须在每个客户端可能请求的路径后面都包含这个session id。

另一种技术叫做表单隐藏字段。就是服务器会自动修改表单，添加一个隐藏字段，以便在表单提交时能够把session id传递回服务器。比如下面的表单

form name="testform" action="/xxx"

input type="text"

/form

在被传递给客户端之前将被改写成

form name="testform" action="/xxx"

input type="hidden" name="jsessionid" value="ByOK3vjFD75aPnrF7C2HmdnV6QZcEbzWoWiBYEnLerjQ99zWpBng!-145788764"

input type="text"

/form

这种技术现在已较少应用，笔者接触过的很古老的iPlanet6(SunONE应用服务器的前身)就使用了这种技术。

实际上这种技术可以简单的用对action应用URL重写来代替。

在谈论session机制的时候，常常听到这样一种误解“只要关闭浏览器，session就消失了”。其实可以想象一下会员卡的例子，除非顾客主动对店家提出销卡，否则店家绝对不会轻易删除顾客的资料。对session来说也是一样的，除非程序通知服务器删除一个session，否则服务器会一直保留，程序一般都是在用户做log off的时候发个指令去删除session。然而浏览器从来不会主动在关闭之前通知服务器它将要关闭，因此服务器根本不会有机会知道浏览器已经关闭，之所以会有这种错觉，是大部分session机制都使用会话cookie来保存session id，而关闭浏览器后这个session id就消失了，再次连接服务器时也就无法找到原来的session。如果服务器设置的cookie被保存到硬盘上，或者使用某种手段改写浏览器发出的HTTP请求头，把原来的session id发送给服务器，则再次打开浏览器仍然能够找到原来的session。

恰恰是由于关闭浏览器不会导致session被删除，迫使服务器为seesion设置了一个失效时间，当距离客户端上一次使用session的时间超过这个失效时间时，服务器就可以认为客户端已经停止了活动，才会把session删除以节省存储空间。

五、理解javax.servlet.http.HttpSession

HttpSession是Java平台对session机制的实现规范，因为它仅仅是个接口，具体到每个web应用服务器的提供商，除了对规范支持之外，仍然会有一些规范里没有规定的细微差异。这里我们以BEA的Weblogic Server8.1作为例子来演示。

首先，Weblogic Server提供了一系列的参数来控制它的HttpSession的实现，包括使用cookie的开关选项，使用URL重写的开关选项，session持久化的设置，session失效时间的设置，以及针对cookie的各种设置，比如设置cookie的名字、路径、域，cookie的生存时间等。

一般情况下，session都是存储在内存里，当服务器进程被停止或者重启的时候，内存里的session也会被清空，如果设置了session的持久化特性，服务器就会把session保存到硬盘上，当服务器进程重新启动或这些信息将能够被再次使用，Weblogic Server支持的持久性方式包括文件、数据库、客户端cookie保存和复制。

复制严格说来不算持久化保存，因为session实际上还是保存在内存里，不过同样的信息被复制到各个cluster内的服务器进程中，这样即使某个服务器进程停止工作也仍然可以从其他进程中取得session。

cookie生存时间的设置则会影响浏览器生成的cookie是否是一个会话cookie。默认是使用会话cookie。有兴趣的可以用它来试验我们在第四节里提到的那个误解。

cookie的路径对于web应用程序来说是一个非常重要的选项，Weblogic Server对这个选项的默认处理方式使得它与其他服务器有明显的区别。后面我们会专题讨论。

关于session的设置参考[5]

~~我要200分~~

九宫格拼图·求此问题解法~~思路~代码都可~~就是关于其还原算法的·急~在线等~多谢哈

在一个3×3的九宫中有1－8这8个数及一个空格随机的摆放在其中的格子里，如图1－1所示。现在要求实现这个问题：将其调整为如图1－1右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。

（图1－1）

二、题目分析：

这是人工智能中的经典难题之一，问题是在3×3方格棋盘中，放8格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图1－2到图1－3的转换）。

（图1－2） （图1－3）

该问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图1－2我们就可以表示成｛8，7，1，5，2，6，3，4，0｝其中0代表空格。

在这个数组中我们首先计算它能够重排列出来的结果，公式就是：

∑（F（X））＝Y，其中F（X）

是一个数前面比这个数小的数的个数,Y为奇数和偶数时各有一种解法。（八数码问题是否有解的判定 ）

上面的数组可以解出它的结果。

F（8）＝0；

F（7）＝0；

F（1）＝0；

F（5）＝1；

F（2）＝1；

F（6）＝3；

F（3）＝2；

F（4）＝3；

Y＝0＋0＋0＋1＋1＋3＋2＋3＝10

Y＝10是偶数，所以其重排列就是如图1－3的结果，如果加起来的结果是奇数重排的结果就是如图1－1最右边的排法。

三、算法分析

求解方法就是交换空格（0）位置，直至到达目标位置为止。图形表示就是：

（图3－1）

要想得到最优的就需要使用广度优先搜索，九宫的所以排列有9！种，也就是362880种排法，数据量是非常大的，使用广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，可以把数据进行适当的压缩。使用DWORD形式保存，压缩形式是每个数字用3位表示，这样就是3×9＝27个字节，由于8的二进制表示形式1000，不能用3位表示，使用了一个小技巧就是将8表示为000，然后用多出来的5个字表示8所在的位置，就可以用DWORD表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。

类结构如下：

class CNineGird

{

public:

struct PlaceList

{

DWORD Place;

PlaceList* Left;

PlaceList* Right;

};

struct Scanbuf

{

DWORD Place;

int ScanID;

};

struct PathList

{

unsigned char Path[9];

};

private:

PlaceList *m_pPlaceList;

Scanbuf *m_pScanbuf;

RECT m_rResetButton;

RECT m_rAutoButton;

public:

int m_iPathsize;

clock_t m_iTime;

UINT m_iStepCount;

unsigned char m_iTargetChess[9];

unsigned char m_iChess[9];

HWND m_hClientWin;

PathList *m_pPathList;

bool m_bAutoRun;

private:

inline bool AddTree(DWORD place , PlaceList* parent);

void FreeTree(PlaceList* parent);

inline void ArrayToDword(unsigned char *array , DWORD data);

inline void DwordToArray(DWORD data , unsigned char *array);

inline bool MoveChess(unsigned char *array , int way);

bool EstimateUncoil(unsigned char *array);

void GetPath(UINT depth);

public:

void MoveChess(int way);

bool ComputeFeel();

void ActiveShaw(HWND hView);

void DrawGird(HDC hDC , RECT clientrect);

void DrawChess(HDC hDC , RECT clientrect);

void Reset();

void OnButton(POINT pnt , HWND hView);

public:

CNineGird();

~CNineGird();

};

计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么。代码：

void CNineGird::Reset()

{

if(m_bAutoRun) return;

vector vs;

int i;

for (i = 1 ; i 9 ; i ++)

vs.push_back(i);

vs.push_back(0);

random_shuffle(vs.begin(), vs.end());

random_shuffle(vs.begin(), vs.end());

for ( i = 0 ; i 9 ; i ++)

{

m_iChess[i] = vs[i];

}

if (!EstimateUncoil(m_iChess))

{

unsigned char array[9] = {1,2,3,8,0,4,7,6,5};

memcpy(m_iTargetChess , array , 9);

}

else

{

unsigned char array[9] = {1,2,3,4,5,6,7,8,0};

memcpy(m_iTargetChess , array , 9);

}

m_iStepCount = 0;

}

数据压缩函数实现：

inline void CNineGird::ArrayToDword(unsigned char *array , DWORD data)

{

unsigned char night = 0;

for ( int i = 0 ; i 9 ; i ++)

{

if (array[i] == 8)

{

night = (unsigned char)i;

break;

}

}

array[night] = 0;

data = 0;

data = (DWORD)((DWORD)array[0] 29 | (DWORD)array[1] 26 |

(DWORD)array[2] 23 | (DWORD)array[3] 20 |

(DWORD)array[4] 17 | (DWORD)array[5] 14 |

(DWORD)array[6] 11 | (DWORD)array[7] 8 |

(DWORD)array[8] 5 | night);

array[night] = 8;

}

解压缩时跟压缩正好相反，解压代码：

inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)

{

unsigned char chtem;

for ( int i = 0 ; i 9 ; i ++)

{

chtem = (unsigned char)(data (32 - (i + 1) * 3) 0x00000007);

array[i] = chtem;

}

chtem = (unsigned char)(data 0x0000001F);

array[chtem] = 8;

}

由于可扩展的数据量非常的大，加上在保存的时候使用的是DWORD类型，将每一步数据都记录在一个排序二叉树中，按从小到大从左到有的排列，搜索的时候跟每次搜索将近万次的形式比较快几乎是N次方倍，把几个在循环中用到的函数声明为内联函数，并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度。二叉树插入代码：

inline bool CNineGird::AddTree(DWORD place , PlaceList* parent)

{

if (parent == NULL)

{

parent = new PlaceList();

parent-Left = parent-Right = NULL;

parent-Place = place;

return true;

}

if (parent-Place == place)

return false;

if (parent-Place place)

{

return AddTree(place , parent-Right);

}

return AddTree(place , parent-Left);

}

计算结果是奇数排列还是偶数排列的代码：

bool CNineGird::EstimateUncoil(unsigned char *array)

{

int sun = 0;

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

{

for ( int j = 0 ; j 9 ; j ++)

{

if (array[j] != 0)

{

if (array[j] == i +1 )

break;

if (array[j] i + 1)

sun++;

}

}

}

if (sun % 2 == 0)

return true;

else

return false;

}

移动到空格位的代码比较简单，只要计算是否会移动到框外面就可以了，并在移动的时候顺便计算一下是不是已经是目标结果，这是用来给用户手工移动是给与提示用的，代码：

inline bool CNineGird::MoveChess(unsigned char *array , int way)

{

int zero , chang;

bool moveok = false;

for ( zero = 0 ; zero 9 ; zero ++)

{

if (array[zero] == 0)

break;

}

POINT pnt;

pnt.x = zero % 3;

pnt.y = int(zero / 3);

switch(way)

{

case 0 : //up

if (pnt.y + 1 3)

{

chang = (pnt.y + 1) * 3 + pnt.x ;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

case 1 : //down

if (pnt.y - 1 -1)

{

chang = (pnt.y - 1) * 3 + pnt.x ;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

case 2 : //left

if (pnt.x + 1 3)

{

chang = pnt.y * 3 + pnt.x + 1;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

case 3 : //right

if (pnt.x - 1 -1)

{

chang = pnt.y * 3 + pnt.x - 1;

array[zero] = array[chang];

array[chang] = 0;

moveok = true;

}

break;

}

if (moveok !m_bAutoRun)

{

m_iStepCount ++ ;

DWORD temp1 ,temp2;

ArrayToDword(array , temp1);

ArrayToDword(m_iTargetChess , temp2);

if (temp1 == temp2)

{

MessageBox(NULL , "你真聪明这么快就搞定了!" , "^_^" , 0);

}

}

return moveok;

}

在进行广度搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，只要从子结点逆向搜索就可以得到最优搜索路径了。用变量m_iPathsize来记录总步数，具体函数代码：

void CNineGird::GetPath(UINT depth)

{

int now = 0 , maxpos = 100 ;

UINT parentid;

if (m_pPathList != NULL)

{

delete[] m_pPathList;

}

m_pPathList = new PathList[maxpos];

parentid = m_pScanbuf[depth].ScanID;

DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);

while(parentid != -1)

{

if (now == maxpos)

{

maxpos += 10;

PathList * temlist = new PathList[maxpos];

memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));

delete[] m_pPathList;

m_pPathList = temlist;

}

DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);

parentid = m_pScanbuf[parentid].ScanID;

}

m_iPathsize = now;

}

动态排列的演示函数最简单了，为了让主窗体有及时刷新的机会，启动了一个线程在需要主窗体刷新的时候，用Slee（UINT）函数来暂停一下线程就可以了。代码：

unsigned __stdcall MoveChessThread(LPVOID pParam)

{

CNineGird * pGird = (CNineGird *)pParam;

RECT rect;

pGird-m_iStepCount = 0;

::GetClientRect(pGird-m_hClientWin , rect);

for ( int i = pGird-m_iPathsize ; i 0 ; i --)

{

memcpy(pGird-m_iChess , pGird-m_pPathList[i].Path , 9);

pGird-m_iStepCount ++;

InvalidateRect( pGird-m_hClientWin , rect , false);

Sleep(300);

}

char msg[100];

sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGird-m_iTime);

MessageBox(NULL , msg , "~_~" , 0);

pGird-m_bAutoRun = false;

return 0L;

}

最后介绍一下搜索函数的原理，首先得到源数组，将其转换成DWORD型，与目标比较，如果相同完成，不同就交换一下数据和空格位置，加入二叉树，搜索下一个结果，直到没有步可走了，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，函数：

bool CNineGird::ComputeFeel()

{

unsigned char *array = m_iChess;

UINT i;

const int MAXSIZE = 362880;

unsigned char temparray[9];

DWORD target , fountain , parent , parentID = 0 , child = 1;

ArrayToDword(m_iTargetChess , target);

ArrayToDword(array , fountain);

if (fountain == target)

{

return false;

}

if (m_pScanbuf != NULL)

{

delete[] m_pScanbuf;

}

m_pScanbuf = new Scanbuf[MAXSIZE];

AddTree(fountain ,m_pPlaceList);

m_pScanbuf[ 0 ].Place = fountain;

m_pScanbuf[ 0 ].ScanID = -1;

clock_t tim = clock();

while(parentID MAXSIZE child MAXSIZE)

{

parent = m_pScanbuf[parentID].Place;

for ( i = 0 ; i 4 ; i ++) // 0 :UP , 1:Down ,2:Left,3:Right

{

DwordToArray(parent , temparray);

if (MoveChess(temparray,i)) //是否移动成功

{

ArrayToDword(temparray , fountain);

if (AddTree(fountain, m_pPlaceList)) //加入搜索数

{

m_pScanbuf[ child ].Place = fountain;

m_pScanbuf[ child ].ScanID = parentID;

if (fountain == target) //是否找到结果

{

m_iTime = clock() - tim;

GetPath(child);//计算路径

FreeTree(m_pPlaceList);

delete[] m_pScanbuf;

m_pScanbuf = NULL;

return true;

}

child ++;

}

}

} // for i

parentID++;

}

m_iTime = clock() - tim;

FreeTree(m_pPlaceList);

delete[] m_pScanbuf;

m_pScanbuf = NULL;

return false;

}

重要函数的介绍结束;下面是程序的运行结果和运算结果：

如何用Java实现树形结构啊？

package tree;

import java.util.LinkedList;

import java.util.List;

/**

* 功能二叉索引树java代码：把一个数组的值存入二叉树中二叉索引树java代码，然后进行3种方式的遍历

*

* 参考资料0:数据结构(C语言版)严蔚敏

*

* 参考资料1：

*

* 参考资料2：

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

public class BinTreeTraverse2 {

private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

private static ListNode nodeList = null;

/**

* 内部类：节点

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

private static class Node {

Node leftChild;

Node rightChild;

int data;

Node(int newData) {

leftChild = null;

rightChild = null;

data = newData;

}

}

public void createBinTree() {

nodeList = new LinkedListNode();

// 将一个数组的值依次转换为Node节点

for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {

nodeList.add(new Node(array[nodeIndex]));

}

// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树

for (int parentIndex = 0; parentIndex array.length / 2 - 1; parentIndex++) {

// 左孩子

nodeList.get(parentIndex).leftChild = nodeList

.get(parentIndex * 2 + 1);

// 右孩子

nodeList.get(parentIndex).rightChild = nodeList

.get(parentIndex * 2 + 2);

}

// 最后一个父节点:因为最后一个父节点可能没有右孩子二叉索引树java代码，所以单独拿出来处理

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList

.get(lastParentIndex * 2 + 1);

// 右孩子,如果数组的长度为奇数才建立右孩子

if (array.length % 2 == 1) {

nodeList.get(lastParentIndex).rightChild = nodeList

.get(lastParentIndex * 2 + 2);

}

}

/**

* 先序遍历

*

* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void preOrderTraverse(Node node) {

if (node == null)

return;

System.out.print(node.data + " ");

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

/**

* 中序遍历

*

* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void inOrderTraverse(Node node) {

if (node == null)

return;

inOrderTraverse(node.leftChild);

System.out.print(node.data + " ");

inOrderTraverse(node.rightChild);

}

/**

* 后序遍历

*

* 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已

*

* @param node

* 遍历的节点

*/

public static void postOrderTraverse(Node node) {

if (node == null)

return;

postOrderTraverse(node.leftChild);

postOrderTraverse(node.rightChild);

System.out.print(node.data + " ");

}

public static void main(String[] args) {

BinTreeTraverse2 binTree = new BinTreeTraverse2();

binTree.createBinTree();

// nodeList中第0个索引处的值即为根节点

Node root = nodeList.get(0);

System.out.println("先序遍历：");

preOrderTraverse(root);

System.out.println();

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

inOrderTraverse(root);

System.out.println();

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

postOrderTraverse(root);

}

}

二叉索引树java代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于二叉搜索树代码、二叉索引树java代码的信息别忘了在本站进行查找喔。