Szukanie w nieuporzadkowanym drzewie binarnym

soku11 · Post autor: **soku11** » 25 gru 2007, o 22:30

WITAM!
Jak w temacie. Mam drzewo binarne ktore wyglada np tak:
... 63e57.html

Jako zadananie mam takie cos. Uzytkownik podaje 3 liczby out,in1,in2. Nastepnie funkcja sprawdza cale drzewo, czy stnieje mozliwosc zrobienia takiego polaczenia. Dla przykladu aby zrobic polaczenia pierwsze od gory uzytkownik podaje 12, 3, 7. Reprezentacje struktury przechowujacej te dane mozna stworzyc np tak:

Kod: Zaznacz cały

typedef struct bt
{
  unsigned int out;
  unsigned int in1,in2;
  struct bt *next;
  struct bt *previosu1,*previosu2;
} bt;

bt *start;

Teraz jak zrobic funkcje, ktora przeszuka to drzewo galaz po galezi i stwierdzi, czy takie polaczenie moze istniec?? Oczywiscie nie moze przyjac np czegos takiego: 6,2,18, bo 2 jest juz uzyta do innego polaczenia :/ Kombinowalem cos w stylu:

Kod: Zaznacz cały

typedef unsigned int uint;
uint found_in,found_out;

bt *search(logic_gate *gate,const uint out,const uint in1,in2)
{
  bt *tmp;
  tmp=gate;

  if(gate == NULL) return NULL;

  if(gate->in1 == out || gate->in2 == out)
    found_in++;
  else
  if(gate->out == in1 || gate->out ==in2 || gate->in1 == out || gate->in2 == out)
    found_out++;
  else
  {
    search(gate->previous1,out,in1.in2);
    search(gate->previous2,out,in1,in2);
  }
  
  return tmp;
}
...
...
if(found_in==1 && found_out==0) add_connection();
...

Czy ten kod sie nadaje?? Z gory dzieki za kazda pomoc. POZDRO

kadiii · Post autor: **kadiii** » 26 gru 2007, o 21:47

Witaj. Z tego co zrozumiałem chodzi ci o to aby sprawdzić czy w drzewie jest gałąź o wartości out i nie ma gałęzi o wartościach in1 i in2(czy może jeśli istnieje taki out dla którego jedną gałęzią jest np.in1 a druga to NULL to można dopisać tam in2?). Jeśli tak, to ja bym to zrobił tak: przeszukał dzrzewo i jeśli wartość gałęzi to in1 lub in2 to przerwał szukanie z negatywnym wynikiem(nie wiem, np.zwrócił zero) a jeśli znajdę out to jeśli wskazuje na dwa NULL-e to ustawiam wskaźnik na tej gałęzi i szukam dalej czy w drzewie nie wystąpiło in1 i in2(co uniemożliwiłoby takie połączenie). Po przeszukaniu całego drzewa sprzwdzamy jeżeli nie zwróciła funkcja zera to jeżeli wskażnik out wskazuje na coś to tam dołączamy in1 i in2 a w przeciwnym wypadku możemy dołączyć na dowolnym liściu. Poza tym taką strukturę drzewa chyba raczej powinna wyglądzać tak:

Kod: Zaznacz cały

typedef struct bt
{
unsigned int value;//która będzie w zależności od miejsca reprezentować in albo out
struct bt *right,*left;//u ciebie jakoś trochę dziwnie choć może ja nie rozumiem twojej ideii(ale zapomniałeś raczej na pewno o * przy previous2
}binary_tree;

Takie drzewko powinno być raczej jak lista, tylko że zamiast liniowości mamy rozgałęzienia(dwa wskaźniki zamiast jednego). Mam nadzieję, że to cokolwiek pomogłem Jak będziesz miał jakieś pytania to chętnię odpowiem jeśli tylko będę potrafił. Pozdrawiam

soku11 · Post autor: **soku11** » 26 gru 2007, o 23:03

Hehe nie wiem czy ja dobrze rozumiem twoje zrozumienie Program ma pobierac od uzytkownika dodatnie wartosci out,in1,in2. Nastepnie ma sprawdzic, czy mozna zrobic takie polaczenie, aby wartosc out odpowiadala jakiemus lisciowi w drzewie, oraz wartosci in1 i in2 sie nie powtarzaly (nie bylo zadnego sprzezenia). Poradzilem juz sobie ze sprawdzaniem tych powtorzen poprzez zrobienie dwoch tablic jednej t_out oraz t_in z wartosciami out i in w drzewie. Jesli jest jedno out i nie ma in, mozna robic polaczenie. Teraz probuje napisac funkcje, ktora szuka pierwszego elementu out w tym oto drzewie, i zwraca wskaznik na ten element. Struktura ma wygladac tak jak wyglada oczywiscie z *. Napisalem ja tak, bo to drzewo ma byc niejako odwrocone w prawo o 90 stopni, i wszystko co odchodzi od wezla w lewo ma byc previous a to co po prawo ma byc next. Musze uzywac drzewa w dwoch kierunkach, by moc pozniej bawic sie w przejscia wartosc - to drzewo to maja byc polaczone bramki logiczne Jakbys mogl to napisz jakas standardowa funkcje ktora przeszukuje to drzewo i jak znajdzie juz ta wartosc out to zwraca wskaznik na element zawierajacy. POZDRO

kadiii · Post autor: **kadiii** » 26 gru 2007, o 23:26

