drzewo binarne - liczenie elementów

Odpowiedz Nowy wątek
2015-01-25 02:27
0

Witam, jest to pewnie dość proste pytanie ale trochę już nad tym siedziałem i nie mogę sobie na nie odpowiedzieć. Chcę sobie poćwiczyć różne operacje na drzewie binarnym i zacząłem od prostej funkcji liczącej ilość elementów w drzewie. Zrobiłem to tak:

struct tree{
int x;
tree l;
tree
p;
};

int ile (tree *root)
{
int licz = 0;
if (root == NULL) return licz;
else
{
licz = 1;
if (root->l != NULL) licz = licz + wid(root->l);
if (root->p != NULL) licz = licz + wid(root->p);
}

return licz;

}

int main(int argc, char** argv) {
int w;

root = new tree;
root->x = 5;

root->l = new tree;
root->l->x = 3;

root->p = new tree;
root->p->x = 10;    

root->l->l = new tree;
root->l->l->x = 20; 

root->l->p = new tree;
root->l->p->x = 21;

root->p->l = new tree;
root->p->l->x = 1;

w = ile(root);
cout << "ile = " << w;

return 0;

}

W kompilacji żaden błąd nie wyskakuje. Po prostu program przestaje działać. Podejrzewam, że źle działa warunek z NULL i program próbuje działać w nieskończoność tylko nie wiem dlaczego. Czy ktoś może zna odpowiedź?

Pozostało 580 znaków

2015-01-25 02:32
1

Co to znaczy przestaje działać? Wywala się?
Poza tym wklej cały kod (między znacznikami <code class="cpp"></code>). Co to za funkcja wid()? A root w main skąd się bierze?

Pozostało 580 znaków

2015-01-25 03:35
0
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

struct tree{
    int x;
    tree *l;
    tree *p;
};
tree *root;

int ile (tree *root)
{
    int licz = 0;
    if (root == NULL) return licz;
    else
    {
        licz = 1;
    if (root->l != NULL) licz = licz + ile(root->l);
    if (root->p != NULL) licz = licz + ile(root->p);
    }
    return licz;
}

int main(int argc, char** argv) {
    int w;

    root = new tree;
        root->x = 5;
    root->l = NULL;
    root->p = NULL;

    root->l = new tree;
    root->l->x = 3;

    root->p = new tree;
    root->p->x = 10;    

    root->l->l = new tree;
    root->l->l->x = 20; 

    root->l->p = new tree;
    root->l->p->x = 21;

    root->p->l = new tree;
    root->p->l->x = 1;

    w = ile (root);
    cout << "w = " << w;

    return 0;
}

Dobra, wkleiłem cały kod. Tak, przestaje działać czyli się wywala. Funkcja wid(), to była nazwa robocza funkcji ile(), jak wklejałem tutaj kod to zmieniłem nazwę z "wid" na "ile" żeby było trochę jaśniej. Root jest zadeklarowane globalnie, tak jak widać powyżej, za pierwszym razem zapomniałem to przekleić.

edytowany 1x, ostatnio: master62, 2015-01-25 03:41

Pozostało 580 znaków

2015-01-25 09:44

Brakuje ci instrukcji 'zamykających' drzewo.

root = new tree;
        root->x = 5;
    root->l = NULL;
    root->p = NULL;

    root->l = new tree;
    root->l->x = 3;

    root->p = new tree;
    root->p->x = 10;
    root->p->p = NULL;//<---

    root->l->l = new tree;
    root->l->l->x = 20;
    root->l->l->l = NULL;//<---
    root->l->l->p = NULL;//<---

    root->l->p = new tree;
    root->l->p->x = 21;
    root->l->p->l = NULL;//<---
    root->l->p->p = NULL;//<---

    root->p->l = new tree;
    root->p->l->x = 1;
    root->p->l->l = NULL;//<---
    root->p->l->p = NULL;//<--- 

Teraz powinno być dobrze.

Pozostało 580 znaków

2015-01-25 10:12
2
unsigned int countLeaves(tree* node)
{
  if (node == NULL) {
    return 0;
  }

 return 1 + countLeaves(node->l) + countLeaves(node->r);
}

Tak prościej :P


edytowany 2x, ostatnio: Patryk27, 2015-01-25 10:14

Pozostało 580 znaków

2015-01-25 21:11
0

Rekman, wielkie dzięki za pomoc, wszystko działa i mogę teraz normalnie ćwiczyć.

Patryk27, tak było na początku tylko zacząłem rozwijać żeby znaleźć błąd ale też dzięki za sugestie. :)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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