当前位置:首页 > 开发 > 编程语言 > 搜索 > 正文

二叉搜索树练习 HDU3791

发表于: 2012-11-25   作者:128kj   来源:转载   浏览:
摘要:      一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象。结点中除了数据外,还包括域left,right和p,它们分别指向结点的左儿子、右儿子,如果结点不存在,则为NULL。 它或者是一棵空树;或者是具有下列性质的二叉树: 1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若
     一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象。结点中除了数据外,还包括域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();
	}
    
   
}

二叉搜索树练习 HDU3791

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
查看原题 题意 先给你一个数字n,接着是一串数字,你把它顺序扫描后建立一棵二叉搜索树。然后再陆续
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象
性质 二叉搜索树;对于树中的每一个节点 x,x 的左子树所有节点的 key 不大于 x.key;x 的右子树的 key
基本概念 二叉搜索树是以一棵二叉树来组织的。这样的一棵树可以使用一个链表数据结构来表示: 其中
二叉搜索树定义 二叉搜索树,又称为二叉排序树。Binary Search Tree,Binary Sort Tree,简写为BST
一、概述 二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序
二叉搜索树,亦称二叉查找树,二叉排序树,它满足以下性质: 可以为空树 不为空树时,若左子树存在
动态查找表的一种理想数据结构。 二叉排序树的定义是:二叉排序树T是一棵树,它或者是空,或者具备一
二叉搜索树是一种搜索树,通常的二分搜素算法有很好的搜索性能但是一般在顺序表上进行,插入和删除
第十章 二叉树 学习目的 学习广义树的定义,熟悉树的有关术语 理解树是一种非线性的数据结构 理解很
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号