рекурсивного дерева, печать предок узлы

Question

это учебный материал, а не домашнее задание:

Я следующее дерево, мне нужно написать алгоритм, который находит заданное число и возвращает целое число, указывающее, сколько узлов он посетил, прежде чем найти Это. Он также должен вывести значения все «предок» узлы по отношению к узлу, в котором было найдено значение (в произвольном порядке, и предполагается, что данное значение всегда присутствует)

  10 
     /\ 
     20 60 
     /\ 
     50 30 
      \ 
      40 

Если данные значение равно 40, оно должно возвращаться 4 и печатать 30, 20, 10 (в любом порядке)

Я написал следующее решение, и я думаю, что это работает, но я обеспокоен печатью.

void foobar (ty_tree *tree, int value, int & count){ 
    if (tree !=null) { 
     if (tree->value != value) { 
      count++; 
      foobar (tree->left, value, count); 
      foobar (tree->right, value, count); 
      cout << tree->value;   
     } 
    } 
} 

Answer 1

Хороший подход! Но для печати предков (ieparent узлов), вы должны знать, в вашей рекурсивной функции, если значение было найдено в одном из ребенка:

bool foobar (ty_tree *tree, int value, int & count) { 
    if (tree !=nullptr) { // oops: NULL or nullptr, the latter is better 
     if (tree->value != value) { 
      count++; 
      if (foobar (tree->left, value, count) || 
        foobar (tree->right, value, count)) // if found below 
      cout << tree->value<<endl; // print the node, because it's on the path   
     } 
     else { 
      cout << "Found: "<<tree->value<<endl; // print the value found 
      return true;  // and inform caller that he can print as well. 
     } 
    } 
    else return false; // reached a leaf without finding   
} 

Как были высказаны сомнения в комментариях, здесь online demo