一棵二元查找樹是按二元樹結構來組織的。這樣的樹可以用鍊錶結構表示，其中每一個結點都是一個物件。結點中除了數據外，還包括域left,right和p,它們分別指向結點的左兒子、右兒子，如果結點不存在，則為NULL。
它或是一棵空樹；或是具有下列性質的二元樹：
1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二元查找樹；
顯然滿足了上面的性質，那麼二元查找樹按中序遍歷就是按從小到大的順序遍歷，這也就是為什麼叫排序樹的原因，當然上面的小於和大於都可以根據自己的需求改變的。
二元查找樹的幾個常用操作：查找，刪除,插入.
HDU 3791:
Problem Description
判斷兩個序列是否為同一二元搜尋樹序列
Input
開始一個數n，(1<=n<=20) 表示有n個需要判斷，n= 0 的時候輸入結束。
接著一行是一個序列，序列長度小於10，包含(0~9)的數字，沒有重複數字，根據這個序列可以建構出一顆二元搜尋樹。
接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二元搜尋樹。
Output
若序列相同則輸出YES，否則輸出NO
Sample Input
2
567432
543267
576342
0
Sample Output
YES
NO
解釋：依序插入數字之後，再用二元樹先序遍歷判斷兩顆二元樹是否相同。
Java程式碼
複製代碼代碼如下:
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
BinarySearchTree<Character> root=null;
while(in.hasNext()){
int t=in.nextInt();
if(t==0) break;
root=new BinarySearchTree<Character>();
String result=null;
String result1=null;
String s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
result=root.printTree(root.getRoot());
for(int i=0;i<t;i++){
root=new BinarySearchTree<Character>();
s=in.next();
for(int j=0;j<s.length();j++){
root.insert(s.charAt(j));
}
result1=root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
class BinaryNode< T extends Comparable<T>> {//二元查找樹節點
BinaryNode< T> left;
BinaryNode< T> right;
T element;
public BinaryNode(T theElement){
this(theElement, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
element = theElement;
left = lt;
right = rt;
}
public T getElement(){
return this.element;
}
public BinaryNode< T> getLeft(){
return this.left;
}
public BinaryNode< T> getRight(){
return this.right;
}
public String toString(){
return element + "";
}
}
class BinarySearchTree< T extends Comparable<T>>{//二元搜尋樹
private BinaryNode< T> root;//根節點
public BinarySearchTree(){//建構函數
root = null;
}
public BinarySearchTree(BinaryNode< T> t){//建構子
root = t;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public BinaryNode<T> getRoot(){
return root;
}
public T find(T x){
return find(x, root).element;
}
public void insert(T x){
root = insert(x, root);
}
public void printTree(){
printTree(root);
}
private BinaryNode< T> find(T x, BinaryNode< T> t){//查找操作
if(t == null){
return null;
}
if(x.compareTo(t.element) < 0){
return find(x, t.left);
}
else if(x.compareTo(t.element) == 0){
return t;
}
else{
return find(x, t.right);
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//插入操作
if(t == null){
t = new BinaryNode< T>(x, null, null);
}
else if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
else if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}
else;
return t;
}
private StringBuffer sb=new StringBuffer();
public String printTree(BinaryNode< T> t){//前序遍歷二元查找樹
if(t != null){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
return sb.toString();
}
}
