Какова логика прохождения каждого пути в двоичном дереве на C++?

Question

Это мой первый раз, когда я изучаю бинарные деревья, и я вижу много вопросов относительно обхода пути, одним из таких вопросов был поиск пути к определенному узлу. Это очень просто в двоичном дереве поиска, но это очень сложно в обычном двоичном дереве, поскольку элементы в узлах не имеют никакой связи между ними. Я придумал много логики, но ни один из них не работает для всех узлов в дереве. И я также хотел бы знать, что такое логика для прохождения каждого пути от корня до листового узла.

Thank you.

Answer 1

Использование рекурсии. Детали варьируются в зависимости от того, как именно вы определили свое дерево, но это может выглядеть примерно так

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);