Два решения:
1. Массив / Вектор (или карта)
Каждый узел имеет до двух дочерних элементов. Их запись позволяет спускаться по дереву.
Но - у каждого узла есть только один родительский элемент . Запись этой информации облегчает восхождение дерева - что отлично подходит для поиска root дерева или LCA для узлов. После анализа вашего ввода ваш массив выглядит следующим образом:
┌─┐
0 │0│
1 │0│
2 │1│
3 │1│
4 │2│
5 │2│
6 │3│
7 │3│
└─┘
Теперь, начиная с любого узла - скажем, 6 - мы видим из массива, что родительский элемент 6 равен 3, а родительский 3 равен 1, а 1 имеет нет родителей. Если ваши ключи узла не являются списком маленьких целочисленных значений, как в вашем примере, вы должны использовать карту вместо этого.
2. Создайте двоичное дерево!
Проблема, с которой вы, вероятно, сталкиваетесь, заключается в том, что мы традиционно работаем с деревом, удерживая ссылку на root и получая доступ ко всем остальным узлам из root - но пока вы строите дерево из примера ввода, вы не только не знаете root, вы также имеете фрагменты дерева, которые объединяются в одно дерево только тогда, когда у вас есть достаточно информации.
Все, что вам нужно, это временная структура для хранения узлов (и тем самым фрагментов), пока дерево не будет завершено и не будет идентифицировано root. Затем вы можете выбросить эту структуру.
Вот некоторый непроверенный код, чтобы показать, что я имею в виду. Осторожно - он использует необработанные указатели, он использует new, у него нет deletes, древовидная структура должна быть классом, et c et c. Это просто для иллюстрации алгоритма и не рекомендуется практика кодирования.
#include <map>
#include <utility>
#include <vector>
struct node {
node *parent, *left, *right;
int value;
};
struct tree {
node *root;
};
tree BuildTree(const std::vector<std::pair<int, int>>& edges) {
std::map<int, node*> nodes;
auto FindOrAddNode = [&nodes](int key) -> node* {
auto node_iter = nodes.find(key);
if (node_iter != nodes.end())
return node_iter->second;
else {
auto new_node = new node;
new_node->value = key;
nodes[key] = new_node;
return new_node;
}
};
for (auto edge : edges) {
auto parent = FindOrAddNode(edge.first);
auto child = FindOrAddNode(edge.second);
child->parent = parent;
if (parent->left == nullptr)
parent->left = child;
else if (child->value >= parent->left->value)
parent->right = child;
else {
parent->right = parent->left;
parent->left = child;
}
}
// now pick any node, and walk up to find the root
// then construct and return a tree object using the root
// when we exit this function, the local `nodes` variable is discarded
// we don't need it any more.
}
int main(int argc, char** argv) {
auto the_tree = BuildTree({{2, 4}, {2, 5}, {3, 7}, {3, 6}, {1, 2}, {1, 3}});
return 0;
}