需要帮助编写函数来检查两个BST是否具有相同的结构

Question

我正在尝试编写一个函数来检查两棵树是否具有相同的结构，而不管其值如何，到目前为止，我编写的代码不起作用。任何帮助或指针（双关语旨在）将不胜感激。

template <class T>
bool BST<T>::similarStructure(BST Tree2) {
    if (isEmpty()) {
        cout << "tree is empty\n";
        return;
    }

    StackArray<node<T>> s1, s2; // s1 for traversal,, s2 for printing

    s1.Push(root);
    s2.Push(tree2.root);
    while (!s1.IsEmpty() &&!s2.isempty()) {
        node<T> n = s1.Pop();
        node<T> n1=s2.Pop();
        if (n->right != NULL && n1->right!=NULL){
            s1.Push(n->right);
            s2.Push(n1->right); }
         else{
           return false;}

        if (n->left != NULL && n->left!=NULL){
            s1.Push(n->left); 
            s2.Push(n1->left);}
        else{
            return false;}

    }
    return true;

Answer 1

我必须心情愉快。

简单的顺序遍历将解决此问题。只需检查两个树中每个节点的左字段是否为空或不为空，对右字段进行相同的测试，然后递归。

此模板功能可以完成工作，您需要使用两棵树的根节点指针来调用它。

template <class T>
bool similarStructure(node<T>* x, node<T>* y) const
{
    if (x == y)
        return true;
    if (x == nullptr || y == nullptr)
        return false;
    return similarStructure(x->left, y->left) && similarStructure(x->right, y->right);
}

未经测试的代码。

Answer 2

这里是您可以尝试的草图：

bool similarStructure(BST t1, BST t2)
{
  return !(t1.root ^ t2.root) 
         && t1.root 
         && similarStructure(t1.root->left, t2.root->left)
         && similarStructure(t1.root->right, t2.root->right)
}

Answer 3

您的功能无效，因为至少在该功能的此部分中

template <class T>
bool BST<T>::similarStructure( BST Tree2 ) 
{
    if (isEmpty()) {
        cout << "tree is empty\n";
        return;
    }
    //...

尽管该函数具有返回类型bool，但是它什么也不返回。

使用您的方法，该函数可以按以下方式查看

template <class T>
bool BST<T>::similarStructure( const BST &Tree2 ) const 
{
    if ( isEmpty() && Tree2.isEmpty() ) return true;

    StackArray<node<T>> s1, s2;

    s1.Push( root );
    s2.Push( tree2.root );

    bool theSame = true;

    while ( theSame && !s1.isEmpty() ) 
    {
        node<T> n  = s1.Pop();
        node<T> n1 = s2.Pop();

        theSame = ( n->right != NULL ) == ( n1->right != NULL );

        if ( theSame && n->right != NULL )
        { 
            s1.Push( n->right );
            s2.Push( n1->right );
        }

        if ( theSame )
        {
            theSame == ( n->left != NULL ) == ( n->left != NULL );
            if ( theSame && n->left != NULL )
            {
                s1.Push( n->left ); 
                s2.Push( n1->left );
            }
        }
    }

    return theSame;
}

请注意，该函数是用限定符const声明的。这意味着类isEmoty的成员函数BST<T>也应使用限定符const声明。

bool isEmpty() const;