A binary search tree is organized according to the binary tree structure. Such a tree can be represented by a linked list structure, where each node is an object. In addition to data, the node also includes the fields left, right and p, which point to the left son and right son of the node respectively. If the node does not exist, it is NULL.
It is either an empty tree; or a binary tree with the following properties:
1) If the left subtree is not empty, then the values of all nodes on the left subtree are less than the value of its root node;
(2) If the right subtree is not empty, then the values of all nodes on the right subtree are greater than the value of its root node;
(3) The left and right subtrees are also binary search trees respectively;
Obviously the above properties are satisfied, then traversing the binary search tree in inorder means traversing in order from small to large, which is why it is called a sorting tree. Of course, the above less than and greater than can be changed according to your own needs.
Several common operations of binary search trees: search, delete, and insert.
HDU 3791:
Problem Description
Determine whether two sequences are the same binary search tree sequence
Input
Start with a number n, (1<=n<=20) means there are n numbers that need to be judged, and the input ends when n= 0.
The next line is a sequence. The length of the sequence is less than 10 and contains numbers (0~9). There are no repeated numbers. Based on this sequence, a binary search tree can be constructed.
There are n sequences in the next n lines. The format of each sequence is the same as the first sequence. Please determine whether these two sequences can form the same binary search tree.
Output
If the sequences are the same, output YES, otherwise output NO
Sample Input
2
567432
543267
576342
0
Sample Output
YES
NO
Explanation: After inserting the numbers in order, use binary tree pre-order traversal to determine whether the two binary trees are the same.
Java code
Copy the code code as follows:
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>> {//Binary search tree node
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 = <
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>>{//Binary search tree
private BinaryNode<T> root;//root node
public BinarySearchTree(){//Constructor
root = null;
}
public BinarySearchTree(BinaryNode< T> t){//Constructor
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){//Find operation
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){//Insert operation
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){//Pre-order traversal of the binary search tree
if(t != null){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
return sb.toString();
}
}
