Na którym poziomie w drzewie leży element?

Question

Witam,

mam kompletne drzewo binarne o p poziomach. I muszę odpowiedzieć, na którym poziomie leży element 229. Jest na to jakiś wzór czy trzeba sprawdzać po kolei każdy poziom. Pomocy, jutro mam klasówkę!

 

P.S. Chyba dobra kategoria :)

Answer 1

wydaje mi się, że to może być przydatne:

https://www.geeksforgeeks.org/check-if-value-exists-in-level-order-sorted-complete-binary-tree/

Mam nadzieję, że trochę kojarzysz C++ :)  Jeżeli nie to można sobie zmienić język na jakiś inny :) 

Comments

No właśnie do klasówki z C++ tego potrzebuje. Dzięki

Answer 2

Drzewo binarne na 1 poziomie ma odwołania do 2 dzieci, to się  sprowadza do prostej matematki... 1 poziom 1 element 2 poziomy 3 elementy... 3 poziomy  7 elementów... widać tutaj sume? 

jest pewna zależność i to generuje wzór. 

2^p - 1  (^- potęga) natomiast p - to liczba poziomów)

zatem przystaw to 229 = 2^p-1
https://eduinf.waw.pl/inf/utils/013_2013/0208.php

Comments

No i mam pełne powtórzenie o drzewkach. Dzięki

---

na stronie również masz przykłady implementacji, generalnie ogrom wiedzy w zakresie algorytmów czy to do szkoły, czy na studia.