Какова логика обхода каждого пути в двоичном дереве в C ++?
Это мой первый раз, когда я изучаю бинарные деревья, и я вижу много вопросов, касающихся обхода пути, одним из таких вопросов было найти путь к конкретному узлу. Это очень просто в бинарном дереве поиска, но очень сложно в обычном бинарном дереве, так как элементы в узлах не имеют отношения между ними. Я придумал много логики, но ни один из них не работает для всех узлов дерева.
И я также хотел бы знать, какова логика для прохождения каждого пути от корня до конечного узла.
Благодарю вас.
Решение
Используйте рекурсию. Детали варьируются в зависимости от того, как именно вы определили свое дерево, но оно может выглядеть примерно так
void visit(TreeNode* node, vector<Node*>& path)
{
// check for NULL
if (node == NULL)
return;
// add node to path
path.push_back(node);
// print the node path
...
// visit left child
visit(node->left, path);
// visit right child
visit(node->right, path);
// remove node from path
path.pop_back();
}
// start at the root
vector<Node*> path;
visit(root, path);
Другие решения
Других решений пока нет …