[es] - Kako obrisati listove u binarnom stablu

DiscoNinja
Pirot

Član broj: 56118
Poruke: 10
195.252.87.*

Profil

Kako obrisati listove u binarnom stablu

^{28.12.2005. u 22:40 - pre 222 meseci}

Dakle imam zadatak da obrisem listove u uredjenom binarnom stablu. Pisao sam neki kod ali mi ne funkcionise kako treba. Problem bi najverovatnije trebalo resavati rekurzivno ali sam se neshto pogubio u tome. Glavna glavobolja mi je sto bi se program, kada obrise neki list, izgubi i nezna kako da se vrati ;)
Evo dela koda:

public void deleteLeaves (){
deleteLeaves (root);
}

public void deleteLeaves(Cvor p){
Cvor prev = null;
while(p!=null){
prev = p;
if((p.left == null) && (p.right == null)) prev = null;
else if (p.left == null)
p = p.right;
else if (p.right == null)
p = p.left;
else ... ???

Ako neko ima ideju, pomagajte!

Za moderatora: Mozda ovo nije za pod "Java" ali ne znam gde bih drugde postavio ovu temu.

_{[Ovu poruku je menjao DiscoNinja dana 28.12.2005. u 23:44 GMT+1]}

Odgovor na temu

tiranin
Dorćol

Član broj: 37185
Poruke: 245
..taman-bg.customer.sbb.co.yu.

Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 09:11 - pre 222 meseci}

Na primer ovako

Code:
public void deleteLeaves (){
          deleteLeaves (root);
           root = null;
}
public void deleteLeaves(Cvor p){
            if((p.left == null) && (p.right == null))
                    return;
            if( p.left != null)
                       deleteLaves(p.left);
            if(p.right != null)
                     deleteLeaves(p.right);
}

Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.leased.neobee.net.

+1 Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 10:15 - pre 222 meseci}

Citat:

tiranin: Na primer ovako

Mislim da treba

Code:
public void deleteLeaves (){
          deleteLeaves (root);
           root = null;
}
public void deleteLeaves(Cvor p){
            if((p.left == null) & (p.right == null))
                    return;
            if( p.left != null) {
                       deleteLeaves(p.left);
                       p.left = null;
            }
            if(p.right != null) {
                     deleteLeaves(p.right);
                     p.right = null;
            }
}

Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541

+711 Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 10:16 - pre 222 meseci}

Citat:

tiranin: Na primer ovako

Koliko vidim, ovo ne briše listove, već samo uništava referencu na root.

Brisanje samo listova (čvorova koji nemaju dece) bi išlo otprilike ovako

Code:

public bool Brisi(cvor p) {
  if (p == null)
    return false;

  if (p.left == null && p.right == null)
    return true;

  if (Brisi(p.left))
    p.left = null;

  if (Brisi(p.right))
    p.right = null;

  return false;
}

_{[Ovu poruku je menjao jablan dana 29.12.2005. u 11:36 GMT+1]}

Odgovor na temu

DiscoNinja
Pirot

Član broj: 56118
Poruke: 10
195.252.87.*

Profil

Re: Kako obrisati listove u binarnom stablu

^{29.12.2005. u 12:52 - pre 222 meseci}

Citat:

jablan: Koliko vidim, ovo ne briše listove, već samo uništava referencu na root.

Brisanje samo listova (čvorova koji nemaju dece) bi išlo otprilike ovako

Upravo je to resenje! Hvala svima na trudu, a posebno jablanu na velikoj pomoci.
Pozdrav!

Odgovor na temu