Wsadzenie elementu na drzewo

Witam. Mam do skonstruowania drzewo które będzie przetrzymywać wyrażenia logiczne typu: AND AND T F T. Nie mam pomysłu w jaki sposób zrealizować funkcję wstawiania tych wyrażeń na te drzewo. Moja aktualna funkcja wstawiania elementu nie działa dla dłuższych wyrażeń logicznych, dodam ze mam napisaną już funkcję która rozbija wyrażenie i wstawia do parametru nowawartość kolejne instrukcje:AND,AND,T,F,T. Bardzo prosiłabym o jakąś pomoc. Z góry dziękuje.

 

struct drzewo{
	bool typ;	//1-operator, 0-operand
	char dana;
	drzewo* rodzic;
	drzewo* lewy;
	drzewo* prawy;
	
	drzewo();

	drzewo(char d)	//konstruktor dla danej
	{
		dana=d;
		lewy=NULL;
		prawy=NULL;
	}

};


void wsadzelement(drzewo *&korzen, char nowawartosc, bool operator)
{
	if(korzen==NULL)
	{
		korzen=new drzewo(nowawartosc);
		korzen->typ=operator;
		return;
	}
	if(korzen->lewy!=NULL)
	{
	if(korzen->lewy->typ)
		wsadzelement(korzen->lewy,nowawartosc,operator);
	}
	if(korzen->prawy!=NULL)
	{
	 if(korzen->prawy->typ)
		wsadzelement(korzen->prawy,nowawartosc,operator);
	}
	if(korzen->lewy==NULL)
		wsadzelement(korzen->lewy,nowawartosc,operator);
	else if(korzen->prawy==NULL)
		wsadzelement(korzen->prawy,nowawartosc,operator);

}

Jeśli dobrze zrozumiałem to masz wyrażenie podane w odwrotnej notacji polskiej (kolejka) i trzeba to zamienić na drzewo wywołań?

Algorytm będzie taki:

[A]

1. Jeśli kolejka jest pusta - wyrażenie jest nieprawidłowe - zakończ algorytm
2. Weź pierwszy element z kolejki i umieść w drzewie (korzeń)
3. Dla wstawionego elementu drzewa wykonuj [B]
4. Jeśli w kolejce pozostały jakieś elementy - wyrażenie jest nieprawidłowe

[B]

1. Jeśli element drzewa jest operandem - wyjdź z [B]
2. Jeśli kolejka jest pusta - wyrażenie jest nieprawidłowe - zakończ algorytm
3. Weź kolejny element kolejki i umieść go w drzewie jako lewe dziecko
4. Dla wstawionego dziecka wykonuj [B]
5. Jeśli kolejka jest pusta - wyrażenie jest nieprawidłowe - zakończ algorytm
6. Weź kolejny element kolejki i umieść go w drzewie jako prawe dziecko
7. Dla wstawionego dziecka wykonuj [B]

W porządku dziękuje za odpowiedź, już troszeczkę problem mi się rozjaśnia. Mam jednak jeszcze 2 pytania: Czy wskaźnik rodzica jest potrzebny w takim drzewie?. Jak to będzie z operatorem jednoargumentowym NOT, z góry przypisywać dla niego prawe lub lewe dziecko stale na NULL?

Wskaźnik rodzica raczej nie będzie potrzebny.

Dla operatorów jednoargumentowych odpadają kroki B5, B6 i B7. No i dziecko będzie wtedy tylko jedno, drugie można oznaczyć jako NULL.

Rozpisałam sobie algorytm na kartce i chyba nie do końca to będzie działać. Może jednak potrzebny będzie wskaźnik na rodzica, żeby w przypadku kiedy dana dojdzie do końca np:lewej gałęzi drzewa i nie będzie już miejsc na umieszczenie danej, to cofa się i szuka miejsc w podgałęziach.

Jak "nie będzie miejsca"? Do takiej sytuacji nie dojdzie. Kod będzie mniej więcej taki, jak poniżej. Zauważ, że nie ma tu problemu "braku miejsca":

(funkcje zwracają false w przypadku błędnego wyrażenia)

bool BudujDrzewo(Kolejka *&kolejka, Drzewo *&korzen)
{
    if (CzyKolejkaPusta(kolejka)) return false;       // A1. kolejka nie może być całkowicie pusta
    korzen = new Drzewo(KolejkaPobierz(kolejka));     // A2. wstawiamy pierwszy element jako korzeń drzewa
    if (!BudujGalezie(kolejka, korzen)) return false; // A3. dodajemy gałęzie
    return CzyKolejkaPusta(kolejka);                  // A4. sprawdzamy, czy opróżniliśmy całą kolejkę
}

bool BudujGalezie(Kolejka *&kolejka, Drzewo *rodzic)
{
    // B1. jeśli operand - nic wiecej do zrobienia, wychodzimy
    if (CzyOperand(rodzic)) return true;

    // B2. jeśli brakło elementów - błędne wyrażenie, wychodzimy
    if (CzyKolejkaPusta(kolejka)) return false;             
    // B3. pobieramy pierwszy argument i wstawiamy do drzewa
    rodzic->lewy = new Drzewo(KolejkaPobierz(kolejka));
    // B4. dodajemy kolejne gałęzie do wstawionego argumentu
    if (!BudujGalezie(kolejka, rodzic->lewy)) return false;

    // jeśli operator jednoargumentowy - nic wiecej do zrobienia, wychodzimy
    if (CzyOperatorJednoargumentowy(rodzic)) return true;

    // B5. jeśli brakło elementów - błędne wyrażenie, wychodzimy
    if (CzyKolejkaPusta(kolejka)) return false;
    // B6. pobieramy drugi argument i wstawiamy do drzewa
    rodzic->prawy = new Drzewo(KolejkaPobierz(kolejka));
    // B7. dodajemy kolejne gałęzie do wstawionego argumentu
    return BudujGalezie(kolejka, rodzic->prawy);
}