Avatar billede blackoak Nybegynder
10. januar 2011 - 20:53 Der er 7 kommentarer og
1 løsning

3 Binær Træ problemer

Hej, jeg sidder og bakser med et Binært Træ, og der er et par af metoderne jeg ikke kan få på plads syntaksialt/metodemæssigt.

public class TestBinaryTree {

public static void main(String[] args) {
  BinaryTree<String> t = new BinaryTree<String>();
  t.addRoot                                        ("A");
  Position<String> left2    = t.insertLeft    (t.root(), "B");
  Position<String> right3 = t.insertRight (t.root(), "C");
  Position<String> left4    = t.insertLeft (left2        , "D");
  Position<String> right5 = t.insertRight(left2      , "E");
  Position<String> left6    = t.insertLeftright3        , "F");
  Position<String> right7 = t.insertRight(right3    , "G");
       
Her er de 3 spørgsmål jeg forsøger at få metoderne på plads til.

        System.out.println("Udskriver elementerne og antallet af deres børn:");
        // toDo;

        System.out.println("Udskriver elementerne i alle blade:");
        // toDo;

        System.out.println("Sletter Roden og erstatter med et Blad der slettes.");
        // toDo
  }
}

Metoderne bør vel være i min BinaryTree klasse, eller kan de fuldtud laves her?

PS: Jeg arbejder med java i Eclipse(Helios)
Avatar billede arne_v Ekspert
10. januar 2011 - 20:58 #1
De to foerste spoergsmaal synes jeg meget ligger op til en rekursiv loesning.

Den tredie bliver bare noget snasket kode.
Avatar billede blackoak Nybegynder
10. januar 2011 - 21:04 #2
Enhver form for kode vil være en stor hjælp, jeg er kørt totalt fast og er endt i flere loops hvor Eclipse foreslår at skifte fra den ene type, for så at foreslå den anden, etc.

Selv snask kan gå an ;)
Avatar billede arne_v Ekspert
10. januar 2011 - 21:10 #3
Jeg vil ikke lave din opgave, men jeg kan godt lave et eksempel som illustrerer nogle teknikker du kan bruge.
Avatar billede blackoak Nybegynder
10. januar 2011 - 21:26 #4
Jeps, men det er jo lidt teknikkerne der p.t. volder problemer.

Har prøvet med tiltag som f.eks

System.out.println("Udskriver elementerne og antallet af deres børn:");
  Iterator<String> i1 = t.elements();
  while (i1.hasNext()) {
    System.out.print(i1.next() + "(" + "antallet af børn?" + ") ");
  }

System.out.println("Udskriver elementerne i alle blade:");
  Iterator<String> i2 = t.elements();
  while (i2.hasNext()) {
    if (t.isExternal(null) == true ) {
    System.out.print(i2.next() + " ");
    }
  }

System.out.println("Sletter Roden og erstatter med et Leaf der slettes.");
System.out.println();
t.hasLeft(v)replace(t.root(), "F");
t.remove(left6);

Men fyr bare, alt kan bruges
Avatar billede japping Nybegynder
10. januar 2011 - 22:56 #5
Her har du et input der bør give dig inspiration til løsning af opgaven:http://en.wikipedia.org/wiki/Tree_traversal

Tæller kan nemt implementeres.
Avatar billede arne_v Ekspert
10. januar 2011 - 23:15 #6
Du skal bruge rekursion.

Et eksempel som viser lidt:

import java.io.PrintStream;

public class TreeNode<T extends Comparable<T>> {
    private T value;
    public TreeNode<T> left;
    public TreeNode<T> right;
    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    public T getValue() {
        return value;
    }
    public TreeNode<T> getLeft() {
        return left;
    }
    public TreeNode<T> getRight() {
        return right;
    }
    public void insert(T value) {
        int comp = value.compareTo(this.value);
        if(comp < 0) {
            if(left == null) {
                left = new TreeNode<T>(value);
            } else {
                left.insert(value);
            }
        } else if(comp > 0) {
            if(right == null) {
                right = new TreeNode<T>(value);
            } else {
                right.insert(value);
            }
        } else {
            throw new IllegalArgumentException("Value already in tree: " + value);
        }
    }
    public int count() {
        int res = 1;
        if(left != null) {
            res += left.count();
        }
        if(right != null) {
            res += right.count();
        }
        return res;
    }
    public void dump(String indent, PrintStream ps) {
        ps.println(indent + value + "(" + count() + ")");
        if(left != null) {
            left.dump(indent + "  ", ps);
        }
        if(right != null) {
            right.dump(indent + "  ", ps);
        }
    }
    public void dump(PrintStream ps) {
        dump("", ps);
    }
    public static void main(String[] args) {
        TreeNode<String> tree = new TreeNode<String>("F");
        tree.insert("B");
        tree.insert("A");
        tree.insert("C");
        tree.insert("H");
        tree.insert("J");
        tree.insert("G");
        tree.insert("D");
        tree.insert("E");
        tree.insert("I");
        tree.dump(System.out);
    }
}
Avatar billede blackoak Nybegynder
11. januar 2011 - 16:55 #7
hej arne_v
Takker for hjælpen, det var en bonus med den intressante insert algoritme.

jeg ændrede din count metode så den passer til mit ønskede output;
// tæl antallet af børn
public int countChildren() {
  int amount = 0;
  if (left != null) {
  amount ++;
  }
  if (right != null) {
  amount ++;
  }
  return amount;
}

har stadig lidt bøvl med at finde blade, og udskrive deres element, prøver med disse at se om jeg kan bygge en metode der virker...

public boolean isExternal(Position<E> v) {
return !isInternal(v);
}

public boolean isInternal(Position<E> v) {
return hasLeft(v) || hasRight(v);
}

Anyways din post var til stor hjælp, og at skifte root element (ikke node) ud med et blads element er nemt nok ;)

smid et svar så får du points
Avatar billede arne_v Ekspert
11. januar 2011 - 18:12 #8
svar
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester