BinärBäume ohne innere Klasse

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

BinärBäume ohne innere Klasse
Hey ich schreibe bald AuD für MT
und mir ist bei euren Altklausuren aufgefallen, dass ihr bei der Datenstruktur
binäre Bäume immer ohne innere Klassen arbeitet. Das verwirrt mich ziemlich.
Ich verstehe nicht wie man ohne root vorgehn soll?
Kann mir das jemand erklären. Z.b wenn ich hier eine Methode nach unserer Art habe:

public boolean isBST(){
			if(root==null){
				return true;
			}
			
			return isBSThelp(root);
			
		}
		private boolean isBSThelp(Node<E> n){
			
			if(n.left!=null){
				if(n.left.value.compareTo(n.value)>0||!isBSThelp(n.left)){
					return false;
				}
				
				
				
				}
			if(n.right!=null){
				if(n.right.value.compareTo(n.value)<0||!isBSThelp(n.right)){
					return false;
				}
			}
			
			return true;
		}

Das ist mit innere Klasse da ist mir alles klar.

3

Ich habe mal auf die Schnelle einen Baum ohne eine innere Klasse implementiert, vielleicht wird es dadurch für dich klarer. Im Prinzip ist “this”, also die aktuell der Methode isSearchTree() übergebene Instanz die Wurzel des aktuellen Teilbaums. Die Wurzel des Gesamtbaums kann irgendwo in der Klasse gespeichert sein, wo der Main-Testfall ist, in diesem Fall ist die Wurzel das Node g in der Main-Methode.

[code=java]public class Node<E extends Comparable> {

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

public Node(E value, Node<E> left, Node<E> right){
	this.value = value;
	this.left = left;
	this.right = right;
}

public boolean isSearchTree(){
	if(this.left == null){
		if(this.right == null){
			return true;
		} else {
			return		  this.value.compareTo(this.right.value) < 0
					&&	this.right.isSearchTree();
		}
	} else if(this.right == null){
		return		  this.value.compareTo(this.left.value) > 0
				&&	this.left.isSearchTree();
	} else {
		return		  this.value.compareTo(this.left.value) > 0
				&&	this.value.compareTo(this.right.value) < 0
				&&	this.right.isSearchTree()
				&&	this.left.isSearchTree();
	}
}

public static void main(String[] args){
	Node<Integer> a = new Node<Integer>(1, null, null);
	Node<Integer> b = new Node<Integer>(3, null, null);
	Node<Integer> c = new Node<Integer>(5, null, null);
	Node<Integer> d = new Node<Integer>(7, null, null);
	Node<Integer> e = new Node<Integer>(2, a, b);
	Node<Integer> f = new Node<Integer>(6, c, d);
	Node<Integer> g = new Node<Integer>(4, e, f);
	System.out.println(g.isSearchTree());
}

}[/code]