Rumah >Java >javaTutorial >Menguji Kelas AVLTree

Menguji Kelas AVLTree

王林
王林asal
2024-07-25 09:09:31766semak imbas

Bahagian ini memberikan contoh penggunaan kelas AVLTree. Kod di bawah memberikan program ujian. Program ini mencipta AVLTree yang dimulakan dengan tatasusunan integer 25, 20 dan 5 (baris 7), memasukkan elemen dalam baris 11–20, dan memadamkan elemen dalam baris 24–30. Memandangkan AVLTree ialah subkelas BST dan elemen dalam BST boleh lelar, atur cara menggunakan gelung foreach untuk merentasi semua elemen dalam baris 35–37 .

package demo;

public class TestAVLTree {

    public static void main(String[] args) {
        // Create an AVL tree
        AVLTree<Integer> tree = new AVLTree<>(new Integer[]{25, 20, 5});
        System.out.print("After inserting 25, 20, 5:");
        printTree(tree);

        tree.insert(34);
        tree.insert(50);
        System.out.print("\nAfter inserting 34, 50:");
        printTree(tree);

        tree.insert(30);
        System.out.print("\nAfter inserting 30");
        printTree(tree);

        tree.insert(10);
        System.out.print("\nAfter inserting 10");
        printTree(tree);

        tree.delete(34);
        tree.delete(30);
        tree.delete(50);
        System.out.print("\nAfter removing 34, 30, 50:");
        printTree(tree);

        tree.delete(5);
        System.out.print("\nAfter removing 5:");
        printTree(tree);

        System.out.print("\nTraverse the elements in the tree: ");
        for (int e: tree) {
            System.out.print(e + " ");
        }
    }

    public static void printTree(BST tree) {
        // Traverse tree
        System.out.print("\nInorder (sorted): ");
        tree.inorder();
        System.out.print("\nPostorder: ");
        tree.postorder();
        System.out.print("\nPreorder: ");
        tree.preorder();
        System.out.print("\nThe number of nodes is " + tree.getSize());
        System.out.println();
    }
}

Selepas memasukkan 25, 20, 5:
Susun (diisih): 5 20 25
Pos pesanan: 5 25 20
Prapesanan: 20 5 25
Bilangan nod ialah 3

Selepas memasukkan 34, 50:
Susun (diisih): 5 20 25 34 50
Pos pesanan: 5 25 50 34 20
Prapesanan: 20 5 34 25 50
Bilangan nod ialah 5

Selepas memasukkan 30
Susun (diisih): 5 20 25 30 34 50
Pos pesanan: 5 20 30 50 34 25
Prapesanan: 25 20 5 34 30 50
Bilangan nod ialah 6

Selepas memasukkan 10
Susun (diisih): 5 10 20 25 30 34 50
Pesanan pos: 5 20 10 30 50 34 25
Prapesanan: 25 10 5 20 34 30 50
Bilangan nod ialah 7

Selepas mengalih keluar 34, 30, 50:
Susun (diisih): 5 10 20 25
Pos pesanan: 5 20 25 10
Prapesanan: 10 5 25 20
Bilangan nod ialah 4

Selepas mengalih keluar 5:
Susun (diisih): 10 20 25
Pos pesanan: 10 25 20
Prapesanan: 20 10 25
Bilangan nod ialah 3

Lintas unsur dalam pokok: 10 20 25

Rajah di bawah menunjukkan bagaimana pokok itu berkembang apabila unsur ditambahkan pada pokok itu. Selepas 25 dan 20 ditambah, pokok itu adalah seperti yang ditunjukkan dalam Rajah di bawah (a). 5 dimasukkan sebagai anak kiri 20, seperti ditunjukkan dalam Rajah di bawah (b). Pokok tidak seimbang. Ia berat kiri pada nod 25. Lakukan putaran LL untuk menghasilkan pepohon AVL, seperti ditunjukkan dalam Rajah di bawah (c).

Selepas memasukkan 34, pokok itu ditunjukkan dalam Rajah di bawah (d). Selepas memasukkan 50, pokok itu adalah seperti yang ditunjukkan dalam Rajah di bawah (e). Pokok tidak seimbang. Ia berat betul pada nod 25. Lakukan putaran RR untuk menghasilkan pepohon AVL, seperti ditunjukkan dalam Rajah di bawah (f).

Selepas memasukkan 30, pokok adalah seperti yang ditunjukkan dalam Rajah di bawah (g). Pokok tidak seimbang. Lakukan putaran RL untuk menghasilkan pokok AVL, seperti ditunjukkan dalam Rajah di bawah (h).

Selepas memasukkan 10, pokok itu adalah seperti yang ditunjukkan dalam Rajah di bawah (i). Pokok tidak seimbang. Lakukan putaran LR untuk menghasilkan pokok AVL, seperti ditunjukkan dalam Rajah di bawah (j).

Image description

Rajah di bawah menunjukkan cara pokok itu berkembang apabila elemen dipadamkan. Selepas memadam 34, 30, dan 50, pokok itu adalah seperti yang ditunjukkan dalam Rajah di bawah (b). Pokok tidak seimbang. Lakukan putaran LL untuk menghasilkan pokok AVL, seperti yang ditunjukkan dalam Rajah di bawah (c).

Selepas memadam 5, pokok adalah seperti yang ditunjukkan dalam Rajah di bawah (d). Pokok tidak seimbang. Lakukan putaran RL untuk menghasilkan pokok AVL, seperti ditunjukkan dalam Rajah di bawah (e)

Testing the AVLTree Class

Atas ialah kandungan terperinci Menguji Kelas AVLTree. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn