二叉搜索树的深度

计算科学 算法 图论
2021-12-05 05:36:00

我写了一个函数来搜索二叉搜索树,但是我有逻辑问题:当我插入一些值时,我有一个 2 级的树,最后一级(在本例中为 2 级)未满(满是它没有所有子节点)它返回 3,而不是 2:

// --- Definition of depth()
template<typename DataType>
int BST<DataType>::depth()
{

  int counter = 0; 

  return Auxdepth(counter, myRoot);

}


// --- Definition of Auxdepth()
template<typename Datatype>
int BST<Datatype>::Auxdepth(int &counter, BinNodePointer subtree)
{
 //BinNodePointer parameter is myRoot, which is the root node
int a;
int b; 

if(empty()) return -1;// garbage value

if(subtree->left == 0 && subtree->right == 0)
    return counter;

else if(subtree->left == 0){
    int x = counter++;
    a= Auxdepth(x,subtree->right);
    return a;
}

else if(subtree->right == 0){
    int x = counter++;
    a = Auxdepth(x,subtree->left);
    return a;
}

if(subtree != 0) { // Recursion
    int x = counter + 1;
    cout << "This is x " << x << endl;
    a = Auxdepth(x, subtree->left);
    b = Auxdepth(x, subtree->right);

            if(a > b) return a;
            else return b;
    }
} 

注意:深度功能只是为了更友好。谁能告诉我我的错误在哪里?

2个回答

这个实现怎么样......(代码是 C,但你可以很容易地转换成你的 C++ 代码)。

int depth(Tree *t)
{
  if(t==NULL)
    return -1;
  else
    return 1 + max( depth(t->subleft), depth(t->subright) );
}

我不知道您的版本是否更有效,但这对我来说很好用。

我不确定这是否是您的问题,但是您通过引用传递计数器,这肯定会导致您当前实现事物的方式出现错误。尝试从按引用调用切换到按值调用并返回 counter 的值以进行复制。