快捷導(dǎo)航

二叉搜索樹實例練習(xí)

更新時間：2012年11月26日 10:48:00 作者：

一棵二叉查找樹是按二叉樹結(jié)構(gòu)來組織的。這樣的樹可以用鏈表結(jié)構(gòu)表示，其中每一個結(jié)點都是一個對象

一棵二叉查找樹是按二叉樹結(jié)構(gòu)來組織的。這樣的樹可以用鏈表結(jié)構(gòu)表示，其中每一個結(jié)點都是一個對象。結(jié)點中除了數(shù)據(jù)外，還包括域left,right和p,它們分別指向結(jié)點的左兒子、右兒子，如果結(jié)點不存在，則為NULL。
它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：
1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
（3）左、右子樹也分別為二叉查找樹；
顯然滿足了上面的性質(zhì)，那么二叉查找樹按中序遍歷就是按從小到大的順序遍歷，這也就是為什么叫排序樹的原因，當(dāng)然上面的小于和大于都可以根據(jù)自己的需求改變的。
二叉查找樹的幾個常用操作：查找，刪除,插入.
HDU 3791:
Problem Description
判斷兩序列是否為同一二叉搜索樹序列
Input
開始一個數(shù)n，(1<=n<=20) 表示有n個需要判斷，n= 0 的時候輸入結(jié)束。
接下去一行是一個序列，序列長度小于10，包含(0~9)的數(shù)字，沒有重復(fù)數(shù)字，根據(jù)這個序列可以構(gòu)造出一顆二叉搜索樹。
接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜索樹。
Output
如果序列相同則輸出YES，否則輸出NO
Sample Input
2
567432
543267
576342
0
Sample Output
YES
NO
解釋：按順序插入數(shù)字之后，再用二叉樹先序遍歷判斷兩顆二叉樹是否相同。
Java代碼

復(fù)制代碼代碼如下:

 
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>> {//二叉查找樹節(jié)點 
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;//根節(jié)點 
public BinarySearchTree(){//構(gòu)造函數(shù) 
root = null; 
} 
public BinarySearchTree(BinaryNode< T> t){//構(gòu)造函數(shù) 
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(); 
} 
} 