No to ja powiem, że nie wiem nadal czy dobrze cię rozumiem. To chyba nie ma znaczenia czy to jest posiomo czy obrócone bo przecież komputer tego sobie nie wyobraża potem(a może? ). Przyjmując więc twoje oznaczenia ja bym tą strukturę widział tak.
struck bt{
unsigned int value;
struct bt *next;
struct bt *previous,*previous2;
}
Nie bardzo rozumiem co robią u ciebie pozostałe składniki struktury. Ty to jakoś trójkami przechowujesz? Bo jak dla mnie jeśli to ma być drzewo binarne to strukturą oprogramowujesz jeden węzeł. Rozjaśnij trochę swoją ideę.

soku11 · Post autor: **soku11** » 26 gru 2007, o 23:33

No tak pisalem ze jest tego inna orientacja, zebys zrozumial moj zapis previous a nie son Niestety w strukturze potrzebuje 3 wartosci, bo jak pisalem maja to byc bramki logiczne. Bramka np AND bedzie miala np wyjscie oznaczone 1 a wejscia jako 2 i 3. Pozniej aby podlaczyc pod 2 kolejna bramke uzytkownik ma wpisac 2=4and5 i wtedy ma sie zrobic bramka logiczna na wejsciu 2 z kolejnymi dwoma wyjsciami 4 i 5, itd... Potrzebne jest to numerowanie by odnajdowac bledy w skladni wprowadzonej komendy oraz do inych komend. Bo programik ma jeszcze robic poprzez polecenie np. test 00100 probe bramek, gdzie kolejne wartosci sa podawane na kolejne wolne ponumerowane wejscia. Oczywiscie jeszcze ma byc komenda show ktora wyswietli wszystkie poprawne polaczenia podobnie jak wpisuje to uzytkownik Mam nadzieje ze juz troche bardziej rozumiesz POZDRO

kadiii · Post autor: **kadiii** » 27 gru 2007, o 00:05

No to widzę nawet całkiem ciekawy program tworzysz . Tylko jeszce jednej rzeczy nie bardzo rozumiem. Te numery na gałęziach reprezentują wyjścia z różnych bramek? Jeśli tak, to proponuję dodać jakieś pole np. gate_id w którym byłby przechowywany numer bramki, i wtedy jeśli chcemy przyłączyć jakeś dwie bramki to szukamy czy już ich nie użyliśmy po tym właśnie id, a sygnałom out i in pozostawiamy zadanie jedynie przeliczalne na operacjach bramkowych.
Co o tym myślisz?

soku11 · Post autor: **soku11** » 27 gru 2007, o 00:20

Najlepiej to widac na rysunku co zalaczylem do pierwszego mojego postu

Takie drzewo sie tworzy poprzez wpisanie przez uzytkownika ciagu instrukcji:
12=3and7
3=not2
7=56or67
...
(typy bramek and i or nie sa zaznaczone na rysunku - tylko widac gdzie not - jedno odgalezienie). Jak obrocisz obrazek w prawo o \(\displaystyle{ 90^{\circ}}\) to wyjscie odchodza z kazdej kropki w prawo (kazda bramka ma jedno wyjscie - chyba logiczne

), natomiast wejscie masz dwa lub jedno w zaleznosci od typu bramki i jest to odgalezienie/a po lewo od kropki. Przykladowo bramka pierwsza (root) ma wyjsce 12 oraz dwa wejscie 3 oraz 7. Bramka 'not' pierwsza po lewej ma wyjscie 3 polaczone do wejscie roota (odpowiadajacy numerek - 3) a jej wejsciem jest 2. Moglbys skrobnac jakas funkcje albo cos aby przeszukiwalo drzewo az do znalezienia tego elementu z odpowiadajaca wartoscia out?? Bo lipa polega na tym, ze trzeba pewnie zastosowac jakas rekurencje tak, aby byla sprawdzona kazda galaz podgalaz i lisc. Mam taki drobny szkic tego, jednak nie jestem pewien czy dobrze bedzie dzialac :/ POZDRO

kadiii · Post autor: **kadiii** » 27 gru 2007, o 00:40

Nie wiem jak dla mnie to dodanie tego id byłoby dobrym rozwiązaniem(jako oznaczenie numeru sygnału). Co do funkcji to trochę już późno więc nie chcę się pomylić. Podaję linka ... /ol015.php gdzie masz funkcję przechodzenia drzewa. Trzeba tylko zmienić strukturę dodając te twoje pola out, in1,in2 i dodając w funkcji parametr sz_out i warunek if(n->out==sz_out).

soku11 · Post autor: **soku11** » 27 gru 2007, o 01:00

Dzieki przeczytam to i postaram sie cos sam napisac

Jakby ci sie chcialo to tez mozesz zarzucic jutro swoim kodem w wolnej chwili. POZDRO

[ Dodano: 27 Grudnia 2007, 17:32 ]
Wykombinowalem cos takiego:

Kod: Zaznacz cały

unsigned int found gate=FALSE;

bt *search_gate(bt *gate,unsigned int out_num)
{
  bt *tmp=gate;
  
  if(!found_gate)
  {
    if(tmp->in_num1 == out_num || tmp->in_num2 == out_num)
    {
      found_gate=TRUE;
      return tmp;
    }
    else
    {
      tmp=search_gate(tmp->previous_gate1,out_num);
      if(!found_gate)
       tmp=search_gate(tmp->previous_gate2,out_num);
       
      return tmp;
    }
  }
  else 
  return tmp;
}

bt*attach=search_gate(start,2);

a koncu jest wywolanie w celu odnalezienia out_num = 2. Wiemy ze takie jest na pewno jedno i tylko jedno. Problem w tym, ze ten algorytm wykrzacza sie jak sie przeszuka cos w right son... Tzn nie rzechodzi tam wogole tylko sie zwiesza :/ Moze ktos rzucic okiem i podsunac jakis pomysl na poprawe, optymalizacje?? POZDRO