Есть ли способ проверить, равны ли два дерева правого брата слева ребенка? - PullRequest
Новая
       12

Есть ли способ проверить, равны ли два дерева правого брата слева ребенка?

0 голосов
/ 22 апреля 2020

В настоящее время я работаю над перегрузкой оператора равенства для левого дочернего правого класса-брата, и эта функция должна проверять, имеют ли два дерева одинаковые root, одинаковые дети и одинаковые сибсы (или в целом, если два дерева точно так же) 

bool CTree::operator==(const CTree &root){
if(this->kids!=nullptr){
return ((kids)==(root.kids));
}
else{
if(this->sibs!=nullptr){
return ((sibs)==(root.sibs));
}
else{
return (data==root.data);
}
}
}

Это моя текущая функция, чтобы проверить, равны ли два дерева левого и правого братьев и сестер; Я думаю, что это имеет две проблемы, которые я не могу найти способ обойти это; во-первых, он возвращает kids == root .kids без проверки sibs, а во-вторых, эта функция перестает проверять равенство двух деревьев, когда kids и sibs указывают на null. Я попытался написать вторую функцию 

bool CTree::operator==(const CTree &root){
  if(this->kids!=nullptr){
    if (!(kids==root.kids)){
        return false;
      }
  }
  else{
    if(this->sibs!=nullptr){
      if (!(kids==root.sibs)){
          return false;
        }
    }
    else{
      if (!(data==root.data)){
          return false;
        }
    }
  }
  return true;
}

Но это также не проверяет правильность равенства двух деревьев. Может кто-нибудь дать мне подсказку, как поступить? Я включил часть моего заголовочного файла для справки 

class CTree {
  friend class CTreeTest;

  char data;     // the value stored in the tree node

  CTree * kids;  // children - pointer to first child of list, maintain order & uniqueness

  CTree * sibs;  // siblings - pointer to rest of children list, maintain order & uniqueness
                 // this should always be null if the object is the root of a tree

  CTree * prev;  // pointer to parent if this is a first child, or left sibling otherwise
                 // this should always be null if the object is the root of a tree}

1 Ответ

0 голосов
/ 22 апреля 2020

Я должен признать, что я еще никогда не слышал о (термин) левые дети-правые родные деревья (или я уже забыл об этом). Однако я уже видел нечто подобное в действии, когда использовал libXml2 . (Взгляните на struct _xmlNode, чтобы понять, что я имею в виду.)

Итак, я объясняю, как бы я сделал сравнение CTree::operator==(): 

    bool operator==(const CTree &cTree) const
    {
  1. Я бы сначала сравнил data. Нет необходимости проходить через любого потомка или брата, если узлы root имеют разные данные. 
      if (data != cTree.data) return false; // unequal data -> equality failed
Следующим шагом будет сравнение парных указателей kids. Если у одного из узлов есть дочерние элементы, а у другого нет, сравнение на равенство может выручить. Для этого я просто конвертирую указатели в bool с. 
      if (!kids != !cTree.kids) return false; // only one has kids -> equality failed
То же самое сделано для указателей родного брата. 
      if (!sibs != !cTree.sibs) return false; // only one has sibs -> equality failed
Теперь оба или ни один из узлов не имеют дочерних элементов. Итак, для первого случая первая рекурсия в детей сделана. (В последнем случае этот шаг можно пропустить.) 
      // recursion into kids (if there are kids)
      if (kids && *kids != *cTree.kids) return false; // kids exist but are unequal
На последнем этапе рекурсия должна выполняться для братьев и сестер, если есть братья и сестры. В противном случае узлы (поддеревья) в этой точке уже считаются равными. Я использую логическое или короткое замыкание. Следовательно, если sibs имеет nullptr, правая часть пропускается и возвращается !nullptr (== true). В противном случае возвращаемое значение приводит к сравнению братьев и сестер. 
      // recursion into sibs (if there are sibs)
      return !sibs || *sibs == *cTree.sibs; // no sibs or result of sibs equality check
Вот и все. 
    }
Для симметрии (а также потому, что она уже использовалась) должна быть определена и противоположная часть operator!=(). Он просто основан на operator==() и AFAIK, это очень обычно. 
    bool operator!=(const CTree &cTree) const { return !(*this == cTree); }

Я сделал MCVE, чтобы проверить и продемонстрировать это. Таким образом, я изменил тип data с char на std::string, чтобы сделать его более наглядным: 

#include <iostream>
#include <string>

class CTree {
  private:
    std::string data;
    CTree *kids;
    CTree *sibs;
    CTree *prev;
  public:
    CTree(const std::string data = ""):
      data(data), kids(nullptr), sibs(nullptr), prev(nullptr)
    { }

    // adds a child.
    void add(CTree *kid)
    {
      if (kids) {
        kids->prev = kid; kid->sibs = kids; 
      }
      kids = kid; kid->prev = this;
    }

    bool operator==(const CTree &cTree) const
    {
      if (data != cTree.data) return false; // unequal data -> equality failed
      if (!kids != !cTree.kids) return false; // only one has kids -> equality failed
      // recursion into kids (if there are kids)
      if (kids && *kids != *cTree.kids) return false; // kids exist but are unequal
      if (!sibs != !cTree.sibs) return false; // only one has sibs -> equality failed 
      // recursion into sibs (if there are sibs)
      return !sibs || *sibs == *cTree.sibs; // no sibs or result of sibs equality check
    }

    bool operator!=(const CTree &cTree) const { return !(*this == cTree); }
};

CTree* install(bool complete)
{
  CTree *pRoot = new CTree("/");
  CTree *pBin = new CTree("bin/"); pRoot->add(pBin);
  CTree *pUsr = new CTree("usr/"); pRoot->add(pUsr);
  CTree *pBash = new CTree("bash"); pBin->add(pBash);
  CTree *pCsh = new CTree("csh"); pBin->add(pCsh);
  if (complete) {
    CTree *pEtc = new CTree("etc/"); pRoot->add(pEtc);
    CTree *pInitD = new CTree("init.d"); pEtc->add(pInitD);
  }
  return pRoot;
}

int main()
{
  CTree *drv1 = install(false);
  CTree *drv2 = install(false);
  CTree *drv3 = install(true);
  std::cout << "drv1 == drv2? " << (*drv1 == *drv2 ? "yes" : "no") << '\n';
  std::cout << "drv1 == drv3? " << (*drv1 == *drv3 ? "yes" : "no") << '\n';
  std::cout << "drv2 == drv3? " << (*drv2 == *drv3 ? "yes" : "no") << '\n';
}

Вывод: 

drv1 == drv2? yes
drv1 == drv3? no
drv2 == drv3? no

Live Demo on coliru

Подумав дважды, я понял, что равенство operator==() можно записать еще более компактно, хотя я не думаю, что оно улучшает читабельность, и я не ожидаю какой-либо производительности победа: 

    bool operator==(const CTree &cTree) const
    {
      return data == cTree.data // unequal data -> equality failed
        && !kids == !cTree.kids // only one has kids -> equality failed
        && !sibs == !cTree.sibs // only one has sibs -> equality failed
        && (!kids || *kids == *cTree.kids) // no kids or result of kids equality check
        && (!sibs || *sibs == *cTree.sibs); // no sibs or result of sibs equality check
    }

Демонстрация в реальном времени на coliru

...