測試 AVLTree 類-java教程-PHP中文網

測試 AVLTree 類

王林

發布： 2024-07-25 09:09:31

原創

765 人瀏覽過

本節給出了使用 AVLTree 類別的範例。下面的程式碼給了一個測試程式。程式建立一個以整數陣列25、20 和5 初始化的AVLTree（第7 行），將元素插入第111 -20 行，並刪除第24-30 行中的元素。由於AVLTree 是BST 的子類，並且BST 中的元素是可迭代的，因此程式使用foreach 循環遍歷第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();
    }
}

登入後複製

插入 25、20、5 後：
Inorder（已排序）：5 20 25
郵購日期：5 25 20
預購：20 5 25
節點數為3

插入 34、50 後：
Inorder（已排序）：5 20 25 34 50
郵購：5 25 50 34 20
預購：20 5 34 25 50
節點數為5

插入30後
Inorder（已排序）：5 20 25 30 34 50
郵購：5 20 30 50 34 25
預購：25 20 5 34 30 50
節點數為6

插入 10 個後
Inorder（已排序）：5 10 20 25 30 34 50
郵購：5 20 10 30 50 34 25
預購：25 10 5 20 34 30 50
節點數為 7

刪除 34、30、50 後：
Inorder（已排序）：5 10 20 25
郵購：5 20 25 10
預購：10 5 25 20
節點數為4

刪除 5 個後：
Inorder（已排序）：10 20 25
郵購日期：10 25 20
預購：20 10 25
節點數為3

遍歷樹中的元素：10 20 25

下圖顯示了隨著元素添加到樹中，樹是如何演變的。加入25和20後，樹如下圖(a)所示。 5以20的左孩子插入，如下圖(b)所示。這棵樹不平衡。它在節點 25 處為左重。執行 LL 旋轉以產生 AVL 樹，如下圖 (c) 所示。

插入34後，樹如下圖(d)所示。插入50後，樹如下圖(e)所示。這棵樹不平衡。它在節點 25 處為右重。執行 RR 旋轉，得到 AVL 樹，如下圖 (f) 所示。

插入30後，樹如下圖(g)所示。這棵樹不平衡。進行RL旋轉得到AVL樹，如下圖(h)所示。

插入10後，樹如下圖(i)所示。這棵樹不平衡。進行LR旋轉得到AVL樹，如下圖(j)所示。