Problem początkującego z binarnym drzewem...

chcę wygenerować drzewo:

public class Binarytree {
	private static Node root;
	public static String data;

	public Binarytree(String data) {
		root = new Node(data);
	}

	public void add(Node parent, Node child, String orientation) {
		if (orientation.equals("l")) {
			parent.setLeft(child);
		} else {
			parent.setRight(child);
		}
	}

	public static void main(String args[]) {
		Node n1 = new Node("a");
		Node n2 = new Node("b");
		Node n3 = new Node("c");
		Node n4 = new Node("d");

		Binarytree tree = new Binarytree("e");
		tree.add(root, n1, "l");
		tree.add(root, n2, "r");
		tree.add(n2, n3, "l");
		tree.add(n2, n4, "r");
	}
}

class Node {
	private String key;
	private Node l;
	private Node r;

	Node(String string) {
		this.key = string;
		r = null;
		l = null;
	}

	public void setKey(String key) {
		this.key = key;
	}

	public String getKey() {
		return key;
	}

	public void setLeft(Node l) {
		this.l = l;
	}

	public Node getLeft() {
		return l;
	}

	public void setRight(Node r) {
		this.r = r;
	}

	public Node getRight() {
		return r;
	}

}

tylko teraz nie wiem jak je wyświetlić? :P

Później będę miała jeszcze mesę innych problemów:
mam później odczytać i wyświetlić powstałe słowa typu "dbe"...

mam do tego użyć rekurencji...
niestety dopiero zaczynam... i nie wiem jak to ugryźć

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Iteratorami

package pl.bv;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

public class BST<E extends Comparable<? super E>> implements Iterable<E> {

    private Node<E> root;

    @Override
    public Iterator<E> iterator() {

        return new InOrderIterator();
    }

    public Iterator<E> preorderIterator() {

        return new PreorderIterator();
    }

    private static class Node<E> {

        private E value;
        private Node<E> left;
        private Node<E> right;

        public Node(E value) {

            this.value = value;
        }
    }

    private class InOrderIterator implements Iterator<E> {

        private final LinkedList<Node<E>> stack;

        private InOrderIterator() {

            stack = new LinkedList<>();

            Node<E> current = root;

            while (current != null) {
                stack.push(current);
                current = current.left;
            }
        }

        @Override
        public boolean hasNext() {

            return !stack.isEmpty();
        }

        @Override
        public E next() {

            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            Node<E> current = stack.pop();
            final E value = current.value;

            current = current.right;
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            return value;
        }
    }

    private class PreorderIterator implements Iterator<E> {

        private final LinkedList<Node<E>> stack;

        private PreorderIterator() {

            stack = new LinkedList<>();
            final Node<E> current = BST.this.root;
            if (current != null) {
                stack.push(current);
            }
        }

        @Override
        public boolean hasNext() {

            return !stack.isEmpty();
        }

        @Override
        public E next() {

            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            final Node<E> current = stack.pop();
            final E value = current.value;

            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }

            return value;
        }
    }
}

udało mi się wykodzić coś takiego:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

class Instrukcje {
	String pozycja;
	String wartosc;

	public Instrukcje(String pozycja, String wartosc) {
		this.pozycja = pozycja;
		this.wartosc = wartosc;
	}
}

public class Main {
	static String korzen = "";
	static ZawartoscDrzewa<String> drzewo = new ZawartoscDrzewa<>(korzen);
	static List<Instrukcje> Instrukcje = new ArrayList<>();
	static int i = 0;
	static String wartosc[] = new String[2];
	static char tmp = 'a';

	public static void main(String[] args) {
		Scanner scan = null;
		ArrayList<String> liniaPliku = new ArrayList<String>();

		try {
//			scan = new Scanner(new File("tree.txt")); 
			scan = new Scanner(new File("drzewo.txt")); // możesz sobie wybać plik
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}

		while (scan.hasNextLine())
			liniaPliku.add(scan.nextLine()); // skanujemy plik i linijki dodajemy do listy w celu dalszej obróbki

		for (i = 0; i < liniaPliku.size(); i++)
			if (liniaPliku.get(i).length() > 1) {
				wartosc = liniaPliku.get(i).split(" ");
				Instrukcje.add(new Instrukcje(wartosc[0].toLowerCase(), wartosc[1].toLowerCase())); // Aby nie zwracało
																									// uwagi na wielkość
																									// liter w pliku
			} else
				korzen = liniaPliku.get(i); // znajdujemy korzeń

		budujDrzewo(drzewo, Instrukcje); // budujemy drzewo

		ArrayList<String> najstarszy = new ArrayList<String>();
		najstarszy.addAll(budujWyrazy(drzewo)); // tworzymy listę wyrazów, aby znalezć najstarszy wyraz
		if (najstarszy.size() > 1)
			Collections.sort(najstarszy); // posortuje jeśli znalazło więcej wyrazów na tą samą literę
									// - w ramach optymalizacji nie sortujemy zawsze,
									// a żeby nie komplikować kodu - sprawdzać kolejnych liści szybciej będzie
									// posortować wynik (w końcu to raczej pojedyncze przypadki)
//			for (i=0;i<najstarszy.size();i++)
//				System.out.println(najstarszy.get(i) + korzen); 
		System.out.println(najstarszy.get(najstarszy.size()-1) + korzen); 
	}

	private static List<String> budujWyrazy(ZawartoscDrzewa<String> pozycjaStartowa) {
		List<String> slowa = new ArrayList<>();
		char najstarsze;
		if (pozycjaStartowa.getLewa() != null)
			slowa.addAll(budujWyrazy(pozycjaStartowa.getLewa())); // rekurencyjnie budujemy wyrazy z lewej strony

		if (pozycjaStartowa.getPrawa() != null)
			slowa.addAll(budujWyrazy(pozycjaStartowa.getPrawa())); // rekurencyjnie budujemy wyrazy z prawej strony

		if (slowa.isEmpty()) {
			najstarsze = pozycjaStartowa.getWartosc().charAt(0);
	//		if (tmp <= najstarsze) { // sprawdza czy ostatni liść jest największy
				tmp = najstarsze;
				slowa.add(pozycjaStartowa.getWartosc()); // buduje słowa tylko z najwyżej znalezionych wartości
		//	}
		} else
			slowa = slowa.stream().map(s -> s + pozycjaStartowa.getWartosc()).collect(Collectors.toList());
		return slowa;
	}

	private static void budujDrzewo(ZawartoscDrzewa<String> pozycja, List<Instrukcje> Instrukcje) { // rekurencyjnie
																									// budujemy drzewo
		List<Instrukcje> lewa = Instrukcje.stream().filter(i -> i.pozycja.startsWith("l")).collect(Collectors.toList());
		List<Instrukcje> prawa = Instrukcje.stream().filter(i -> i.pozycja.startsWith("r"))
				.collect(Collectors.toList()); // odczytujemy instrukcje...

		Instrukcje lewoStart = lewa.stream().filter(i -> i.pozycja.length() == 1).findFirst().orElse(null);
		Instrukcje prawoStart = prawa.stream().filter(i -> i.pozycja.length() == 1).findFirst().orElse(null);

		if (lewoStart != null) {
			pozycja.setLewa(new ZawartoscDrzewa<String>(lewoStart.wartosc));
			List<Instrukcje> zLewej = lewa.stream().map(i -> new Instrukcje(i.pozycja.substring(1), i.wartosc))
					.collect(Collectors.toList());
			budujDrzewo(pozycja.getLewa(), zLewej);
		}

		if (prawoStart != null) {
			pozycja.setPrawa(new ZawartoscDrzewa<String>(prawoStart.wartosc));
			List<Instrukcje> zPrawej = prawa.stream().map(i -> new Instrukcje(i.pozycja.substring(1), i.wartosc))
					.collect(Collectors.toList());
			budujDrzewo(pozycja.getPrawa(), zPrawej);

		}

	}
}

ZawartoscDrzewa:

public class ZawartoscDrzewa<String> {
    private final String wartosc;
    private ZawartoscDrzewa<String> lewa;
    private ZawartoscDrzewa<String> prawa;

    public ZawartoscDrzewa(String wartosc) {
        this.wartosc = wartosc;
    }

    public String getWartosc() {
        return wartosc;
    }

