• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Moje drzewo binarne

Object Storage Arubacloud
+1 głos
787 wizyt
pytanie zadane 26 lutego 2018 w C i C++ przez Kurczak Użytkownik (940 p.)

Cześć, napisałem własną implementację drzewa binarnego za pomocą struktury. Prosiłbym o obiektywną ocenę mojej wersji, chciałbym się dowiedzieć który fragment wykonałem niezbyt elegancko, czy funkcje typu void nie powinny jednak być typu "węzeł" (node), ogólnie jestem otwarty na wszelkie uwagi, gdyż sposób wypracowałem praktycznie samodzielnie, a nie chcę uczyć się złych nawyków.
Kod:
 

#include "stdafx.h"
#include <iostream>

using namespace std;

typedef struct node   //pretty obvious part
{
	int value;
	node *left;
	node *right;
} node;

typedef struct tree //root is the very first element of our tree, current stands for currently used element
{
	node *root;
	node *current;
} tree;

void initialize(struct tree *t)   //Making initial tree
{
	t->root = NULL;
	t->current = NULL;
}

void addValue(struct tree *t, int value)      
{
	if (t->root == NULL)           //If working on initial tree
	{
		t->root = new node;      //dynamic memory allocation
		t->root->value = value; //passing the value
		t->root->left = NULL;  //as we've just initialized our tree, it's a lonely parent
		t->root->right = NULL;
	}                         
	else                                            //Tree's not empty!
	{
		bool placed = false;                       //Just so we know whether placing's finished or not
		while (placed == false)
		{
			while (value >= t->current->value && placed ==false)     //Keep going along right branch if inserted value is bigger than or equal to the actual
			{
				if (t->current->right != NULL)      //If right branch is not empty
					t->current = t->current->right; //go along right branch
				else                                //RIGHT BRANCH IS EMPTY!
				{
					t->current->right = new node;  //Dynamic memory allocation, for parrent to be
					t->current = t->current->right; 
					t->current->value = value;
					t->current->right = NULL;
					t->current->left = NULL;
					placed = true;               //Placing part's done.
				}
			}
				while (value < t->current->value)   //Analogically if value is smaller than current
				{
					if (t->current->left != NULL)
						t->current = t->current->left;
					else
					{
						t->current->left = new node;
						t->current = t->current->left;
						t->current->value = value;
						t->current->right = NULL;
						t->current->left = NULL;
						placed = true;
					}
				}
		}
	}
	t->current = t->root; //Next time, we would like to add a value, we have to start process from the root
}

void print(struct tree *t)      //Simple printing function
{
	char dir;
	if (t->current == t->root)             //First use of our function - we don't want to double-print our current parent
	{
		cout << "Root "<<t->root->value << endl;
		cout << " ------------Instruction Manual------------ " << endl;
		cout << "'a' or 'l' to go to left branch" << endl;
		cout << "'d' or 'r' to go to right branch" << endl;
		dir = getchar();
	}
	while (dir != EOF)
	{
		if(dir!='\n')  //We're confirming our choice with enter, so let's prevent printing twice
		if ((dir == 'a' || dir == 'l') && t->current->left != NULL)    //'a' or 'l' - go to the left branch if it's not empty!
		{
			t->current = t->current->left;
			cout << t->current->value << endl;
		}
		else if ((dir == 'd' || dir == 'r') && t->current->right != NULL) //'d' or 'r' - go to the right branch if it's not empty!
		{
			t->current = t->current->right;
			cout << t->current->value << endl;
		}
		else       //Let's hope no forbidden button's been pressed ^^. If there's no element in that branch let's make user aware of that.
			cout << "No more elements!" << endl;
		dir = getchar();
	}
}

int main()
{
	/*Just an example*/
	char c;
    tree tree1;
	initialize(&tree1);
	addValue(&tree1, 10);
	addValue(&tree1, 6);
	addValue(&tree1, 14);
	addValue(&tree1, 5);
	addValue(&tree1, 8);
	addValue(&tree1, 11);
	addValue(&tree1, 18);
	addValue(&tree1, 12);
	addValue(&tree1, 7);
	addValue(&tree1, 121);
	addValue(&tree1, 2);
	addValue(&tree1, 13);
	addValue(&tree1, 11);
	print(&tree1);
	getchar();
}

 

3 odpowiedzi

+3 głosów
odpowiedź 26 lutego 2018 przez Patrycjerz Mędrzec (192,320 p.)

Kod wygląda całkiem OK. Takie uwagi na szybko:

  1. Po co używasz typedef dla struktur? Ten trik był potrzebny w C, aby zlikwidować konieczność używania słowa struct przy każdym odniesieniu do typu. Ty przecież pracujesz w C++, a z kolei ciągle używasz dopisku struct we wszystkich deklaracjach funkcji, więc ten zapis jest bezużyteczny.
  2. Po co ci pole current w strukturze tree? Takie robocze zmienne powinny się znajdować jedynie wewnątrz funkcji. Tak w ogóle chyba zapominasz zresetować tego wskaźnika w funkcji print.
  3. Nazwy typów zaczynaj od dużej litery. Taka niepisana konwencja, a ułatwia odróżnienie typu od nazwy obiektu.
2
komentarz 26 lutego 2018 przez JAKUBW Nałogowiec (33,470 p.)
Konwencja konwencja, to dlaczego natywne klasy i metody C++ te z namespace std są nazywane z małej litery?
komentarz 26 lutego 2018 przez Patrycjerz Mędrzec (192,320 p.)
Tak jak mówiłem, wszystko zależy od konwencji. Twórcy C++ zastosowali wyróżnik w postaci przestrzeni std, zaś większość programistów używa nazw typów pisanych dużą literą. Wszystko ma sens, jeśli spełnia swoje zadanie, w tej sytuacji wyróżniające.
komentarz 26 lutego 2018 przez Kurczak Użytkownik (940 p.)

