c++ - 在具有 C++ 子列表的通用树中的两个给定节点之间添加一个节点并查找路径成本

Question

我需要在其子项包含在列表中的通用树中创建一个添加节点函数。有 2 个结构定义了树中的一个节点(有一个标签，它和它的父亲之间的权重，以及一个指向它的 child 列表的指针)和一个 child 列表中的 child (有一个指向子节点和列表中的下一个元素):

struct tree::treeNode {
    Label label;
    Weight weight;
    childrenList children;
}; //(typedef'ed as Tree)

struct tree::childrenListElem {
    treeNode* child;
    childrenListElem* next;
};

我已经生成的代码在树为空(添加根)时有效。当我尝试将节点添加到非空树时遇到运行时错误。

Output tree::addElem(const Label labelOfNodeInTree, const Label labelOfNodeToAdd, const Weight w, Tree& t) {
      if ((labelOfNodeInTree == emptyLabel) && isEmpty(t)) {
        t = createNode(labelOfNodeToAdd, emptyWeight);
        return OK;
      }
    if (((labelOfNodeInTree == emptyLabel) && !isEmpty(t)) ||
       ((labelOfNodeInTree != emptyLabel) && isEmpty(t)))
        return FAILED;
    if (member(labelOfNodeToAdd, t))
        return ALREADY_PRESENT; 
    Tree v = getNode(labelOfNodeInTree, t); //here is where the problems begin to rise
    if (v==emptyTree)
        return FAILED;
    else {
        g = createNode(labelOfNodeToAdd, w);
        v->children->next->child = g;
        g = t;          
        return OK;
    }
}

以下是我实现的 createEmpty、getNode、member 和 isEmpty 函数:

bool tree::isEmpty(const Tree& t)
{
   return (t==emptyTree);
}

Tree getNode(const Label & l, const Tree t)
{
    Tree aux = t;
    while (!isEmpty(aux)) {
        if (aux->label == l)
            return aux;
        aux = aux->children->next->child;
    }
    return emptyTree;
}

Tree createNode(const Label l, Weight w)
{
    Tree t = new treeNode;
    t->label = l;
    t->weight = w;
    t->children = emptyChildrenList;
    return t;
}

编辑:我已经按照函数中的建议修改了成员函数:它只适用于一个单一的节点，即输入给定的节点，而不适用于整个树:只要我必须搜索从输入给出的树的子列表中的给定节点(t 节点)。当我尝试分析其子节点的子节点时(在存在的其他节点上遍历树)，我不起作用。这是目前的成员函数:

bool tree::member(const Label l, const Tree& t) {
    if (isEmpty(t))     return false;
    if (t->label == l)  return true;
    for (childrenList aux = t->children; aux; aux = aux->next) {
        Tree g = aux->child; 
        if (g->label == l)
                        return true;
        g->children = g->children->next;
    }
    return false;   
}

我该怎么做才能使函数在给定节点的子节点列表中搜索给定标签？

我认为问题可能出在 getNode 辅助函数、成员或 addElem 函数的最后一个 else 中，我需要找到一种方法，使 labelOfNodeToAdd 成为 labelOfNodeInTree 的子项之一。我是否将其正确添加到列表中？ getNode 函数是否因为 aux = aux->children->next->child; 行而无法正常工作？我在想象子列表时遇到问题，因此我不确定如何分析每个元素(检查它是否是由 getNode 中的给定标签标识的节点，或者检查它是否存在于成员树中) .

编辑 2:如果可能的话，我想展示最后一个函数(找出 2 个给定节点之间路径的成本(权重总和))——因为它使用了已经在此处实现的函数。

Weight tree::pathCost(const Label from, const Label to, const Tree& t)
{
    int len = 0;
    Tree da = getNode(from, t);
    Tree a = getNode(to, t);
    if (da == emptyTree || a == emptyTree)
    return notExistingPath;
    if (da == a)
        return 0;
    for (childrenList aux = t->children; aux; aux = aux->next) {
        Tree n = aux->child;
        if (aux->child == a) {
            return 0;
        }
        len += n->weight;
    }
    return len;
}

每次我尝试计算路径时，它都会给我带来问题 - 总和有问题吗？或者它没有正确横向？

Answer 1

member 的正确实现可能如下所示:

bool tree::member(const Label l, const Tree& t) {
    if (isEmpty(t))     return false;
    if (t->label == l)  return true;
    for (childrenList aux = t->children; aux; aux = aux->next) {
        if (member(l, aux->child))
            return true;
    }
    return false;   
}

for 循环遍历节点的子节点(例如一层深)，递归 member 调用负责向下一层。

getNode 遵循相同的模式，但返回一个 Tree:

Tree getNode(const Label & l, const Tree t)
{
    if (isEmpty(t))     return emptyTree;
    if (t->label == l)  return const_cast<Tree>(t);
    for (childrenList aux = t->children; aux; aux = aux->next) {
        Tree candidate = getNode(l, aux->child);
        if (!isEmpty(candidate))
            return candidate;
    }
    return emptyTree;
}

那时你不妨将 member 重新实现为:

bool tree::member(const Label l, const Tree& t) {
  return !isEmpty(getNode(l, t));
}

编辑:addElem 的最后一个分支也是错误的:

Output tree::addElem(const Label labelOfNodeInTree, const Label labelOfNodeToAdd, const Weight w, Tree& t) {
      if ((labelOfNodeInTree == emptyLabel) && isEmpty(t)) {
        t = createNode(labelOfNodeToAdd, emptyWeight);
        return OK;
      }
    if (((labelOfNodeInTree == emptyLabel) && !isEmpty(t)) ||
       ((labelOfNodeInTree != emptyLabel) && isEmpty(t)))
        return FAILED;
    if (member(labelOfNodeToAdd, t))
        return ALREADY_PRESENT; 
    Tree v = getNode(labelOfNodeInTree, t);
    if (v==emptyTree)
        return FAILED;
    else {
        // Get a reference to the first null pointer in the linked list
        childrenListElem*& aux = v->children;
        while (aux) {
            aux = aux->next;
        }

        // Append a new element by overwriting the pointer
        aux = new childrenListElem;
        aux->child = createNode(labelOfNodeToAdd, w);
        aux->next = nullptr;
        return OK;
    }
}