递归树，印刷祖先节点

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