Как найти узел, использующий обход в порядке в двоичном дереве?

Question

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

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

Node Защиту:

struct node { 
    int item; 
    node* l; // Link to left child 
    node* r; // Link to right child 
}; 
typedef node* link; 

Моя попытка:

link find(link x,int n) { 
    if (x == 0) return; // Base condition for recursion 
    find(x->l,n); 
    if (x->item == n) return x; 
    find(x->r,n); 
} 

Как вернуть нулевое значение, если данный узел не существует в дереве?

Answer 1

Вы должны распространять ссылку обратно, если вы нашли одно:

link find(link x,int n) { 
    if (x == 0) return 0; // Base condition for recursion 
    link r = find(x->l,n); 
    if(r != 0) { 
     return r; 
    } 
    if (x->item == n) return x; 
    return find(x->r,n); 
} 

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

Или неоптимизированный вариант:

link find(link x,int n) { 
    if (x == 0) return 0; //we read below a leave, that's not gonna work 
    link r = find(x->l,n); //attempt a search on the left child 
    if(r != 0) { //we found it! 
     return r; //now return what we've found 
    }//apparently it's not in the left child, now continue 
    if (x->item == n) return x; //hmm, maybe we should check or own value, if it is equal, we report ourself 
    //apparently that failed as well, last chance: the right child 
    r = find(x->r,n); //attempt a search on the right child 
    if(r != 0) { //we found it! 
     return r; //now return what we've found 
    }//apparently it's not in the right child either 
    return 0;//we didn't find anything, so let's return 0 
} 

Но последняя if часть может быть оптимизирована, так как шаблон:

if(x != a) { 
    return x; 
} 
return a; 

(с произвольным x и a)

Является ли это шаблон, не имеет большого смысла. В конце концов, если x == a, мы возвращаем a в обоих случаях.