Palabra en un árbol V40142
Diremos que un BinTree<char> T representa una palabra word, formada por los caracteres c1c2… cn, con n≥ 0, si hay un camino en el árbol comenzando desde la raíz y de longitud n tal que los valores de los nodos del camino forman word. Implementad eficientemente la función count_word_in_paths, especificada a continuación:
/** * @pre `word` tiene al menos una letra * @post se retorna el número de caminos en T que representan * la palabra word desde la raíz */ int count_word_in_paths(const vector<char>& word, const BinTree<char>& T);
Por ejemplo, para la palabra "dia" si el árbol es t1, el resultado es 0, si el árbol es t2 el resultado es 3 y si el árbol es t3 el resultado es 1.
t1 = d t2 = d t3 = d
/ \ / \ / \
d d i i i i
/ \ / / \ / \
w i a a a a b
/ \ /
k a r
Observación
Solo es necesario que enviéis el código de la función en un archivo .cc, en el icono del gatito tenéis un .tar para poder compilar y probar vuestra solución.
count_word_in_paths("a", "a(b,)") → 1 count_word_in_paths("ab", "a(b,)") → 1 count_word_in_paths("abc", "a(b,)") → 0 count_word_in_paths("abc", "a(b(c,x),b(y,c))") → 2 count_word_in_paths("abc", "a(b,c(d,))") → 0
- Author
- PRO2
- Language
- Spanish
- Translator
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++