我正在阅读算法设计手册。提交人说,一棵树的高度是:
h = log n,
where
h is height
n = number of leaf nodes
log is log to base d, where d is the maximum number of children allowed per node.
他接着说,一个完美平衡的二叉树的高度是:
h = log n
我不知道第二条语句中的n是否表示“叶节点的总数”或“节点的总数”。
这就引出了一个更大的问题,节点总数与一个完全平衡的二叉树的高度之间是否存在数学关系?
二叉树与下面的二叉树代码相同或不相同,给出了线性复杂度,即大O (n),其中n是二叉树中节点数最少的节点数。
boolean identical(Node a, Node b)
{
if (a == null && b == null)
return true;
if (a != null && b != null)
return (a.data == b.data
&& identical(a.left, b.left)