二叉搜索树实例练习

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

while(in.hasNext()){

int t=in.nextInt();

if(t==0) break;

root=new BinarySearchTree();

String result=null;

String result1=null;

String s=in.next();

for(int i=0;i

root.insert(s.charAt(i));

}

result=root.printTree(root.getRoot());

for(int i=0;i

root=new BinarySearchTree();

s=in.next();

for(int j=0;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> {//二叉查找树节点

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>{//二叉搜索树

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

}

}