Drzewo binarne - liczenie powtarzających się wpisów

Witam,

Mam pytanie odnośnie powtarzających się danych w drzewie binarnym i ich liczenia. Otóż mam sobie taką funkcję:

struct tree * add_node(struct tree *p, int number) {

	if (p == NULL) {
		p = (struct tree *)malloc(sizeof(struct tree));
		p->value = number;
		p->left = p->right = NULL;
		p->count = 1;
	}
	else if (number == p->value)
		p->count++;
	else if (number>p->value)
		add_node(p->right, number);
	else
		add_node(p->left, number);

	return p;

}

I przykładowo takiego maina:

struct tree *ptr = NULL;

	ptr = add_node(ptr, 100);
	ptr = add_node(ptr, 50);
	ptr = add_node(ptr, 120);
	ptr = add_node(ptr, 110);
	ptr = add_node(ptr, 19);
	ptr = add_node(ptr, 100);

	print_tree(ptr);

I jak dokładnie program liczy powtarzające się liczby? W tym przypadku dla 100 zwróci liczbę 2, ale pierwsze i ostatnie wywołanie funkcji to już są 2 zupełnie różne wskaźniki. Czy to jest tak, że w pamięci są równolegle zapisane wszystkie te strktury i program jest w stanie to policzyć mimo że w funkcji w danej chwili jest już przetwarzana inna struktura?

O czym ty mówisz? Przecież w kodzie wstawiania węzła masz jak byk napisane:

        else if (number == p->value)
                p->count++;

czyli: "jeśli element w drzwie juz jest, bo go znaleźliśmy to podbij licznik elementów o tym kluczu o 1 w górę.
To znaczy ze w drzewie każdy węzeł oprócz klucza przechowuje też ilość wystąpień.

No to jest jasne. Ale moje dotyczy samej istoty działania takiej formy danych jak ta lista oparta na strukturach. Czy to jest tak, że moją listą w tym przypadku jest wiele struktur znajdujących się w pamięci w tym samym czasie połączonych wskaźnikami do siebie? Nie wiem, czy dobrze wytłumaczyłem o co mi chodzi :)

Odpowiedź brzmi: tak, na tym zwykle polegają struktury listowe i drzewiaste że masz elementy polączone wskaźnikami.

Spoko, ja po prostu dopiero zaczynam. Dzięki :) Mam jeszcze jedno pytanie. Jak wygląda przykładowe drzewo dla tej funkcji add_node() wykorzystanej w ten sposób w mainie:

struct tree *ptr = NULL;

	ptr = add_node(ptr, 100);
	ptr = add_node(ptr, 50);
	ptr = add_node(ptr, 120);
	ptr = add_node(ptr, 110);
	ptr = add_node(ptr, 19);
	ptr = add_node(ptr, 8);

	print_tree(ptr);

Bo moim zdaniem, zgodnie z kodem, powinno to być coś takiego jak w jedynce.

Ale w takim wypadku nie jest to raczej drzewem binarnym. Logika nakazywałaby więc coś podobnego do dwójki, chociaż i tam nie jest idealnie (zły dobór liczb?). Ogólnie chodzi o to, że ja tę funkcję rozumiem tak, że kolejne wartości dodawane są do dzieci dziecka, więc jedna ze stron ciągle jest pusta. Ale pewnie coś źle rozumiem :)

Wygląda tak jak 2 i wynika to jasno z kodu. Każdy węzeł jest dodawany od i jest porownywany z kolejnymi węzłami idąc w dół. Jeśli klucz dodawanego węzła jest > od klucza aktualnego węzła to idziemy w prawo, jeśli nie to w lewo.
Nie rozumiem jak chciałbyś uzyskać drzewo podane jako 1. W chwili dodawania 120 dzieje się tak:

• porównujemy 120 z 100, jest większe więc idziemy w prawo
• z prawej strony od 120 nic nie ma, więc 120 zostaje tam wstawione.
  Nie rozumiem też jak chciałbyś 110 wstawić tak jak w 1. Wstawiając 110 dzieje się tak samo jak dla 120 -> w korzeniu drzewa od razu skręcamy w prawo bo 110 > 100

A ty chyba nie wiesz co to jest drzewo binarne. Drzew binarne to takie gdzie każdy węzeł ma nie więcej niż 2 dzieci. Może tobie myli się drzewo binarne ze zrównoważonym drzewem binarnym (AVL)?

Dzięki za cierpliwość, ale muszę jeszcze jedną rzecz wyjaśnić. Bo patrz:

Na początku ptr jest NULL-em, więc dodajemy 100 i mamy te 100 na górze. Jeszcze raz uruchamiamy funkcje add_node(), ptr nie jest już NULL-em, więc porównujemy: 50 jest mniejsze od 100, więc ląduje po lewej. ALE: teraz nie wracamy już przecież do węzła ze 100, tylko jesteśmy w węźle z 50. I moim zdaniem w takim wypadku sprawdzalibyśmy, czy 120 jest większe od 50. Jest, więc ląduje po prawej, ale po prawej od 50 stając się jakby wnuczkiem węzła ze 100. Do tego węzła pierwszego (ze 100) wracamy rekurencyjnie dopiero na szarym końcu, dlatego jest on cały czas pierwszy, ale moim zdaniem przez to wartości dodają się niesymetrycznie.

Och tak? A przypatrz się uważnie który wskaźnik przekazujesz do funkcji i który jest modyfikowany! Wskaźnik przekazany do funkcji jest modyfikowany TYLKO jeśli jest nullem. To znaczy ze dodajac pierwszy węzeł zostanie on zmodyfikowany, ale przy każdym kolejnym dodaniu już nie, tam będą modyfikowane tylko wskaźniki NULLowe po prawej lub po lewej itd.

