/** * Binaerer Suchbaum, der int-Werte enthaelt */ public class BinTree { TreeNode root = null; /** * Defaultkonstruktor */ public BinTree() { } /** * Suchen eines Wertes. Falls x nicht vorhanden ist, wird null zurueckgegeben. * (rekursiv) * * @param x * @return Knoten mit gesuchtem Wert */ public TreeNode getNode(int x) { TreeNode node = this.root; return this.getNode(x, node); } /** * Sucht rekursive im uebergebenen Teilbaum nach einem Wert. Falls der Wert * gefunden wurde wird der entsprechende Knoten zurueckgegeben anonsten null. * * @param x * Zu suchender Wert. * @param node * Wurzel des zu pruefenden Teilbaums * @return Knoten mit dem gesuchten Wert oder null */ private TreeNode getNode(int x, TreeNode node) { if (node == null) { return null; } if (node.data == x) { return node; } if (x < node.data) { return this.getNode(x, node.left); } return this.getNode(x, node.right);// rechts suchen } /** * Sucht nach dem Wert x im Baum(iterativ) * * @param x * @return den Knoten, der den Wert x beinhaltet */ @SuppressWarnings("unused") private TreeNode getNode2(int x) { TreeNode node = this.root; while (node != null) { if (node.data == x) { break; } if (x < node.data) { node = node.left; } else { node = node.right; // rechts suchen } } return node; // nicht gefunden->null zurueckgeben } /** * Suchen des Elternknoten eines Wertes. Falls x nicht vorhanden ist oder in der * Wurzel steht, wird null zurueckgegeben.(rekursiv) * * @param x * @return vaterknoten des gesuchten Wertes */ public TreeNode getParentNode(int x) { TreeNode node = this.root; if (node.data == x) { return null; } return this.getParentNode(x, node); } /** * Gibt den Elternknoten des Knoten zurueck der den uebergebenen Wert enthaelt. * * @param x * Zu suchender Wert * @param node * Wurzelknoten des zu pruefenden Teilbaum * @return Elternknoten des Knotens mit dem gesuchten Wert oder aber null. */ private TreeNode getParentNode(int x, TreeNode node) { if ((x < node.data) && (node.left != null)) { // links suchen if (node.left.data == x) { return node; } return this.getParentNode(x, node.left); } else if ((x > node.data) && (node.right != null)) { // rechts suchen if (node.right.data == x) { return node; } return this.getParentNode(x, node.right); } return null; } /** * Suchen des Elternknoten eines Wertes. Falls x nicht vorhanden oder in der * Wurzel steht, wird null zurueckgegeben.(iterativ) * * @param x * @return Elternknoten oder null */ @SuppressWarnings("unused") private TreeNode getParentNode2(int x) { TreeNode node = this.root; while (node != null) { if (x < node.data) { // links suchen if ((node.left != null) && (node.left.data == x)) { return node; } node = node.left; } else { if ((node.right != null) && (node.right.data == x)) { return node; } node = node.right; // rechts suchen } } return node; // nicht gefunden->null zurueckgeben } /** * Fuegt den Wert n in den Baum ein * * @param n */ public void insert(int n) { if (this.root == null) { // Baum leer this.root = new TreeNode(null, null, n); return; } TreeNode node = this.root; this.insert(n, node); } /** * Fueget den uebergebenen Wert in den Baum ein. * * @throws ArithmeticException * wenn der Wert bereits im Baum enthalten ist. * @param n * Einzufuegender Wert * @param node * Wurzelknoten des zu bearbeitenden Teilbaums. */ public void insert(int n, TreeNode node) { if (node.data == n) { // Wert schon drin->Exception throw new ArithmeticException("Wert schon im Baum enthalten!"); //$NON-NLS-1$ } if (n < node.data) { if (node.left == null) { // links frei node.left = new TreeNode(null, null, n); return; } this.insert(n, node.left); } else { if (node.right == null) { // rechts frei node.right = new TreeNode(null, null, n); return; } this.insert(n, node.right); } } /** * Loescht den Knoten mit dem Wert n * * @param n */ public void remove(int n) { if (this.getNode(n) == null) { throw new ArithmeticException("Knoten gibt es nicht!"); //$NON-NLS-1$ } TreeNode node = this.root; while (node != null) { TreeNode parent = this.getParentNode(node.data); if (node.data == n) { // Node gefunden if ((node.left == null) && (node.right == null)) { // case 1 if (parent == null) { this.root = null; } else if (parent.left == node) { parent.left = null; } else { parent.right = null; } } else if ((node.left != null) && (node.right != null)) { // case 3 (two children) TreeNode childNode = node.right; // suche naechst groesseres Element while (childNode.left != null) { childNode = childNode.left; // nach links wie moeglich } // Merke mir wichtige Knoten // spaeter zum Tauschen TreeNode left = node.left; TreeNode right = node.right; TreeNode childParent = this.getParentNode(childNode.data); if (parent == null) { // falls Wurzel this.root = childNode; } else if (parent.left == node) { // ist linkes Kind parent.left = childNode; } else { // ist rechtes Kind parent.right = childNode; } childNode.left = left; // Linke Kinder an ChildNode haengen if (right != childNode) { // hatte unser childNode rechts noch Kinder? childParent.left = childNode.right; // rechte Kinder an ChildNode haengen childNode.right = right; } } else { // case 2 (one child) TreeNode childNode = (node.left != null) ? node.left : node.right; if (parent == null) { // falls Wurzel this.root = childNode; } else if (parent.left == node) { // linkes Kind parent.left = childNode; } else { // rechtes Kind parent.right = childNode; } } break; } if (n < node.data) { node = node.left; } else { node = node.right; } } } /** * Loeschen aller Daten */ public void clear() { this.root = null; } class TreeNode { int data; TreeNode left; TreeNode right; public TreeNode(TreeNode links, TreeNode rechts, int wert) { this.data = wert; this.left = links; this.right = rechts; } @Override public String toString() { String res = "knoten " + this.data; //$NON-NLS-1$ if (this.left != null) res += ", kinder " + this.left.data + ","; //$NON-NLS-1$ //$NON-NLS-2$ else res += ", kinder null,"; //$NON-NLS-1$ if (this.right != null) res += this.right.data; else res += "null"; //$NON-NLS-1$ return res; } } }