0

我正在尝试用孩子的向量创建一个 n-ary 树。

这是我到目前为止所得到的。

在 node.h 文件中，我有这个：

  #include <vector>
  #include <string>

  using namespace std;

  class Node{

  private:
      Node *parent; 
      vector <Node*> children; 

      int data; 

  public: 
      Node();
      Node(Node parent, vector<Node> children);
      Node(Node parent, vector<Node> children, int data);

      Node * GetParent(); 

      void SetChildren(vector<Node> children);
      vector<Node>* GetChildren();
      void AddChildren(Node children);

      void SetData(int data);
      int GetData();

      bool IsLeaf();
      bool IsInternalNode();
      bool IsRoot();

  };

这是我的 node.cpp 文件。

   #include "node.h"

   Node::Node(){
       this->parent = NULL; 
       this->children = NULL; 
       this->data = 0;
   }

   Node::Node(Node parent, vector<Node> children){
       this->parent = &parent; 
       this->children = &children; 
   }

   Node::Node(Node parent, vector<Node> children, int data){
       this->parent = &parent; 
       this->children = &children; 
       this->data = data; 
   }

   Node* Node:: GetParent(){
       return this->parent;
   }

   void Node::SetChildren(vector<Node> children){
       this->children = &children; 
   }

   vector<Node> * Node::GetChildren(){
       return this->children;
   }

   void Node::AddChildren(Node children){
       this->children.push_back(children);
   }

   void Node::SetData(int data){
       this->data = data;
   }

这显然是行不通的。我的主要问题是我不太确定如何为孩子们处理向量。我在网上的一些教程之后写了这个，但正如你所看到的，我非常困惑。

4

3 回答 3

5

您的代码中的主要（也可能是唯一的）问题是您定义了您的Node类以通过指针 ( Node*) 操作节点：

class Node{
  private: 
    Node *parent; 
    vector <Node*> children;

但是您的方法是按值（Node）操作节点。

例如，在构造函数中：

Node::Node(Node parent, vector<Node> children){
    this->parent = &parent;

存储父参数的地址不起作用，它是一个临时对象，您需要将 a 传递Node* parent给您的构造函数或创建一个新的Node对象。

    this->children = &children;

这没有任何意义，因为this->children是 的向量，Node*而children参数是 的向量Node。同样，您需要将向量传递Node*给构造函数或创建新的节点对象。

SetChildren您在和中也有同样的问题AddChildren。

此外，由于您将节点作为指针进行操作，因此要非常小心内存管理。C++ 中没有垃圾收集器，您必须在适当的时间处理delete所有事情。new

于 2013-10-11T14:21:52.213 回答
2

检查以下代码是否可以帮助您创建 n 数组树创建。

struct TreeNode
{
    vector<TreeNode*> children;
    char value;
};

class TreeDictionary
{
    TreeNode *root;
public:
    TreeDictionary()
    {
        root = new TreeNode();
        root->value = 0;
    }

    TreeNode *CreateNode(char data)
    {
        TreeNode *parent_node = new TreeNode;
        if (parent_node)
            parent_node->value = data;
        return parent_node;
    }
    TreeNode* SearchElement(TreeNode *NextNode, char *data, int& val)
    {
        bool bVal = false;
        for (vector<TreeNode*>::iterator it = NextNode->children.begin(); it != NextNode->children.end(); it++)
        {
            if ((*it)->value == *(data))
                return SearchElement((*it), ++data, ++val);
        }
        return NextNode;

    }
    TreeNode *InsertNode(TreeNode *parent, TreeNode *ChildNode, char data)
    {
        if (parent == NULL)
            ChildNode = CreateNode(data);
        else
        {
            TreeNode *childNode = CreateNode(data);
            parent->children.push_back(childNode);
            return childNode;
        }
        return ChildNode;
    }

    void InsertMyString(string str)
    {
        TreeNode *NextNode = root;
        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == '\0')
                return;
            cout << str[i] << endl;
            if (NextNode->value == 0)
            {
                NextNode->value = str[i];
                continue;
            }
            else if (NextNode->value != str[i])
            {
                NextNode = InsertNode(NextNode, NULL, str[i]);
            }
            else
            {
                TreeNode *node;
                node = SearchElement(NextNode, &str[++i], i);
                NextNode = InsertNode(node, NULL, str[i]);
            }
        }
    }
};

int main()
{
    TreeDictionary td;
    td.InsertMyString("Monster");
    td.InsertMyString("Maid");
    td.InsertMyString("Monday");
    td.InsertMyString("Malli");
    td.InsertMyString("Moid");
    return 0;
}
于 2017-09-07T13:13:18.917 回答
0

这种SearchElement（没有递归）的实现也有效：

TreeNode* SearchElement(TreeNode *NextNode, char *data, int& val)
{
    bool bVal = false;
    for (vector<TreeNode*>::iterator it = NextNode->children.begin(); it != NextNode->children.end(); it++)
    {
        if ((*it)->value == *(data))
            return (*it);
    }
    return NextNode;
}

TreeNode* res = SearchElement(root, data, value);

我检查了这一点，无法理解，为什么 - 它适用于您想要在树中找到的任何节点，无论树中节点的深度和级别如何，这还不清楚为什么，因为循环只在子节点上迭代在树的第二层（根节点的子节点），尽管如此 - 它甚至会在树中找到深度为 10 层的节点。

于 2018-11-14T08:28:44.977 回答