@Patrycjerz,

1. Takie nawyki z C :(

2.Ta zmienna znacznie ułatwiła mi pisanie funkcji, bez niej ciężko mi było w ogóle ugryźć temat. Dopiszę jeszcze kilka funkcji jak usuwanie drzewa, elementów ... a następnie zrefaktoryzuję kod i postaram się to naprawić. Racja, powinienem dodać zerowanie.

3.Konwencję znam, aczkolwiek jeszcze musi "wejść w krew"


Dzięki za wszystkie uwagi!

+3 głosów
odpowiedź 26 lutego 2018 przez mokrowski Mędrzec (156,220 p.)
Dodam jeszcze:

1. Za długie ciało addValue(...). Nie załatwiaj komentarzem czegoś co możesz napisać jawnie (np. 75-82 dlaczego nie zrobisz metody: initialNode(...)).

2. Dalej masz "poszukiwania dobrego miejsca" do wstawienia. Po co to robić w addValue(..) kiedy powinna od tego być odpowiednia funkcja?

3. Wiem że wyświetlenie na konsolę często wygląda paskudnie w kodzie (pomieszanie napisów, znaków oraz logiki), niemniej jednak i tu da się coś zrobić by było czytelne.

4. Lepiej stosować nullptr niż NULL.

5. 45-50 i podobnie niżej ... nie lepiej funkcja insertToRight(...) ?

6. Zamiast testu: t->current->left != NULL   lepiej   t->current->left czy zamiast: t->root == NULL lepiej: ! t->root  (dlatego radziłem nullptr zamiast NULL)

7. Ogólnie... nie lepiej w funkcjach przekazywać referencję jako argument? Lepiej będzie czytać i pisać kod bez ciągłego -> i nie będziesz publikować wewnętrznej implementacji struktury drzewa dla kogoś kto będzie tego używał.
komentarz 26 lutego 2018 przez Kurczak Użytkownik (940 p.)
1,2,5.Ok, long story short - powinienem rozbić program na więcej funkcji, dobrze rozumiem?
3.Średnio rozumiem w czym jest błąd, możesz sprecyzować?
4.Dzięki za radę, czemu jednak nullptr jest lepsze od NULL'a?
6.Już wiem ^^
7.Jak czytałem poradniki, to wszędzie korzystali ze wskaźników, myślałem, że coś w tym może być. Postaram się poprawić :).
+1 głos
odpowiedź 26 lutego 2018 przez Sic Dyskutant (8,510 p.)
edycja 26 lutego 2018 przez Sic

Dla samego siebie analizowałem twój kod i mam pytania do kilku rzeczy:

1.

typedef struct node   //pretty obvious part
{
...
} node;

a) Dlaczego użyłeś na sam koniec nazwy struktury ?

 

2.

typedef struct node
{
    node *right;
}

a) tego po prostu nie rozumiem wskaźnik struktury w strukturze ??

3.

t->root->value = value;
t->root->left = NULL;  
t->root->right = NULL;

a) obiekt struktury tree 'root' wskazuje na value ? (nie rozumiem)

b) "t->root" jest jako jedność i to wskazuje na kolejny obiekt ?

1
komentarz 26 lutego 2018 przez Kurczak Użytkownik (940 p.)
edycja 26 lutego 2018 przez Kurczak

1. Nie jestem w stanie odpowiedzieć na to pytanie blush Jak pisałem w C listę powiązaną, na końcu użyłem nazwy nodeS, żeby nie pisać ciągle struct node... Tutaj myślę, że to jest zbedne.
2.Tak, o ile się nie mylę jest to coś a la referencja w funkcjach :) Węzeł (node) wyobrażam sobie jako pudełko z 2 sznurkami (lewym i prawym). W pudełku mam moje dane, a wskaźniki to sznurki, które łączę z innymi węzłami, więc nie mogą być np. typu int, bo nie łączę ich z integerem, tylko z innym węzłem.
3.
a)
Na początku obiekt struktury tree 'root' wskazuje na puste miejsce w pamięci, później "tworzę pudełko" i w nim mogę wskazać na zawartość lub na sznurki, które odchodzą od niego i "wskazują" następne pudełeczka.
b)
Chyba nie bardzo rozumiem pytania :(

Jeśli masz jakiekolwiek wątpliwości, napisz jeszcze raz, bo wiem, że ciężko zrozumieć czyjś kod, a chyba jeszcze trudniej przenieść własne myśli na "papier".

komentarz 26 lutego 2018 przez Sic Dyskutant (8,510 p.)
Dzięki za odpowiedź, również na 3. b), ponieważ wytłumaczyłeś to słowami "Na początku obiekt struktury tree 'root' wskazuje ...".

Zresztą postaram sobie poradzić sam dzięki za pomoc.
komentarz 27 lutego 2018 przez Kurczak Użytkownik (940 p.)

Od siebie mogę polecić ten poradnik: LINK
Co prawda jest to lista, w C, ale jak dla mnie najbardziej obrazowe podejście ze wszystkich poradników, dzięki niemu załapałem listę i samemu wykombinowałem drzewo binarne :)

Podobne pytania

0 głosów
1 odpowiedź 956 wizyt
0 głosów
0 odpowiedzi 595 wizyt
pytanie zadane 19 stycznia 2019 w C i C++ przez profsor500 Użytkownik (610 p.)
0 głosów
2 odpowiedzi 281 wizyt
pytanie zadane 3 czerwca 2018 w C i C++ przez Roman1212 Początkujący (460 p.)

92,698 zapytań

141,613 odpowiedzi

320,143 komentarzy

62,058 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...