时间戳

首页 > 解决方案 > 有没有办法检查两个左孩子右兄弟树是否相等？

c++ - 有没有办法检查两个左孩子右兄弟树是否相等？

问题描述

我目前正在为左子右兄弟类重载相等运算符，这个函数应该检查两棵树是否具有相同的根、相同的孩子和相同的同胞（或者总体上是否两棵树完全相同）

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}

标签： c++classrecursiontreeoperator-overloading

解决方案

我必须承认我从未听说过（术语）left-child-right-sibling-trees（或者我已经忘记了）。但是，当我使用libXml2时，我已经看到了类似的操作。
（看看struct _xmlNode我的意思。）

所以，我解释一下我将如何进行比较CTree::operator==()：

    bool operator==(const CTree &cTree) const
    {
  1. 我会比较第data一个。如果根节点有不同的数据，则无需遍历任何子节点或兄弟节点。
      if (data != cTree.data) return false; // unequal data -> equality failed
  1. 下一步是kids成对比较指针。如果其中一个节点有子节点，而另一个节点没有，则相等比较可以退出。为此，我只是将指针转换为bools。
      if (!kids != !cTree.kids) return false; // only one has kids -> equality failed
  1. 同级指针也是如此。
      if (!sibs != !cTree.sibs) return false; // only one has sibs -> equality failed
  1. 现在，两个或没有一个节点有孩子。因此，对于前一种情况，第一次递归到孩子中已经完成。（在后一种情况下，可以跳过此步骤。）
      // recursion into kids (if there are kids)
      if (kids && *kids != *cTree.kids) return false; // kids exist but are unequal
  1. 最后一步，如果有兄弟姐妹，则必须对兄弟姐妹进行递归。否则，此时节点（子树）已被视为相等。
    我使用逻辑或短路。因此，如果sibs有 anullptr则跳过右侧并返回!nullptr( == true)。否则，返回值会导致兄弟姐妹的比较。
      // recursion into sibs (if there are sibs)
      return !sibs || *sibs == *cTree.sibs; // no sibs or result of sibs equality check
  1. 而已。
    }
  1. 为了对称（并且因为它已经被使用过），operator!=()还必须定义对应部分。它只是建立在operator==()AFAIK 之上，这很常见。
    bool operator!=(const CTree &cTree) const { return !(*this == cTree); }

我制作了一个 MCVE 来检查和演示这一点。因此，我更改了datafrom的类型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

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 现场演示

推荐阅读