Pohon pencarian biner disusun menurut struktur pohon biner. Pohon seperti itu dapat diwakili oleh struktur daftar tertaut, di mana setiap node adalah sebuah objek. Selain data, node juga menyertakan field kiri, kanan, dan p, yang masing-masing menunjuk ke anak kiri dan anak kanan dari node tersebut. Jika node tidak ada, maka NULL.
Ini bisa berupa pohon kosong; atau pohon biner dengan properti berikut:
1) Jika subpohon kiri tidak kosong, maka nilai semua node pada subpohon kiri lebih kecil dari nilai node akarnya;
(2) Jika subpohon kanan tidak kosong, maka nilai seluruh node pada subpohon kanan lebih besar dari nilai node akarnya;
(3) Subpohon kiri dan kanan masing-masing juga merupakan pohon pencarian biner;
Tentunya sifat-sifat di atas terpenuhi, maka melintasi pohon pencarian biner secara inorder berarti melintasi secara berurutan dari kecil ke besar, oleh karena itu disebut pohon pengurutan. Tentu saja, kurang dari dan lebih besar dari di atas dapat diubah sesuai keinginan Anda kebutuhan sendiri.
Beberapa operasi umum pohon pencarian biner: pencarian, penghapusan, dan penyisipan.
HDU 3791:
Deskripsi Masalah
Tentukan apakah dua urutan merupakan urutan pohon pencarian biner yang sama
Masukan
Dimulai dengan angka n, (1<=n<=20) berarti ada n angka yang perlu dinilai, dan input berakhir ketika n= 0.
Baris berikutnya adalah barisan. Panjang barisan kurang dari 10 dan berisi angka (0~9). Berdasarkan barisan ini, pohon pencarian biner dapat dibuat.
Terdapat n sequence pada n baris berikutnya. Format tiap sequence sama dengan sequence pertama. Tentukan apakah kedua sequence tersebut dapat membentuk pohon pencarian biner yang sama.
Keluaran
Jika urutannya sama, keluarkan YES, jika tidak, keluarkan NO
Contoh Masukan
2
567432
543267
576342
0
Contoh Keluaran
YA
TIDAK
Penjelasan: Setelah memasukkan angka secara berurutan, gunakan traversal pre-order pohon biner untuk menentukan apakah kedua pohon biner itu sama.
kode Jawa
Copy kode kodenya sebagai berikut:
impor java.util.Scanner;
kelas publik Utama{
public static void main(String args[]){
Pemindai masuk=Pemindai baru(Sistem.dalam);
BinarySearchTree<Karakter> root=null;
while(dalam.hasNext()){
int t=dalam.nextInt();
jika(t==0) pecah;
root=Pohon BinerSearchbaru<Karakter>();
Hasil string=null;
Hasil string1=null;
String s=masuk.berikutnya();
for(int i=0;i<s.panjang();i++){
root.masukkan(s.charAt(i));
}
hasil=root.printTree(root.getRoot());
untuk(int i=0;i<t;i++){
root=Pohon BinerSearchbaru<Karakter>();
s=masuk.berikutnya();
for(int j=0;j<s.panjang();j++){
root.masukkan(s.charAt(j));
}
hasil1=root.printTree(root.getRoot());
if(hasil.sama dengan(hasil1)) System.out.println("YA");
else System.out.println("TIDAK");
}
}
}
}
class BinaryNode< T extends Comparable<T>> {//Node pohon pencarian biner
BinerNode<T> kiri;
BinerNode<T> kanan;
elemen T;
BinerNode publik(T Elemen){
ini(Elemen, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
elemen = Elemen;
kiri = <
kanan = rt;
}
publik T getElement(){
kembalikan ini.elemen;
}
BinerNode publik<T> getLeft(){
kembalikan ini.kiri;
}
BinaryNode publik<T> getRight(){
kembalikan ini.kanan;
}
String publik keString(){
elemen kembali + "";
}
}
kelas BinarySearchTree< T extends Comparable<T>>{//Pohon pencarian biner
BinaryNode pribadi<T> akar;//simpul akar
publik BinarySearchTree(){//Konstruktor
akar = nol;
}
public BinarySearchTree(BinaryNode< T> t){//Konstruktor
akar = t;
}
kekosongan publik makeEmpty(){
akar = nol;
}
boolean publik isEmpty(){
kembalikan akar == nol;
}
BinaryNode publik<T> getRoot(){
kembalikan akar;
}
publik T temukan(T x){
kembali temukan(x, root).elemen;
}
sisipan kekosongan publik(T x){
akar = sisipkan(x, akar);
}
kekosongan publik printTree(){
printTree(akar);
}
BinaryNode pribadi< T> temukan(T x, BinaryNode< T> t){//Cari operasi
jika(t==nol){
kembalikan nol;
}
if(x.compareTo(t.element) < 0){
return find(x, t.kiri);
}
else if(x.compareTo(t.element) == 0){
kembali t;
}
kalau tidak{
return find(x, t.kanan);
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//Operasi penyisipan
jika(t==nol){
t = BinaryNode baru<T>(x, null, null);
}
else if(x.compareTo(t.element) < 0){
t.kiri = sisipkan(x, t.kiri);
}
else if(x.compareTo(t.element) > 0){
t.kanan = sisipkan(x, t.kanan);
}
kalau tidak;
kembali t;
}
pribadi StringBuffer sb=StringBuffer baru();
public String printTree(BinaryNode< T> t){//Traversal praorder pohon pencarian biner
jika(t != nol){
sb.append(t.elemen);
printTree(t.kiri);
printTree(t.kanan);
}
kembali sb.toString();
}
}
