在2-3棵树中打印最小值到最大值的时间复杂度

Question

我编写了一个伪代码，用于从最小到最大在2-3树中打印叶子。我一直试图理解这段代码中的时间复杂度。任何帮助都会很棒。这是代码：

/* you start algorithm by calling recursivePrint(root) */

void recursivePrint(node){

    if (node is a leaf){

        /* Here print node's value/values */

    } else if (node has 2 children){

        recursivePrint(node.leftChild);
        /* Here print node's value */
        recursivePrint(node.rightChild);

    } else if (node has 3 children)

        recursivePrint(node.leftChild);
        /* Here print node's left value */
        recursivePrint(node.middleChild);
        /* Here print node's right value */
        recursivePrint(node.rightChild)

    }

    /* Shouldn't be other cases in 2-3 trees */
}

Answer 1

由于您的算法必须检查所有节点，因此它的O（n）其中n是树中的节点数。（请注意，树的高度不会影响时间复杂度！）