Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Ahoj,
mohl by někdo říci co mám špatně (resp. proč to tak je) ve funkcích int soucetNerek(Node *p) a void print2Nerek(Node *p).
Zde je co to dělá (výpis a součet prvků rekurzivně je správně):
a zde je kod:
#include <iostream> #include <iomanip> #include <cstdlib> #include"stack.h" using namespace std; struct Node { int info; Node *left, *right; Node(int x, Node* l, Node* r) { info = x; left = l; right = r; } }; inline int random(int m) { // vysledkem je pseudonahodne cislo z intervalu 0 az m-1 return rand()%m; } Node *randTree(int depth) { if(depth<=0 || random(10)>7) return NULL; return new Node(random(100),randTree(depth-1), randTree(depth-1)); } //------------------------------------------------------------------------------ // vypíše ve tvaru stromu (hodnoty pod sebe) void print(Node *p, int s) { cout << setw(s) << ' '; if(p) { cout << p->info << endl; print(p->left, s+1); print(p->right, s+1); } else cout << "x" << endl; } //vypíše ve tvaru: hodnota uzlu(levý podstrom, pravý podstrom) - rekurzivně void print2(Node *p) { if(p) { cout << p->info << " (" ; print2(p->left); cout << ","; print2(p->right); cout << ")"; } else cout << "x"; } //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //vypíše ve tvaru: hodnota uzlu(levý podstrom, pravý podstrom) - nerekurzivně (s použitím zásobníku) struct Pair { Node *ptr; int spc; Pair(Node *p) { ptr = p; } }; void print2Nerek(Node *p) { Stack<Pair> stc; stc.push(Pair(p)); while(!stc.empty()) { Pair pair = stc.pop(); if(!pair.ptr) cout << "x" ; else if(pair.ptr) { cout << pair.ptr->info; cout << " ("; stc.push(Pair(pair.ptr->right)); cout << ","; stc.push(Pair(pair.ptr->left)); cout << ")"; } } } //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //sečte hodnoty všech uzlů - rekurivně int soucet(Node *p) { if(p) return p->info+soucet(p->left)+ soucet(p->right); else return 0; } //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //sečte hodnoty všech uzlů s použitím zásobníku - nerekurzivně (s použitím zásobníku) int soucetNerek(Node *p) { Stack<Node*> stc; int soucet = 0; stc.push(p); while(!stc.empty()) { Node *q = stc.pop(); if(q) { soucet+=q->info; stc.push(q->right); stc.push(q->left); soucet++; } } return soucet; } //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- int main() { Node *root = randTree(4); cout << "vypis (rekurzivne)" << endl; print2(root); cout << endl << endl; cout << "vypis (nerekurzivne)" << endl; print2Nerek(root); cout << endl << endl; //print(root, 1); cout << "soucet uzlu stromu (rekurzivne): " << soucet(root) << endl; cout << "soucet uzlu stromu (nerekurzivne): " << soucetNerek(root) << endl << endl; system("PAUSE"); return 0; }
Děkuji
Offline
Tak ta chyba u součtu je dost triviální: stačí umazat soucet++
Chyba u výpisu je horší, tam je špatně celá logika věci (vypisuješ "(,)" hned, když narazíš na ten uzel; je potřeba vypsat pouze "(" a uzel si držet v zásobníku, zpracovat jeho levý podstrom, vypsat ",", zpracovat pravý podstrom, vypsat ")" a pak teprve odstranit ze zásobníku.
Zkuším si to naprogramovat, pak třeba dodám kód.
Offline
Jo, děkuju.
Offline
Tak jsem si našel čas to doprgat:
struct Pair { Node *ptr; char spc; Pair(Node *p,char s) { ptr = p; spc = s; } }; void print2Nerek(Node *p) { stack<Pair> stc; stc.push(Pair(p,'l')); while(!stc.empty()) { Pair pair = stc.top(); if(!pair.ptr) { cout << "x" ; while(pair.spc=='r') { stc.pop(); pair=stc.top(); cout<<")"; } stc.pop(); if(!stc.empty())cout<<","; } else { cout << pair.ptr->info; cout << " ("; stc.push(Pair(pair.ptr->right,'r')); stc.push(Pair(pair.ptr->left,'l')); } } }
Použil jsem místo tvé vlastní stack.h již hotovou třídu stack dostupnou po #include<stack>, proto tam, kde já mám top (vrátí horní prvek bez odebrání) ty budeš mít nejdřív pop a pak push. Pokud ale nebyla součást zadání napsat si vlastní stack, doporučuju používat ten už hotový.
Kód se lépe čte, když pop dělá po každé to samé ;)
Offline
Děkuji.
Offline
Stránky: 1