二叉搜索树实例练习

2019-11-26 16:17:55

字体：大中小

来源：转载

供稿：网友

一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了数据外，还包括域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(); 
} 
} 