Добавить узел и Найти стоимость пути между двумя заданными узлами в общем дереве со списком детей в C ++

Question

Мне нужно сделать функцию добавления узла в общем дереве, чьи дочерние элементы содержатся в списке. Существует 2 структуры, которые определяют узел в дереве (который имеет метку, вес между ним и его отцом и указатель на список его дочерних элементов) и дочерний элемент в списке дочерних элементов (который имеет указатель на дочерний узел и один следующий элемент в списке):

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, где мне нужно найти способ, чтобы labelOfNodeToAdd стал одним из дочерних элементов labelOfNodeInTree. Правильно ли я добавил его в список? Функция getNode работает плохо из-за строки aux = aux->children->next->child;? У меня проблема с представлением списка дочерних элементов, и поэтому я не уверен, как анализировать каждый элемент (чтобы проверить, является ли он узлом, идентифицированным данной меткой в ​​getNode, или проверить, существует ли он в дереве с элементом) .

РЕДАКТИРОВАТЬ 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;
    }
}