我已经实现了如下代码,在这里我做了两个函数来计算二叉树的高度,使用递归和不使用递归。nHeight of tree using non-recursive function: " << heightNonRecursive(root);
} 我已经实现了一个倾斜的二叉树,比如10->20->30->40->50->60->70->75->80,但是在heightNonRecursive()
在每一个recursive call中,有一半的树被“消除”,也就是说,我们减少了需要search for in half的节点数量。虽然我知道这等同于O(log(n)) space,但它不也等同于O(h)树的高度吗?
假设我们在我们的BST中寻找14个,最多的递归调用将等于树的高度,3?这是正确的吗?我想这也延伸到了一