二叉搜索树的讲解与实例分析
来源：爱站网时间：2018-12-05编辑：网友分享
二叉搜索树的讲解与实例分析，一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了数据外，还包括域left,right和p,它们分别指向结点的左儿子、右儿子，如果结点不存在，则为NULL。
二叉搜索树的讲解与实例分析，一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了数据外，还包括域left,right和p,它们分别指向结点的左儿子、右儿子，如果结点不存在，则为NULL。
它或者是一棵空树；或者是具有下列性质的二叉树：
1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
显然满足了上面的性质，那么二叉查找树按中序遍历就是按从小到大的顺序遍历，这也就是为什么叫排序树的原因，当然上面的小于和大于都可以根据自己的需求改变的。
二叉查找树的几个常用操作：查找，删除,插入.
HDU 3791:
Problem Description
判断两序列是否为同一二叉搜索树序列
Input
开始一个数n，(1
接下去一行是一个序列，序列长度小于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
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
}
result=root.printTree(root.getRoot());
for(int i=0;i
s=in.next();
for(int j=0;j
}
result1=root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
class BinaryNode> {//二叉查找树节点
BinaryNode left;
BinaryNode 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 getLeft(){
return this.left;
}
public BinaryNode getRight(){
return this.right;
}
public String toString(){
return element + "";
}
}
class BinarySearchTree>{//二叉搜索树
private BinaryNode root;//根节点
public BinarySearchTree(){//构造函数
root = null;
}
public BinarySearchTree(BinaryNode t){//构造函数
root = t;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public BinaryNode
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 find(T x, BinaryNode t){//查找操作
if(t == null){
return null;
}
if(x.compareTo(t.element) return find(x, t.left);
}
else if(x.compareTo(t.element) == 0){
return t;
}
else{
return find(x, t.right);
}
}
private BinaryNode insert(T x, BinaryNode t){//插入操作
if(t == null){
t = new BinaryNode(x, null, null);
}
else if(x.compareTo(t.element) 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){//前序遍历二叉查找树
if(t != null){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
return sb.toString();
}
}
到这里，二叉搜索树的讲解与实例分析的介绍就算完成了。如果有什么不清楚可以留言给我。如果觉得我写得不错的话，请给爱站技术频道一个关注，谢谢!
下一篇：Java匿名内部类实例剖析
