二叉查找树的查寻——迭代程序对栈的需求是多少

二叉查找树的查找——迭代程序对栈的需求是多少？

tree_pointer search2(tree_pointer tree,int key)
{
   while(tree)
   {
      if(key==tree->data)
         return tree;
      if(key<tree->data)
         tree=tree->left_child;
      else
         tree=tree->right_child;
   }
   return NULL;
}

以上是二叉查找树的迭代查找函数
tree_pointer的定义如下
typedef struct node *tree_pointer;
typedef struct node
{
   tree-pointer left_child;
   tree-pointer right_child;
   int data;  //关键字值
}；
问题就是：二叉查找树的迭代查找函数对栈的需求是O(h)吗？为什么？请给出详细解释（h是二叉查找树的深度） tree c search
[解决办法]
好像时间复杂度是O(h)。对栈的要求是O(1)吧。
不是递归，也不是栈模拟递归。
[解决办法]
这个很显然是O(1)的！函数体是循环，不是递归。如果是递归遍历树，那就是O(h)了
[解决办法]
search2里面没有其他调用 所以空间复杂度O(1) 时间复杂度O(h)

查看更多 下一篇