c - 定制树的复杂度顺序

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 7 年前。

Improve this question

请告诉我下面树的复杂性。请解释一下计算过程。

树结构:

root->left->right 和 root->right->left 指向同一个节点。

算法:如果我们用正常的中序遍历来遍历这棵树，那么我们会访问某些节点超过1次。

喜欢

节点4(2次)0->1->4和0->2->4

节点7(3次) 0->1->3->7, 0->1->4->7, 0->2->4->7

上述算法的复杂度是多少？

Answer 1

在您的图解结构(这是一个有向无环图或“DAG”，而不是树)中，遍历将访问除叶节点之外的每个节点的两个子节点。因此，它将总共访问 2^h-1 个节点(计算重复项)，其中 h 是 DAG 的高度。 (图中的高度为 5。)

假设 DAG 已完全填充，则 n(DAG 中的节点数)必须为 h(h+1)/2。 (这是高斯求和从 1 到 h 的整数的公式。)

Solving n = h(h+1)/2 for h gives us h = (sqrt(8n + 1) - 1)/2 ，因此访问的节点总数(以 n 为单位)为 2^{(sqrt(8n + 1) - 1)/2} - 1。

更新

遍历函数如下所示:

def traverse(node):
    if node.left is not None:
        traverse(node.left)
    print(node.data)
    if node.right is not None:
        traverse(node.right)

请注意，traverse 不会查看节点的父节点，只会查看其子节点。从traverse的角度来看，某些节点是共享的(因此有两个父节点)是无关紧要的。它无法区分 DAG 和普通二叉树之间的区别。

每个 DAG 内部节点都有两个子节点。因此，从traverse的角度来看，您的 DAG 与高度为 h 的完全填充的二叉树相同。高度为 h 的完全填充二叉树有 2^h-1 个节点。