首頁 >Java >java教程 >測試 AVLTree 類

測試 AVLTree 類

王林
王林原創
2024-07-25 09:09:31766瀏覽

本節給出了使用 AVLTree 類別的範例。下面的程式碼給了一個測試程式。程式建立一個以整數陣列25205 初始化的AVLTree(第7 行),將元素插入第111 -20 行,並刪除第24-30 行中的元素。由於AVLTreeBST 的子類,並且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)所示。

Image description

下圖顯示了樹如何隨著元素被刪除而演變。刪除34、30、50後,樹如下圖(b)所示。這棵樹不平衡。進行LL旋轉得到AVL樹,如下圖(c)所示。

刪除5後,樹如下圖(d)所示。這棵樹不平衡。進行RL旋轉得到AVL樹,如下圖(e)

Testing the AVLTree Class

以上是測試 AVLTree 類的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn