0

给定一个非常大的二叉树（即具有数百万个节点），如何确定树中的节点数？换句话说，给定这棵树的根节点给一个函数，该函数应该返回树中的节点数。

或者让我们说如果二叉树有非常多的节点，你如何检查二叉树是否是 BST？

4

2 回答 2

1

遍历所有节点并检查您需要的任何条件/指标。如果没有关于树的额外知识，您将无能为力。

您可以在创建树时强制执行特定条件（即必须平衡/排序/无论如何）或在创建时收集有关树的信息（即存储并不断更新子节点的数量）。

于 2012-11-21T16:47:34.970 回答
0

要检查它是否是有效的 bst，您必须首先访问每个节点深度并确保每个节点都小于前一个节点。

如果您想评估平衡 BST 需要多长时间，您可以通过计算一条腿的长度来快速估算尺寸，我相信总尺寸将在 2^(n-1) 和 2^n 之间-1 包括在内

于 2018-04-18T18:48:12.777 回答