DFS在C++中的实现

Question

我写了下面的代码。但是我不确定我是否正确地插入了我的树，代码编译成功，但是在输出中没有得到DFS遍历的数组。代码编译成功，但我没有在输出中得到DFS遍历数组。谁能告诉我，我哪里做错了？

输入的树在下面，但请告诉我，我在主函数中的调用是否正确？而正确的输出应该是[a b e f i j c d g k h]。

    A
  / \ \
 B   C D
/ \   / \
E  F  G  H
 / \  \
I  J  K

#include <bits/stdc++.h>
using namespace std;

class Node
{
    public:
      string name;
      vector <Node *> children;

      Node(string name)
      {
          this->name = name;
      }

      //O(v+e) time | O(v) space
      vector <string> depthFirstSearch(vector<string> *array)
      {
          array->push_back(this->name);
          for(size_t i = 0; i < this->children.size(); i++)
               children[i]->depthFirstSearch(array);


          return *array;
      }

      Node *addChild(string name)
      {
          Node *child = new Node(name);
          children.push_back(child);
          return this;
      }
};

int main()
{
    Node n1("a");



    n1.addChild("b");
    n1.addChild("c");
    n1.addChild("d");
    n1.children[0]->addChild("e");
    n1.children[0]->addChild("f");
    n1.children[0]->children[1]->addChild("i");
    n1.children[0]->children[1]->addChild("j");
    n1.children[2]->addChild("g");
    n1.children[2]->addChild("h");
    n1.children[2]->children[0]->addChild("k");
    vector <string> array;
    n1.depthFirstSearch(&array);




    for (size_t i = 0; i< array.size(); i++)
        cout<<array[i]<<' ';



}

注意 - 谢谢你的解释 ，但我做了一些编辑，我在主函数中构建树的方式，并继续使用返回这个语句，它的工作。

Answer 1

这个错误其实很简单，但不是预期中的错误。

该 Node::addChild() 返回 this:

      Node *addChild(string name)
      {
          Node *child = new Node(name);
          children.push_back(child);
          return this; // <-- OUCH!
      }

因此，当用于 main():

    Node n1("a");
    Node *n2 = n1.addChild("b"); // => n2 = &n1;
    n1.addChild("c");
    Node *n4 = n1.addChild("d"); // => n4 = &n1;
    n2->addChild("e");
    Node *n3 = n2->addChild("f"); // => n3 = n2 = &n1;
    n3->addChild("i");
    n3->addChild("j");
    Node *n5 = n4->addChild("g"); // => n5 = n4 = &n1;
    n4->addChild("h");
    n5->addChild("k");

所以，这棵树实际上并没有得到预期的形状，而是像。

   A________________
  / \ \ \ \ \ \ \ \ \
 B   C D E F G H I J K

对于OP的当前输出是完全正确的。

修复的方法很简单。

      Node *addChild(string name)
      {
          Node *child = new Node(name);
          children.push_back(child);
          return child;
      }

输出

a b e f i j c d g k h 

在coliru上进行现场演示

---

上方坚持认为 Node::addChild() 必须 return this; 并要求用另一种方法来规避这个问题。我试图说服OP return child; 总比 return this;.

其实，我直觉地认为 Node::addChild() 会返回创建的子代，这让我花费了一些额外的调试时间来找到真正的错误。 :-)

关于

我在主函数中构建树的方式--是正确的方式还是有更有效的方式？

我个人认为，在 main() 并没有那么糟糕，因为它是。

不过，去罗马的路往往不止一条。

所以，这里只是另一个想法。

用第二个构造函数来显式地构造子节点。

      Node(Node &parent, string name): Node(name)
      {
        parent.children.push_back(this);
      }

可以把树的init. main() 像这样。

    Node nA("a");
    Node nB(nA, "b");
    Node nC(nA, "c");
    Node nD(nA, "d");
    Node nE(nB, "e");
    Node nF(nB, "f");
    Node nI(nF, "i");
    Node nJ(nF, "j");
    Node nG(nD, "g");
    Node nH(nD, "h");
    Node nK(nG, "k");

(Node::addChild() 在这种情况下，甚至不需要使用）。)

输出。

a b e f i j c d g k h 

现场演示在coliru