二叉搜索树练习 HDU3791

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

解释：按顺序插入数字之后，再用二叉树先序遍历判断两颗二叉树是否相同。


   

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();
	}
    
   
}