Drzewo binarne przechowujące liczby

0

Witam mam napisać program który przechowuje liczby w drzewie binarnym. Napisałem ale nie działa tak jak powinien gdzie popełniłem błąd?
Wejście
Ciąg wierszy zakończony symbolem znaku końca pliku (EOF) reprezentujący poprawnie (zgodnie z powyższym opisem) pewne drzewo binarne T. Każdy pojedynczy wiersz zakończony znakiem nowej linii (kod ASCII 10) opisujący pozycję wierzchołka w drzewie T i zawierający:

  • liczba całkowita - etykieta wierzchołka,

  • znak odstępu (kod ASCII 32),

  • ciąg znaków L (kod ASCII 76) oraz R (kod ASCII 82) - ciąg skierowań krawędzi na ścieżce od korzenia drzewa do rozważanego wierzchołka.

#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>

using namespace std;

struct drzewo
{
       int liczba;
       drzewo *lewy,*prawy;
       
       drzewo(int liczba)
       {
                  this->liczba=liczba;
                  lewy = prawy = NULL;
       }
};
       

int main()
{
   drzewo * korzen = NULL;
   int value=0,len=0, liczba;
char ch;
bool ujemna = false;
drzewo** iter = &korzen;
while((ch=getchar())!=EOF)
  {
   if(ch=='-')
       ujemna = true;
   if(isdigit(ch))
     {
      	
      ++len;
      value=value*10+ch-'0';
     }
   else if(len)
     {
      if(ujemna)
	  {
	  	liczba = -value;
	  	ujemna = false;
	  }	
      else
		{
	      liczba = value;
	      value=len=0;
  		}
     }
     else if(ch == ' ')
         drzewo** iter = &korzen;
     else if(ch==10)
     {
     	if(*iter == NULL)
     	   *iter = new drzewo(liczba);
     	(*iter)->liczba = liczba;
     }
     else
     {
     	if(*iter == NULL)
     	   *iter = new drzewo(0);
     	if(ch == 'L')
     	   iter = &((*iter)->lewy);
     	if(ch == 'R')
     	   iter = &((*iter)->prawy);
     }
  }
  drzewo** ite = &korzen;
  cout << "Korzen wynosi " << (*ite)->liczba << endl;
}
1
prykaz napisał(a):

Napisałem ale nie działa tak jak powinien gdzie popełniłem błąd?
Błąd popełniłeś w olewaniu formatowania. Więc nie widzisz jakie bzdury wypisujesz.

0

Niestety nie rozumiem. Czy mógłbyś jaśniej mi wytłumaczyć?

0

Teraz po poprawieniu wydaje mi się że wygląda to przejrzyście

 #include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
 
using namespace std;
 
struct drzewo
{
       int liczba;
       drzewo *lewy,*prawy;
 
       drzewo(int liczba)
       {
                  this->liczba=liczba;
                  lewy = prawy = NULL;
       }
};
 
 
int main()
{
   drzewo * korzen = NULL;
   int value=0,len=0, liczba;
char ch;
bool ujemna = false;
drzewo** iter = &korzen;

while((ch=getchar())!=EOF)
  {
   		if(ch=='-')
       		ujemna = true;
   	 if(isdigit(ch))
     {
 
	      ++len;
	      value=value*10+ch-'0';
     }
     else if(len)
     {
      		if(ujemna)
          	{
                  liczba = -value;
                  ujemna = false;
                  value=len=0;
          	}	        
      		else
            {
	              liczba = value;
	              value=len=0;
            }
     }
     else if(ch == ' ')
         drzewo** iter = &korzen;
    
     else if(ch==10)
     {
             if(*iter == NULL)
                *iter = new drzewo(liczba);
             (*iter)->liczba = liczba;
     }
     else
     {
             if(*iter == NULL)
                *iter = new drzewo(0);
             if(ch == 'L')
                iter = &((*iter)->lewy);
             if(ch == 'R')
                iter = &((*iter)->prawy);
     }
  }
  drzewo** ite = &korzen;
  cout << "Korzen wynosi " << (*ite)->liczba << endl;
}
1

