[c ++ / указатели]:имея объекты A и B (B имеет векторный элемент, в котором хранится указатель на A), зная A, возможно ли получить указатель на B?

Question

Пытаясь выучить c ++, я попытался реализовать класс, представляющий очень простой trie.Я пришел к следующему:

class Trie {
public:
    char data;
    vector<Trie* > children;

    Trie(char data);
    Trie* addChild(Trie* ch);    // adds child node

    (skipped others members/methods)

};

Способ Добавить дочерний элемент проверяет, является ли дочерний сн с тем же данные присутствует в векторе дети, если нет, то он вставляет его туда, если да - возвращает указатель на уже существующий дочерний элемент.

Теперь, рассматривая этот фрагмент кода:

Trie t('c');
Trie* firstchild = new Trie('b');
Trie* secondchild = new Trie('a');


firstchild->addChild(secondchild);
t.addChild(firstchild);

если у меня есть только указатель на второй ребенок, возможно ли каким - то образом вернуть указатели на первенец или, может быть, даже t?

Я хотел бы знать, возможно ли это сделать, потому что логика моего рабочего кода должна проходить по дереву "вверх" (от нижних узлов к верхним), к родительскому элементу текущего объекта.В настоящее время я просто использую рекурсивную функцию для перемещения вниз - но мне интересно, существует ли какой-либо другой способ?

Прошу прощения, если вышесказанное неясно или я где-то напутал, я довольно неопытен и пишу по памяти, без рабочего кода.

Answer 1

Вам нужно добавить что-то вроде

Trie* parent;

или

Trie* previoussibling;
Trie* nextsibling;

в класс, чтобы попасть непосредственно из firstchild Для secondchild или наоборот, или подняться от одного из детей к t.

Обратите внимание, что если вам нужна такая взаимосвязь, то вам потребуется дополнительное обслуживание при добавлении и удалении узлов, чтобы все ссылки были правильными.

Answer 2

Объект Trie не отслеживает родительский объект.Это в основном похоже на односвязный список, и вы не можете вернуться назад, если вы не "знаете" родительский элемент.

class Trie {
public:
    char data;
    vector<Trie* > children;
    Trie* parent;

    Trie(char data):parent(NULL){}
    Trie* addChild(Trie* ch)
    { //set the parent
     ch->parent = this;
    }

    (skipped others members/methods)

};

Тогда траверс выглядел бы примерно так:

traverse(Trie* pPtr)
{
Trie* currentPtr = pPtr;
 while(currentPtr)
 {
  currentPtr = currentPtr->parent;
 }

}

Answer 3

У меня есть только указатель на secondchild, возможно ли как-то вернуть указатели на firstchild или, может быть, даже t?

Нет.Вы должны установить эти отношения самостоятельно, передав firstChild в качестве родителя второго ребенка.