O matko, jak mogłem tego nie zauważyć. Serio, wielkie dzięki za poświęcony czas :) Teraz już wszystko jest jasne jak słońce.

Trochę późno, wiem, ale mimo wszystko chciałbym podjąć pewien temat z tym związany.
Otóż mam pewne zadanie ale jego treść jest bardzo niejednoznaczna dlatego pytania które tutaj zadam proszę rozpatrywać czysto teoretycznie i naprawdę w luźny sposób.
Chciałbym zaimplementować algorytm zliczania powtarzających się wyrazów używając takiego drzewa binarnego, z pliku chciałbym wczytać słowo po słowie i pakować je do struktur (node) i łączyć je z drzewem za pomocą wskaźników, i nie robi to na mnie kompletnie wrażenia i jest spokojnie do zrobienia.
Problem pojawia się ponieważ w tej niejednoznacznej treści pisze że mam obowiązek wykorzystać dziedziczenie i funkcje wirtualne.
Oczywiście wiem co to jest bo programuję od wielu wielu lat w C#, C++ i ANSI C.
Nie jestem jednak w stanie wykapować po co i gdzie miałoby to być w tym akurat zadaniu wykorzystane, inaczej: chodzi mi o to aby ktoś zarzucił pomysłem w jaki sposób wykorzystać dziedziczenie i funkcje wirtualne do realizacji problemu tworzenia drzewa binarnego (które nota bene zawierać powinno : ilość powtórzeń, string dane, wskaźnik na synów z lewej i prawej strony).

Help, give me some idea please.

No może się da -- zrób klasę abstrakcyjną Drzewo, oraz dwie pochodne DrzewoPuste oraz DrzewoNiepuste.

To nawet nie jet tak bardzo bez sensu jak się wydaje... :)

Kolego @koszalek-opalek dzięki za odp. Dodam tylko że programuję w C++ a to oznacza że chcąc wytworzyć klasę abstrakcyjną muszę w niej mieć przynajmniej jedną metodę czysto wirtualną i nie będę mógł tworzyć obiektów tej klasy (tylko i wyłącznie jej pochodnych czyli DrzewoPuste i DrzewoNiepuste) i nie piszę tego dlatego żeby Ci to powiedzieć tylko dlatego żeby samemu sobie to utrwalić dokładnie.

Ale do Ciebie kolego @koszalek-opalek mam takie pytanie w związku z Twoją propozycją. Czy mógłbyś rozwinąć trochę swój pomysł z tymi dwoma klasami pochodnymi? Jak wg Ciebie miałoby to działać? Inaczej - po co mi klasy pochodne od abstrakcyjnej jeśli przecież mogę dać jedną klasę drzewo i w tej klasie zaimplementować listę która to drzewo realizuje? Inaczej: jak wg Ciebie z poziomu tych dwóch klas (czyli zgodnie z wymogiem użycia klasy abstrakcyjnej i metod wirtualnych) rozwiązać problem konstrukcji takiego drzewa? Proszę Cię uprzejmie o bardziej szczegółową wypowiedź.

Adamos19 napisał(a):

Jak wg Ciebie miałoby to działać?

Poniżej szkic początku kodu.

Inaczej - po co mi klasy pochodne od abstrakcyjnej jeśli przecież mogę dać jedną klasę drzewo i w tej klasie zaimplementować listę która to drzewo realizuje?

Tak, wiem, było to też w komentarzach kolegów do Twojego wcześniejszego postu. To Ty sam chciałeś tak się bawić... :)

Inaczej: jak wg Ciebie z poziomu tych dwóch klas (czyli zgodnie z wymogiem użycia klasy abstrakcyjnej i metod wirtualnych) rozwiązać problem konstrukcji takiego drzewa? Proszę Cię uprzejmie o bardziej szczegółową wypowiedź.

Rzuć okiem na kod, jesli wyjaśni sprawę, to napisz, a jesli nie, to też napisz. :)

using Zawartosc = int;  // tylko dla ustalenia uwagi, może być cokolwiek;
                        // ewentualnie można poniżej przerobić wszystko
                        // na szablony


class Drzewo {
public:
    virtual ~Drzewo() {}
    virtual Drzewo * idz_w_lewo() =0;
    virtual Drzewo * idz_w_prawo() =0;
    virtual Zawartosc * zawartosc() =0;
    /* od C++17 może lepiej:
    virtual std::optional<Zawartosc> zawartosc() =0;
    */
};

class DrzewoPuste : public Drzewo {
public:
    virtual ~DrzewoPuste() {}
    Drzewo * idz_w_lewo() override {
        return nullptr;
    }
    Drzewo * idz_w_prawo() override {
        return nullptr;
    }
    Zawartosc * zawartosc() override {
        return nullptr;
    }
};

class DrzewoNiepuste : public Drzewo {
private:
    Zawartosc x;
    Drzewo * lewe;
    Drzewo * prawe;
public:
    DrzewoNiepuste(const Zawartosc & zaw, Drzewo & l, Drzewo & p)
    : x(zaw)
    , lewe(&l)
    , prawe(&p)
    {}
    // no itrzeba zdefiniować lub jawnie usunąć
    // konstruktory -- kopiujący i przenoszący
    // oraz podstawienia -- kopiujące i przenoszące
    virtual ~DrzewoNiepuste() { /* tu też coś pewnie trzeba... :) */ }
    Drzewo * idz_w_lewo() override {
        return lewe;
    }
    Drzewo * idz_w_prawo() override {
        return prawe;
    }
    Zawartosc * zawartosc() override {
        return &x;
    }
};