1

このアルゴリズムは、一般的な二分木をレベルごとに出力するためのものです。

printSpecificLevel_BT()と の時間計算量と空間計算量はprintBT_LBL()?

printSpecificLevel_BT時間の複雑さはO(lg N)で、空間の複雑さはだと思いますO(lg N)。時間の複雑さはで、空間の複雑さは
だと思います。printBT_LBL()O((lgN)^2)O((lgN)^2)

これは正しいです？

// Print the specific level of a binary tree.
public static void printSpecificLevel_BT (Node root, int level) {
    if (root == null) return;
    if (level == 0) System.out.print(String.format("%-6d", root.data)); // Base case.
    // Do recrusion.
    printSpecificLevel_BT(root.leftCh, level - 1);
    printSpecificLevel_BT(root.rightCh, level - 1);
}

// Get the height of a binary tree.
public static int getHeight_BT (Node root) {
    if (root == null || (root.leftCh == null && root.rightCh == null)) return 0; // Base case.
    return 1 + Math.max (getHeight_BT(root.leftCh), getHeight_BT(root.rightCh));
}

// Print a binary tree level by level.
public static void printBT_LBL (Node root) {
    // Get the height of this binary tree.
    int height = getHeight_BT(root);
    for (int i = 0; i <= height; i ++) {
        printSpecificLevel_BT(root, i);
        System.out.println();
    }
}
4

2 に答える 2

2

printSpecificLevel_BTO(n)ツリー内のすべてのノードを調べるためです。ただし、単純な変更（ の場合に戻るlevel == 0）で、 にすることができますO(min(n, 2^level))。

getHeightO(n)ツリー内のすべてのノードを調べるためです。は何度もprintBT_LBL呼び出すので、その複雑さはです。getHeightprintSpecificLevel_BT heightO(n + n*height) = O(n*height)

それぞれの空間の複雑さはO(height)、ツリーの最下部まで再帰するためです。O(log n)ツリーは必ずしもバランスが取れているとは限らないため (バランスが取れていない限り)、とは言えません。

于 2014-04-06T16:21:34.767 に答える