Учитывая ввод строки, как мы можем пересечь бинарное дерево рекурсивно ⇐ C++

[Anonymous]

Допустим, наше двоичное дерево (BT) выглядит следующим образом:

Код: Выделить всё

Node* root = new Node();
root->left = new Node("B");
root->right = new Node();
root->right->right = new Node("A");
root->right->left = new Node();
root->right->left->right = new Node("D");
root->right->left->left = new Node("C");
< /code>
И нам дают строку «01111».
Эта строка должна декодировать на «baa». < /p>
Я не могу обернуть голову вокруг «условной» рекурсии. Я особенно застрял на том, чтобы функция продолжала обрабатывать строку после первого "1". Все мои предыдущие попытки сделают программу закончить и только напечатать «b a».void Decode(const string& unambiguous_message, const Node* root, const Node* current, size_t index = 0) {
// Base case: if index reaches the end of the string, stop
if (index >= unambiguous_message.length()) {
return;
}

if (current->left == nullptr && current->right == nullptr) {
cout data left != nullptr) {
Decode(unambiguous_message, root, current->left, index + 1);
} else if (unambiguous_message[index] == '1' && current->right != nullptr) {
Decode(unambiguous_message, root, current->right, index + 1);
} else {
// Invalid path: restart from root at next index to try next prefix
Decode(unambiguous_message, root, root, index + 1);
}
}

Кроме того, если есть лучший способ перевести BT с изображения на код.
Я ожидаю, что строка будет полностью обработана.>

Подробнее здесь: https://stackoverflow.com/questions/797 ... ecursively