我要评论它或者是一棵空树；或者是具有下列性质的二叉树：
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();
}
}
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论