ugrás a tartalomhoz

Kiegyensúlyozott-e az adott bináris fa

morocztamas · 2012. Feb. 22. (Sze), 16.50
Egy bináris fáról, hogyan tudom megállapítani, hogy kiegyensúlyozott-e és aztán azzá tenni?
Eddig a forrás ilyen:
package binfa;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Binfa {
  public static void main(String[] args) throws FileNotFoundException {
    RendezettBinfa rbf2 = new RendezettBinfa();
    Scanner s = null;
    try {
      s = new Scanner (
              new BufferedReader (
                      new FileReader ("szamok.txt")));
      while (s.hasNextInt()) {
        rbf2.addElem(s.nextInt());
      }
    } finally {
      if (s != null) {
        s.close();
      }
    }
    System.out.println(rbf2.inorder());
    System.out.print("Magassága: ");
    System.out.println(rbf2.height());
    System.out.println();

    /**/
    
    RendezettBinfa rbf = new RendezettBinfa();
    rbf.addElem(4);
    rbf.addElem(2);
    rbf.addElem(1);
    rbf.addElem(3);
    rbf.addElem(6);
    rbf.addElem(5);
    rbf.addElem(7);
    System.out.println(rbf); // inorder eljárás, mert a gyökér a bal- és a jobbrészfa kiírása között van 
    System.out.print("Inorder: ");
    System.out.println(rbf.inorder());
    System.out.print("Postorder: ");
    System.out.println(rbf.postorder());
    System.out.print("Magassága: ");
    System.out.println(rbf.height());
    System.out.print("Preorder: ");
    System.out.println(rbf.preorder());
    
    /*
    Csucs cs = new Csucs(5);
    Csucs bcs = new Csucs(6);
    Csucs jcs = new Csucs(7);
    cs.addLeft(bcs);
    cs.addRight(jcs);
    System.out.println(cs); // *.toString
    cs.setElem(1);
    cs.bcs.setElem(2);
    jcs.setElem(3);
    System.out.println(cs);
    // System.out.println(jcs);
    */
  }
}
package binfa;

public class Csucs {
  protected int elem;
  Csucs bcs, jcs;
  
  public Csucs (int elem) {
    this.elem = elem;
    bcs = null;
    jcs = null;
  }
  
  public void addLeft (Csucs cs) {
    bcs = new Csucs(cs.getElem());
  }
  
  public void addRight (Csucs cs) {
    jcs = new Csucs(cs.getElem());
  }
  
  @Override
  public String toString () {
    String s = "" + elem;
    if (bcs != null) {
      s += ", " + bcs.toString();
    }
    if (jcs != null) {
      s += ", " + jcs.toString();
    }
    return s;
  }
  
  public void setElem (int elem) {
    this.elem = elem;
  }
  
  public int getElem () {
    return elem;
  }
}
package binfa;

public class RendezettBinfa {
  Csucs gy;
  RendezettBinfa balFa, jobbFa;
  
  public RendezettBinfa () {
    gy = null;
    balFa = null;
    jobbFa = null;
  }
  
  public void addElem (int elem) {
    if (gy == null) {
      gy = new Csucs(elem);
    } else if (gy.getElem() >= elem) {
      if (balFa == null) {
        balFa = new RendezettBinfa();
      }
      balFa.addElem(elem);
    } else {
      if (jobbFa == null) {
        jobbFa = new RendezettBinfa();
      }
      jobbFa.addElem(elem);
    }
  }
  
  public int height () {
    if (balFa == null && jobbFa == null) {
      return 0;
    } else if (balFa == null) {
      return jobbFa.height() + 1;
    } else if (jobbFa == null) {
      return balFa.height() + 1;
    } else {
      int b = balFa.height(), j = jobbFa.height();
      return (b < j ? j : b) + 1;
    }
  }
  
  public String preorder () {
    String s = "";
    if (gy != null) {
      s += gy.getElem() + ", ";
      if (balFa != null) {
        s += balFa.preorder(); // Mint a faktoriális függvénynél. n! = (n - 1)! * n
      }
      if (jobbFa != null) {
        s += jobbFa.preorder();
      }
    }
    return s;
  }
  
  public String inorder () {
    String s = "";
    if (balFa != null) {
      s += balFa.inorder();
    }
    if (gy != null) {
      s += gy.getElem() + ", ";
    }
    if (jobbFa != null) {
      s += jobbFa.inorder();
    }
    return s;
  }
  
  public String postorder () {
    String s = "";
    if (balFa != null) {
      s += balFa.postorder();
    }
    if (jobbFa != null) {
      s += jobbFa.postorder();
    }
    if (gy != null) {
      s += gy.getElem() + ", ";
    }
    return s;
  }
  
  @Override
  public String toString () { // Inorder
    String s = "";
    if (balFa != null) {
      s += balFa.toString();
    }
    if (gy != null) {
      s += gy.getElem() + ", ";
    }
    if (jobbFa != null) {
      s += jobbFa.toString();
    }
    return s;
  }
}
 
1

How to determine if binary

Poetro · 2012. Feb. 22. (Sze), 17.23
2

Fura, nincs java

inf3rno · 2012. Feb. 22. (Sze), 18.26
Fura, nincs java kódszínezőnk? Nálam nem működik... :S
3

Úgy tűnik. A multkor én is

kuka · 2012. Feb. 23. (Cs), 10.24
Úgy tűnik. A multkor én is JavaScript színezést kértem a Java kódhoz. Kipróbáltam, a fentebbi kód is jól mutat JavaScript színezéssel. Lehet ez az a kivétel amelyik erősíti a Java!=JavaScript szabályt.
4

Átszíneztem js-re, elmegy,

inf3rno · 2012. Feb. 23. (Cs), 18.54
Átszíneztem js-re, elmegy, jobb, mint a semmi...
Egyébként valszeg azért hasonló, mert ugyanazok a foglalt szavak...