Już znacznie lepiej ale nie do końca, wcięcia muszą być takie same na takim samym poziomie zagłębienia.
Wypisz sobie (osobno w notepadzie) drabinkę if'ów wewnątrz while bez zawartości.

0 
 
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
 
using namespace std;
 
struct drzewo
{
       int liczba;
       drzewo *lewy,*prawy;
 
       drzewo(int liczba)
       {
                  this->liczba=liczba;
                  lewy = prawy = NULL;
       }
};
 
int main()
{
	drzewo * korzen = NULL;
	int value=0,len=0, liczba;
	char ch;
	bool ujemna = false;
	drzewo** iter = &korzen;
	while((ch=getchar())!=EOF)
	{
			if(ch=='-')
				ujemna = true;
			if(isdigit(ch))
			{
				++len;
				value=value*10+ch-'0';
			}
			else if(len)
			{
				if(ujemna)
				{
					  liczba = -value;
	                                  ujemna = false;
	                                  value=len=0;
				}
				else
				{
					  liczba = value;
		                          value=len=0;
				}
			}
			else if(ch == ' ')
			{
				drzewo** iter = &korzen;
			}
			else if(ch==10)
			{
				if(*iter == NULL)
                                           *iter = new drzewo(liczba);
                                
                                (*iter)->liczba = liczba;
			
			}
			else
			{
				if(*iter == NULL)
				{
					*iter = new drzewo(0);
				}
				if(ch == 'L')
				{
					iter = &((*iter)->lewy);
				}
				if(ch == 'R')
				{
					iter = &((*iter)->prawy);
				}
			}
	}
	drzewo** ite = &korzen;
	cout << "Korzen wynosi " << (*ite)->liczba << endl;
}
1

Wciąż nie rozumiesz?
Ok to powiedz mi co ma zostać spełnione żeby program wszedł w tego if'a: if(ch == ' ') ?

0

Ustawia wskaźnik który przechodzi po kolejnych liściach drzewa na korzeń. A warunek będzie spełniony jeśli ch będzie znakiem spacji. Prawdopodobnie się mylę bo zdaję sobie sprawę, że przy Tobie jestem laikiem z programowania, ale według mnie tak należało rozwiązać ten problem. W momencie jak mam takie dane 6 RLR. To najpierw muszę ustalić wskaźnik na roota polem przejść na prawy dalej lewy i znowu prawy liść.

1

Dobra uproszczę twój kod do:

a=?;
if(a==1)  cout<<"jeden";
else if(a!=1) cout<<"nie jeden";
else cout<<"nigdy tu nie trafisz";

Co trzeba wpisać w zmienną a żeby wyświetliło się nigdy tu nie trafisz ?

0

A teraz dlaczego program się załamuje

#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
 
using namespace std;
 
struct drzewo
{
       int liczba;
       drzewo *lewy,*prawy;
 
       drzewo(int liczba)
       {
                  this->liczba=liczba;
                  lewy = prawy = NULL;
       }
};
 
 
int main()
{
	drzewo * korzen = NULL;
	int value=0,len=0, liczba;
	char ch;
	bool ujemna = false;
	drzewo** iter = &korzen;
	
	while((ch=getchar())!=EOF)
	  {
	     if(ch=='-')
	     	ujemna = true;
	       		
	     if(ch == 32)
	         drzewo** iter = &korzen;
		
	     if(ch==10)
	     {
	             if(*iter == NULL)
	                *iter = new drzewo(liczba);
	             (*iter)->liczba = liczba;
	     }
	   	 if(isdigit(ch))
	     {
	 
		      ++len;
		      value=value*10+ch-'0';
	     }
	     else if(len)
	     {
	      		if(ujemna)
	          	{
	                     liczba = -value;
	                     ujemna = false;
	                     value=len=0;
	          	}	        
	      		else
	               {
		              liczba = value;
		              value=len=0;
	               }
	     }
	     else
	     {
	     
		     if(*iter == NULL)
		        *iter = new drzewo(0);
		     if(ch == 'L')
		        iter = &((*iter)->lewy);
		     if(ch == 'R')
		        iter = &((*iter)->prawy);
	    }
	  }
	  drzewo** ite = &korzen;
	  cout << "Korzen wynosi " << (*ite)->liczba << " a lewy wynosi "<< (*ite)->lewy->liczba << endl;
}
1

