поиск определенного конечного узла в двоичном дереве, запись маршрута - PullRequest
Новая
       28

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

0 голосов
/ 13 июня 2019

У меня есть двоичное дерево, в котором у конечных узлов есть символ («a», «r» и т. Д.).Я хочу найти определенный узел в этом дереве и записать маршрут, когда я его нашел.(Это алгоритм Хаффмана). Проблема в том, что мой код просто печатает только последние 2 подчиненных маршрута (В случае с символом "p" мой код просто указывает "10", и он должен вывести "110". Слово: paddle . Маршрут начинается с корня. enter image description here

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

struct nodo{
    int frecuencia;
    nodo *izq, *der, *next;
    char letra;
    int binario; // binario it is "0" or "1" 
    int usado;

}; 

bool recorrerarbol(nodo *n, char letradada, string &cadena){
    if(n!=NULL){
            if(n->letra==letradada){
                    cadena=to_string(n->binario)+cadena; //n->binario it is 0 or 1
                    return true;
            }
            else{
                    if(recorrerarbol(n->izq,letradada,cadena)){
                            cadena=to_string(n->binario)+cadena;
                    }
                    else{
                            if(recorrerarbol(n->der,letradada,cadena)){
                                   cadena=to_string(n->binario)+cadena;
                    }}
            }

    }

    return false;
    }

Ожидаемый результат: для "a": 111 для "p": 110 для"d": 0 Что я получаю: "d": 00"p": 10 "a": 11 Как видите, проблема в том, что учитываются только последние 2 уровня роста. Спасибо

1 Ответ

0 голосов
/ 13 июня 2019

Я отвечаю самому себе.Проблема была в каждом, если / else не возвращает True.поэтому в некоторых случаях функция возвращала значение false, когда эффективно находила нужный узел.Этот код работает: n указатель на корневую ноту дерева, "летрадада" - буква на искомом узле, кадена строки с маршрутом (например: 01101) 

bool recorrerarbol(nodo *n, char letradada, string &cadena){
    if(n!=NULL){
            if(n->letra==letradada){
                    cadena=to_string(n->binario)+cadena;
                    return true;
            }
            else{
                    if(recorrerarbol(n->izq,letradada,cadena)){
                            if(n->binario==-1) return true;
                            cadena=to_string(n->binario)+cadena;
                            return true;
                    }
                    else{
                            if(recorrerarbol(n->der,letradada,cadena)){
                                    if(n->binario==-1) return true;
                                    cadena=to_string(n->binario)+cadena;
                                    return true;
                    }}
            }
    }
    return false;
    }

Спасибо всем

...