想要:二阶二叉树输出法的递推公式

Question

我在寻找这个java方法的递归公式时遇到了麻烦

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

一些标准：

• 它是一棵完整的二叉树(每个内结有两个孩子，每片叶子都有相同的深度)
• 这棵树有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与最终结果更相关。

Answer 1

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

• 0级有1次操作。
• 一级有两个操作。
• 二级有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.

Answer 2

这里有一种使用平滑规则的替代方法(Levitin，设计和分析算法，第二版，481-82)，它允许这样的递归关系被表示为指数。

​

​

无论是向前替代还是向后替换，都适合于这个问题。在许多情况下，我发现向后替换更容易理解。