java - 想要: Recurrence Formula of In-Order binary tree output method

我有点想搜索此java方法的重复公式

void printInorder(Node<T> v) {
    if(v != null) {
        printInorder(v.getLeft());
        System.out.println(v.getData());
        printInorder(v.getRight());
    }
}

一些标准:

是一个完整的二叉树(每个内部结有2个子节点，每片叶子的深度相同)

该树有n个结，复杂度为O(n)

我必须使用depth h找到与树的n knots相关的递归公式，作为额外的好处，我需要从中推断出导致O(n)的显式公式。

现在，这就是我得到的:

d = depth of the tree
c = constant runtime for execution of the method itself
d = 1: T(n) = c
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c

我使用示例d = 3为自己澄清了一些事情，但我很难进一步分解。我的假设是否正确？

编辑:
下次尝试

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number
d = 1: T(d) = 1
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1)))

1: T(h)  = T(i = 0) + T(i = 1) + ... T(i = h-1)
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2)))
3: T(h)  = n + n + ... + n
4: T(h)  = (h-1)n
5: T(h)  = O(n)

因为树的每个深度级别都精确地包含2 ^(h-1)个节点，所以第4行中的h因子可以忽略，因为n与最终结果更相关。

最佳答案

T(n)= T(n/2)+ T(n/2)+1

0级有1个操作。

1级有2个操作。

2级有4个操作。

级别k具有2 ^ k个操作。

树的深度为lgn。

1 + 2 + ... + 2 ^ lgn =
2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ lgn =
(2 ^(lgn + 1)-1)/(2-1)= 2 * 2 ^ lgn =
2n。