Drzewo binarne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Drzewo binarne

Post autor: aneta909811 »

Niech \(\displaystyle{ T_{n}}\) bedzie zbiorem uporządkowanym w typ drzewa binarnego (do kazdego wierzchołka dochodzi jedna krawedz, a wychodzą - poza końcowymi wierzchołka - dwie krawedzie), ktorego wszystkie drogi od korzenia do wierzcholka koncowego maja te samą długość \(\displaystyle{ n}\). Ile wierzchołków ma takie drzewo?
Ostatnio zmieniony 9 lip 2019, o 09:34 przez aneta909811, łącznie zmieniany 1 raz.
Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Drzewo binarne

Post autor: leg14 »

Co to jest suma drogi?
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Drzewo binarne

Post autor: aneta909811 »

Przepraszam chodziło o długość drogi
Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Drzewo binarne

Post autor: leg14 »

Proponuje dowod indukcyjny
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Drzewo binarne

Post autor: aneta909811 »

Dobrze, tylko nie wiem właśnie ile to wierzchołków, z dowodem raczej sobie poradzę
Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: Drzewo binarne

Post autor: leg14 »

To na początek rozrysuj sobie przypadki dla \(\displaystyle{ n =1, n=2, n =3}\) - znajdź liczbę wierzchołków i popatrz jak wyglądają takie drzewa
aneta909811
Użytkownik
Użytkownik
Posty: 260
Rejestracja: 1 lut 2015, o 19:20
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 68 razy

Re: Drzewo binarne

Post autor: aneta909811 »

Czy \(\displaystyle{ w=2^{(n+1)}-1}\)?
Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: Drzewo binarne

Post autor: leg14 »

Tak - teraz czas na odwód indukcyjny
ODPOWIEDZ