Нужна помощь в написании функции, чтобы проверить, имеют ли два BST одинаковую структуру - PullRequest
Новая
       23

Нужна помощь в написании функции, чтобы проверить, имеют ли два BST одинаковую структуру

0 голосов
/ 08 мая 2020

Я пытаюсь написать функцию, чтобы проверить, имеют ли два дерева одинаковую структуру, независимо от значений, и код, который я написал до сих пор, не работает. Любая помощь или указатели (каламбур) были бы очень признательны. 

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;

Ответы [ 3 ]

0 голосов
/ 08 мая 2020

Вот набросок того, что вы можете попробовать: 

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)
}
0 голосов
/ 08 мая 2020

Ваша функция недействительна, потому что, по крайней мере, в этой части функции 

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;
0 голосов
/ 08 мая 2020

Я должен быть в хорошем настроении.

Простой обход по порядку решит проблему. Просто проверьте на каждом узле, что левое поле равно нулю или не равно нулю в обоих деревьях, тот же тест для правого поля, затем выполните рекурсию.

Эта функция шаблона выполняет свою работу, вам нужно вызвать ее с помощью root указатель узла двух ваших деревьев. 

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);
}

Непроверенный код.

...