Maig al calendari SBM-XEIX

Els arbres binaris (Socarrell, Launaea cervicornis)

Els arbres binaris són un cas particular de graf on dos nodes estan units per un únic camí i cada node té com a màxim tres arestes. Els nodes que només tenen una aresta són les fulles. En són exemples els arbres de presa de decisions de sí o no, els diagrames d’arbre per representar els possibles resultats en diversos experiments (com per exemple llançar una moneda a l’aire) o els arbres d’ancestres d’una persona. Aquests darrers són arbres binaris complets i perfectes, és a dir, totes les fulles estan a la mateixa profunditat o altura (distància des de l’arrel). Sabríeu dir quin és el nombre de fulles en aquest cas? Idò sí, 2^h on h és la profunditat de les fulles.