    public ZawartoscDrzewa<String> getLewa() {
        return lewa;
    }

    public void setLewa(ZawartoscDrzewa<String> lewa) {
        this.lewa = lewa;
    }

    public ZawartoscDrzewa<String> getPrawa() {
        return prawa;
    }

    public void setPrawa(ZawartoscDrzewa<String> prawa) {
        this.prawa = prawa;
    }
}

Ale wykładowca stwierdził, że nie przechodzi mu 60% testów i gubi elementy - tam gdzie powinien zbudowac wyraz 17 literowy, buduje 14 np...
Jak go zapytałam o możliwosc podesłania pliku gdzie mu źle cos wygenerowało źle stwierdził, że mam sama rozkminić, on nic nie udostępnia - to wynik jego AI i tyle...
to, że w drzewie nie dodaje korzenia wiem i nie wiem jak to obejść (dodaję korzeń ręcznie przy wypisywaniu danych)...

Ogólnie ćwiczenie jest takie by zbudować drzewo z określonego pliku gdzie są instrukcje typu
r t
l s
b
rr o
rl e
czyli: instrukcje (r - prawo, l - lewo [spacja] etykieta)
b jest korzeniem.

i wyświetlić słowo, które jest ostatnie w alfabecie.
Pliku drzewa nie musimy walidować - możemy przyjąć, że jest na pewno poprawne.

hmmm nadal mam 90% testów - nie przechodzi dla wartości powyżej 1000 elementów... dodatkowo mam pozbyć się streamów...
jak można inaczej zapisać:

		List<Instrukcje> lewa = Instrukcje.stream().filter(i -> i.pozycja.startsWith("l")).collect(Collectors.toList());

aby nie używać stream?

@noobek101:

Wygląda na to, że ty nie implementujesz drzewa binarnego tylko imitujesz jego strukturę jakimiś listami. Po co Ci to? Drzewo składa się z węzłów i węzły posiadają komplet informacji potrzebnych do poruszania się po nich jak po drzewie binarnym. Nie widzę treści zadania, ale jak rozumiem w każdej linijce jest zapisana ścieżka dojścia (za pomocą "l" i "r") do węzła w którym ma się znaleźć wartość ostatnia w linijce. Zakładam, że skoro nie musimy badać poprawności danych, to że w każdym węźle znajdzie sie jakaś literka.

Tak naprawdę potrzebujesz wyłącznie stworzyć obiekty węzłów, żadne listy nie są Ci potrzebne. Widzę, że zapis w pliku jest dowolny, drzewo jest tworzone "nie po kolei". Ok to nie jest problem - musisz po prostu przy przechodzeniu po scieżce "lrlrlrlrr" sprawdzić, czy już masz węzeł, jeśli nie to go utworzyć.

Jeżeli te słowa to są słowa które powstają przez przejście od roota do liścia to tez nie potrzebujesz budowac listy słów i jej sortować - idziesz po drzewie sprawdzajac co jest pozniej w alfabecie lewy czy prawy wezeł.

Ma to sens co napisałem, czy coś źle zrozumiałem? Wydaje mi się, że znacznie prościej można to napisać, niż To co wkleiłaś, nawet nie chce mi ię tego analizować, sorry :D

p.s.
Ofkz jak uwzględnisz ww. to streamy same znikną, nie będzie miejsca w którym by były potrzebne.

        List<String> slowa = new ArrayList<>();
        char najstarsze;
        if (pozycjaStartowa.getLewa() != null)
            slowa.addAll

To Ci spowalnia (i inne wywołania addAll na ArrayListach). addAll pewnie dodaje po jednym w pętli, a operacja dodawania w ArrayList ma kwadratową złożoność. Użyj LinkedList, która ma stałą złożoność dla add, a po zakończeniu budowy drzewa czy dodawania wielu węzłów utwórz ArrayList z tej listy, żeby mieć szybszy dostęp.

Po drugie zgadzam się z przedmówcą, że niepotrzebnie budujesz klasę drzewa i na niej operujesz. Starczy węzeł.

@LoneWanderer: skąd wniosek, że ArrayList.addAll ma o(n^2) ?

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking)
z https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html