แบบฝึกหัดตัวอย่างการค้นหาแบบไบนารี

คัดลอกรหัสรหัส ดังต่อไปนี้:

นำเข้า java.util.Scanner;
ชั้นเรียนสาธารณะหลัก{
โมฆะคงที่สาธารณะ main (String args []) {
สแกนเนอร์ใน = สแกนเนอร์ใหม่ (System.in);
BinarySearchTree<ตัวละคร> root=null;
ในขณะที่ (in.hasNext ()) {
int t=in.nextInt();
ถ้า(t==0) พัง;
root=new BinarySearchTree<ตัวละคร>();
ผลลัพธ์สตริง=null;
สตริง result1=null;
สตริง s=in.next();
สำหรับ(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
-
ผลลัพธ์=root.printTree(root.getRoot());
สำหรับ(int i=0;i<t;i++){
root=new BinarySearchTree<ตัวละคร>();
s=in.ถัดไป();
สำหรับ(int j=0;j<s.length();j++){
root.insert(s.charAt(เจ));
-
result1=root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("ใช่");
อื่น System.out.println("ไม่ใช่");
-
-
-
-
class BinaryNode< T ขยายการเปรียบเทียบ<T>> {//โหนดแผนผังการค้นหาแบบไบนารี
BinaryNode<T> ซ้าย;
BinaryNode<T> ขวา;
องค์ประกอบที;
BinaryNode สาธารณะ (T theElement) {
นี้ (องค์ประกอบ, โมฆะ, โมฆะ);
-
BinaryNode สาธารณะ (T theElement, BinaryNode lt, BinaryNode rt) {
องค์ประกอบ = องค์ประกอบ;
ซ้าย = <
ขวา = rt;
-
สาธารณะ T getElement(){
ส่งคืน this.element;
-
BinaryNode สาธารณะ <T> getLeft () {
กลับสิ่งนี้ซ้าย;
-
BinaryNode สาธารณะ <T> getRight () {
ส่งคืน this.right;
-
สตริงสาธารณะ toString(){
ส่งคืนองค์ประกอบ + "";
-
-
class BinarySearchTree< T ขยายการเปรียบเทียบ<T>>{//แผนผังการค้นหาแบบไบนารี
BinaryNode<T> ส่วนตัว root;//root node
BinarySearchTree(){//Constructor สาธารณะ
รูท = โมฆะ;
-
BinarySearchTree สาธารณะ (BinaryNode< T> t){//Constructor
รูต = เสื้อ;
-
โมฆะสาธารณะ makeEmpty(){
รูท = โมฆะ;
-
บูลีนสาธารณะ isEmpty(){
ส่งคืนรูท == null;
-
BinaryNode สาธารณะ<T> getRoot(){
คืนราก;
-
สาธารณะ T ค้นหา (T x) {
กลับค้นหา (x, root). องค์ประกอบ;
-
การแทรกโมฆะสาธารณะ (T x) {
รูท = แทรก (x, รูท);
-
โมฆะสาธารณะ printTree(){
printTree(ราก);
-
BinaryNode ส่วนตัว< T> ค้นหา (T x, BinaryNode< T> t){// ค้นหาการดำเนินการ
ถ้า(t==null){
กลับเป็นโมฆะ;
-
ถ้า(x.compareTo(t.องค์ประกอบ) < 0){
กลับค้นหา (x, t.left);
-
อื่นถ้า (x.compareTo (t.element) == 0) {
กลับที;
-
อื่น{
กลับค้นหา (x, t.right);
-
-
BinaryNode ส่วนตัว < T> แทรก (T x, BinaryNode < T> t){// การดำเนินการแทรก
ถ้า(t==null){
t = BinaryNode ใหม่<T>(x, null, null);
-
อื่นถ้า (x.compareTo (t.element) < 0) {
t.left = แทรก(x, t.left);
-
อื่นถ้า(x.compareTo(t.element) > 0){
t.right = แทรก(x, t.right);
-
อื่น;
กลับที;
-
StringBuffer ส่วนตัว sb = StringBuffer ใหม่ ();
public String printTree(BinaryNode< T> t){//สั่งการข้ามผ่านแผนผังการค้นหาแบบไบนารีล่วงหน้า
ถ้า(t != null){
sb.ผนวก(t.องค์ประกอบ);
printTree(t.ซ้าย);
printTree(t.ขวา);
-
กลับ sb.toString();
-
-