Teraz nie trafia w else.
Wywal tego swojego cholernego if(len) wraz z zawartością.
Pod if(ch == ' ') dodaj:

liczba=ujemna?-value:value;

Pod if(ch=='\n') dodaj:

ujemna=value=0;
0

Zmieniłem, ale dalej jak wprowadzam dane to program albo się wiesza albo wypisuje niepoprawne drzewo

1

A my oczywiście mamy zgadnąć jak zmieniłeś ...

0 
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
 
using namespace std;
 
struct drzewo
{
       int liczba;
       drzewo *lewy,*prawy;
 
       drzewo(int liczba)
       {
                  this->liczba=liczba;
                  lewy = prawy = NULL;
       }
};
 
 
int main()
{
	   drzewo * korzen = NULL;
	   int value=0,len=0, liczba;
	char ch;
	bool ujemna = false;
	drzewo** iter = &korzen;
	
	while((ch=getchar())!=EOF)
	  {
	     if(ch=='-')
	       	 ujemna = true;
	       		
	     if(ch == 32){
	         liczba=ujemna?-value:value;
	         drzewo** iter = &korzen;
	     }
	     if(ch==10)
	     {
	             ujemna=value=0;
				 if(*iter == NULL)
	                *iter = new drzewo(liczba);
	             (*iter)->liczba = liczba;
	     }
	   	 if(isdigit(ch))
	     {
	 
		      ++len;
		      value=value*10+ch-'0';
	     }
	     else
	     {
		     if(*iter == NULL)
		        *iter = new drzewo(0);
		     if(ch == 'L')
		        iter = &((*iter)->lewy);
		     if(ch == 'R')
		        iter = &((*iter)->prawy);
	    }
	  }
	  drzewo** ite = &korzen;
	  cout << "Korzen wynosi " << (*ite)->liczba << " a lewy wynosi "<< (*ite)->lewy->liczba << endl;
}
0 
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
 
struct drzewo
  {
   int liczba;
   drzewo *lewy,*prawy;
   drzewo(int liczba):liczba(liczba),lewy(0),prawy(0) {}
  };
 
int main()
  {
   drzewo *korzen=0,**iter=&korzen;
   int value=0,ch;
   bool ujemna=false;
   while((ch=getchar())!=EOF)
     {
      if(ch=='-') ujemna=true;
      else if(ch == 'L') iter = &((*iter)->lewy);
      else if(ch == 'R') iter = &((*iter)->prawy);
      else if(isdigit(ch)) value=value*10+ch-'0';
      else if(ch=='\n')
        {
         *iter=new drzewo(ujemna?-value:value);
         ujemna=value=0;
         iter=&korzen;
        }
     }
   cout << "Lewy Lewy wynosi "<< korzen->lewy->lewy->liczba << endl;
   cout << "Lewy wynosi "<< korzen->lewy->liczba << endl;
   cout << "Lewy Prawy wynosi "<< korzen->lewy->prawy->liczba << endl;
   cout << "Korzen wynosi " << korzen->liczba <<endl;
   cout << "Prawy Lewy wynosi "<< korzen->prawy->lewy->liczba << endl;
   cout << "Prawy wynosi "<< korzen->prawy->liczba << endl;
   cout << "Prawy Prawy wynosi "<< korzen->prawy->prawy->liczba << endl;
   return 0;       
  }

http://ideone.com/btkRjT

0

Działa tylko po wypisaniu danych program się załamuję i zwraca błąd SIGSEGV

0

Nie wypisuje w ogóle danych. Wrzucam zadanie na spoja i wyskakuje mi błąd SIGSEGV. A jak kompiluje program do kończy działanie

0

Jak widać z zadania może być tak że zaczyna się budowa drzewa od niezdeterminowanych gałęzi, więc trzeba ten program odpowiednio przerobić.

1 użytkowników online, w tym zalogowanych: 0, gości: 1