Drzewa BST java

Question

Witam mam napisac program który implementuje drzewa BST jednakże jest to zadanie na studia więc jest z góry narzucona struktura kodu mianowicie 

public abstract class BinaryTreeNode {
    
    //wartosc w wezle
    protected int dane;
    //prawe i lewe poddrzewo
    protected BinaryTreeNode lewy, prawy;

    public BinaryTreeNode(int dane) {
        this.dane = dane;
    }
    
/* Wypisuje drzewo np. dla drzewa
        8
    3       5
 2    1  4    0 
 wypisac:
        2
     3
        1
  8
        4
     5
        0
wypisz lewe
wypisz odstep, wypisz dane, endl
wypisz prawe
 */
    public abstract void print(int poziom);
       
  
//rekurencyjne przeszukuje drzewo BST, zwraca true, jesli znajdzie element o podanej wartosci   
    public abstract boolean searchBSTRec(int szukany);
    
//rekurencyjnie dodaje element do drzewa BST
    public abstract void addBSTRec(int nowy);
    
//zwraca pare: wezel zawierajacy poszukiwany element oraz jego poprzednika
//jesli szukanego elementu nie ma w drzewie, to pierwszym elementem pary jest null
//jesli pierwszy element pary jest korzeniem (nie ma poprzednika), to drugim elementem pary jest null    
    public abstract Pair < BinaryTreeNode, BinaryTreeNode > searchBST(int szukany);    
    
 
}

i mam napisac metode która doda mi element do drzewa naskrobałem tyle i zatrzymałem się bo nie wiem kiedy mam dodawać na prawą strone drzewa a kiedy na lewą 

o oto co napisałem sam 

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package drzewabst;

/**
 *
 * @author Patryk
 */
public class Lab8 extends BinaryTreeNode{

    private Lab8 korzen = null;
    
    public Lab8(int dane) {
        super(dane);
  
    }

    @Override
    public void addBSTRec(int nowy) {
      if(korzen == null){
          korzen = new Lab8(nowy);
      }
// tu nie wiem kiedy dodawać na prawą strone drzewa a kiedy na lewa 
    }


    
}

może mi ktoś pomóc naprowadzić ?

Answer 1

Drzewo BST działa tak że na lewo masz dane mniejsze od korzenia a na prawo masz dane wieksze. W twoim wypadku najlepiej porównywać nowy z dane a nastepnie sprawdzac czy lewy/prawy jest nullem. Jak tak to tworzysz jak nie rekurencyjnie wywołujesz dodanie.

Comments

 @Override
    public void addBSTRec(int nowy) {
        Lab8 pom = null;
        if(this.korzen == null){
            this.korzen = new Lab8(nowy);
            this.korzen.lewy = null;
            this.korzen.prawy = null;
        }else{
            pom = new Lab8(nowy);
            if(pom.dane < this.korzen.dane){
                this.korzen.lewy = new Lab8(nowy);
            }else{
                this.korzen.prawy = new Lab8(nowy);
            }
            
        }
        
     }

o to chodziło ?

 

---

Nie do końca. Popierwsze po co tworzysz pom jeśli potem i tak tworzysz nowe Lab8.

To o co mi chodziło to raczej powinno wygladać tak.

else{
           
            if(nowe < this.korzen.dane){
               if(korzen.lewy==null) this.korzen.lewy = new Lab8(nowy);
               else korzen.lewy.addBSTRec(nowy);
            }else{
               if(korzen.prawy==null) this.korzen.prawy = new Lab8(nowy);
               else korzen.prawy.addBSTRec(nowy);
            }
             
        }

 

---

dzięki kolego naprowadziłeś mnie, jednakże mam teraz kolejny problem mam to wypisać w taki sposób

* Wypisuje drzewo np. dla drzewa
        8
    3       5
 2    1  4    0
 wypisac:
        2
     3
        1
  8
        4
     5
        0
wypisz lewe
wypisz odstep, wypisz dane, endl
wypisz prawe
 */

jak uzyskać taki efekt ?

---

wypisz lewe
wypisz odstep, wypisz dane, endl
wypisz prawe :)

Rekurencyjnie wywołujesz

Coś w tym stylu. Tylko musisz pobawić się jakos z spacjami:)

void wypiszDane(){

if(lewy!=null)lewy.wypiszDane()

System.out.println(" " + dane);

if(prawy!=null) prawy,wypiszDane();

}

---

zrobiłem jak mi poradziłeś jednakże nie działa mi to dobrze

 @Override
    public void print(int poziom) {
      
       if(this.lewy != null)this.korzen.lewy.print(poziom); 
           System.out.print(this.korzen.lewy.dane + " ");
       
       
        if(this.prawy != null)this.korzen.prawy.print(poziom); 
            System.out.print(this.korzen.prawy.dane + " ");
        
       
      System.out.println();
       
    }


  @Override
    public void addBSTRec(int nowy) {
        if(this.korzen == null){
            this.korzen = new Lab8(nowy);
            this.korzen.lewy = null;
            this.korzen.prawy = null;
        }else{
            if(nowy < this.korzen.dane){
                if(this.korzen.lewy == null)this.korzen.lewy = new Lab8(nowy);
                else this.korzen.lewy.addBSTRec(nowy);
                this.print(this.korzen.lewy.dane);
            }else{
                if(this.korzen.prawy == null) this.korzen.prawy = new Lab8(nowy);
                else this.korzen.prawy.addBSTRec(nowy); 
                this.print(this.korzen.prawy.dane);
            }
        }
     
     }

 

---

Nie wiem dlaczego robisz printa w dodawaniu, mi wydaje się że jest to nie potrzebne. No ale jeśli chodzi o funkcie print to nei tak ją sobie wyobrażałem. Nie wypisujesz danych z korzenia tylko z dzieci. A dzieci powinny same sobie wypisywać dane, po ich rekurencyjnym wywołaniu.

---

to jak mam to niby wyświetlać ?

---

@Override
   public void print(int poziom) {
      
      if(this.lewy != null)this.korzen.lewy.print(poziom+1);        
      for(int n =0; n<poziom; n++) System.out.print(" ");
      System.out.println(dane);
      if(this.prawy != null)this.korzen.prawy.print(poziom+1);      
   }
 

Ja bym to jakoś tak zrobił. 

A wyświetlanie drzewa zaczynasz od korzenia na którym wykonujesz print(0)

---

wybacz kolego faktycznie xd

---

A jak jest?