Kako obrisati listove u binarnom stablu

Kako obrisati listove u binarnom stablu 28.12.2005. u 23:40 · pre 254 meseca #1

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.

Re: Kako obrisati listove u binarnom stablu 29.12.2005. u 10:11 · pre 254 meseca #2

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);
}

Re: Kako obrisati listove u binarnom stablu 29.12.2005. u 11:15 · pre 254 meseca #3

Citat:

tiranin: 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);
}

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;
            }
}

Re: Kako obrisati listove u binarnom stablu 29.12.2005. u 11:16 · pre 254 meseca #4

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;
}

Re: Kako obrisati listove u binarnom stablu 29.12.2005. u 13:52 · pre 254 meseca #5

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

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;
}

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

Forum kao aplikacija na telefonu

Srodne teme