1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:

package avl_tree_5;

public class AVLNode {

    // ////////////////////////////////
    //
    // ** Attribute **
    //
    // ////////////////////////////////

    private Object key, value;

    private AVLNode left, right, parent;

    // ////////////////////////////////
    //
    // ** Konstruktoren **
    //
    // ////////////////////////////////

    public AVLNode(Object key) throws Exception {
  this(key, key);
    }

    public AVLNode(Object key, Object value) throws Exception {
  if (key == null)
      throw new Exception("Uebergebener Parameter Key ist NULL!");
  if (value == null)
      throw new Exception("Uebergebener Parameter Value ist NULL!");

  this.key = key;
  this.value = value;
  this.setLeft(null);
  this.setRight(null);
    }

    // ////////////////////////////////
    //
    // ** Klassenbezogene Methoden **
    //
    // ////////////////////////////////

    public boolean isLeaf() {
  return (this.left == null && this.right == null);
    }

    public int compareTo(AVLNode n) {
  return ((Comparable) this.key).compareTo(n.getKey());
    }

    public String toString() {
  String s = "";

  // // für unterschiedlichen key/value
  // s += "(";
  // s += this.key.toString();
  // s += "|";
  // s += this.value.toString();
  // s += ")";

  s += "(" + this.key.toString() + ")";

  return s;
    }

    // ////////////////////////////////
    //
    // ** Getter / Setter **
    //
    // ////////////////////////////////

    public void setLeft(AVLNode n) throws Exception {
  this.left = n;
    }

    public void setRight(AVLNode n) throws Exception {
  this.right = n;
    }

    public Object getKey() {
  return key;
    }

    public Object getValue() {
  return value;
    }

    public AVLNode getLeft() {
  return left;
    }

    public AVLNode getRight() {
  return right;
    }

    public AVLNode getParent() {
  return parent;
    }

    public void setParent(AVLNode parent) {
  this.parent = parent;
    }

    // public Object[] getHilfe() { // nur hilfe zum debuggen!
    // Object[] arr = new Object[4];
    // arr[0] = this.toString();
    // arr[1] = this.getLeft();
    // arr[2] = this.getRight();
    // arr[3] = this.getParent();
    // return arr;
    // }
    
    public void hilfe() { // nur hilfe zum debuggen!
  
  System.out.println("---");
  System.out.println("GetHilfe: ");
  System.out.print(this.toString());
  System.out.print(" ; left: " + this.getLeft());
  System.out.print(" ; right: " + this.getRight());
  System.out.print(" ; parent: " + this.getParent());
  System.out.println("---");

    }

}                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
524:
525:
526:
527:
528:
529:
530:
531:
532:
533:
534:
535:
536:
537:
538:
539:
540:
541:
542:
543:
544:
545:
546:
547:
548:
549:
550:
551:
552:
553:
554:
555:
556:
557:
558:
559:
560:
561:
562:
563:
564:
565:
566:
567:
568:
569:
570:
571:
572:
573:
574:
575:
576:
577:
578:
579:
580:
581:
582:
583:
584:
585:
586:
587:
588:
589:
590:
591:
592:
593:
594:
595:
596:
597:
598:
599:
600:
601:
602:
603:
604:
605:
606:
607:
608:
609:
610:
611:
612:
613:
614:
615:
616:
617:
618:
619:
620:
621:
622:
623:
624:
625:
626:
627:
628:
629:
630:
631:
632:
633:
634:
635:
636:
637:
638:
639:
640:
641:
642:
643:
644:
645:
646:
647:
648:
649:
650:
651:
652:
653:
654:
655:
656:
657:
658:
659:
660:
661:
662:
663:
664:
665:

package avl_tree_5;

import java.awt.print.Printable;
import java.util.Stack;

public class AVLTree {

    // ////////////////////////////////
    //
    // ** Attribute **
    //
    // ////////////////////////////////

    public AVLNode root; // private UMAENDERN!! nur zu testzwecken

    public AVLNode nodeIt; // Node-Iterator

    private boolean found; // gefunden-boolean

    private int heigthCounter;

    private boolean avlNature;

    // ////////////////////////////////
    //
    // ** Konstruktoren **
    //
    // ////////////////////////////////

    public AVLTree() {
  root = null;
    }

    // ////////////////////////////////
    //
    // ** Klassenbezogene Methoden **
    //
    // ////////////////////////////////

    boolean debugMode = false;

    protected void debugMsg(String message) {
  if (debugMode) // boolean ob halt ausgabe ein oder aus is
      System.out.println(this.getClass() + ": " + message);
    }

    public void add(Object key) throws Exception {

  System.out.println("\n -> Mache add(" + key + ")");

  AVLNode n = new AVLNode(key);

  if (isEmpty()) {
      root = n;
  } else {

      if (key.getClass() != root.getKey().getClass())
    throw new Exception("der Key des neuen Objekts hat andere "
      + "Klasse als die anderen Keys im Baum");

      findKey(key);

      if (n.compareTo(nodeIt) < 1)
    nodeIt.setLeft(n);
      else
    nodeIt.setRight(n);

      n.setParent(nodeIt);

      // -- ab hier die rebalancierung --

      System.out.println("\n -> Mache Baum Rebalancieren");
      rebalance(n);
      System.out.println("\n -> Baum erfolgreich rebalanciert");

      // ------------------------------
  }
  ausgabe2();
    }

    public void rebalanceAll() throws Exception { // NUR EINE TESTMETHODE!!!
  rebalanceAll(root);
    }

    public void rebalanceAll(AVLNode n) throws Exception {
  if (n.getLeft() != null)
      rebalance(n.getLeft());
  if (n.getRight() != null)
      rebalance(n.getRight());
  rebalance(n);
    }

    public void rebalance(AVLNode n) throws Exception {

           // das hier isn anderer versuch, kann man uebergucken, der funktioniert genau so wenig
  // int leftHeight = getHeigthNode(n.getLeft());
  // int rightHeight = getHeigthNode(n.getRight());
  // int difference = Math.abs(leftHeight - rightHeight);
  //  
  // if(difference > 1)
  // {
  // if(leftHeight > rightHeight)
  // {
  // if(getHeigthNode(n.getLeft().getLeft()) <
  // getHeigthNode(n.getLeft().getRight()))
  // {
  // AVLNode temp = n.getLeft().getRight();
  // System.out.println("Double rotate left right");
  // rol(n.getLeft());
  // ror(n);
  // return temp;
  // }
  // else
  // {
  // AVLNode temp = n.getLeft();
  // System.out.println("Single rotate right");
  // ror(n);
  // return temp;
  // }
  // }
  //    
  // else if(leftHeight < rightHeight)
  // {
  // if(getHeigthNode(n.getRight().getRight()) <
  // getHeigthNode(n.getRight().getLeft()))
  // {
  // AVLNode temp = n.getRight().getLeft();
  // System.out.println("Double rotate right left");
  // ror(n.getRight());
  // rol(n);
  // return temp;
  // }
  // else
  // {
  // AVLNode temp = n.getRight();
  // System.out.println("Single rotate left");
  // rol(n);
  // return temp;
  // }
  // }
  // }
  // return n;

  try {
      AVLNode gf = n.getParent().getParent(); // gf = grandFather von n
      if (!isAVLNode(gf)) { // wenn n nicht AVL -> rebalance

    if (gf.getLeft() != null) {
        if (gf.getLeft().getLeft() == n) // 1.fall LL
      ror(findKeyNode(gf.getKey()));
        else if (gf.getLeft().getRight() == n) // 2.fall LR
      doppelRor(findKeyNode(gf.getKey()));
    }

    if (gf.getRight() != null) {
        if (gf.getRight().getLeft() == n) // 3.fall RL
      doppelRol(findKeyNode(gf.getKey()));
        else if (gf.getRight().getRight() == n) // 4. fall RR
      rol(findKeyNode(gf.getKey()));
    }

      }

      if (n.getParent() != null) // n.vater rebalancen
    rebalance(n.getParent());

  } catch (Exception e) {
      System.out.println(e);
      System.out.println("fertig mit rebalance");
      // throw (e);
  }

    }

    public boolean isEmpty() {
  return (this.root == null);
    }

    // ////////////////////////////////
    // Suchen-Methoden
    // ////////////////////////////////

    // gibt nur zurueck ob key gefunden wird
    public boolean findKey(Object key) throws Exception {

  // kann nur nach gleichen key-objekten suchen wie schon im baum
  if (key.getClass() != root.getKey().getClass())
      throw new Exception("der Key des gesuchten Objekts hat andere "
        + "Klasse als die anderen Keys im Baum");

  AVLNode seekedNode = new AVLNode(key);
  found = false;
  nodeIt = null;
  return (findKey(root, seekedNode));
    }

    // 
    public AVLNode findKeyNode(Object key) throws Exception {
  if (findKey(key))
      return nodeIt;
  else
      return null;
    }

    private boolean findKey(AVLNode n, AVLNode seekedNode) {

  if (seekedNode.compareTo(n) == 0) {
      found = true; // wenn knoten gefunden ist nodeIt dieser
      nodeIt = n; // wenn am blatt angekommen, ist knoten sicher nicht im
      // baum, nodeIt ist dann der vaterknoten des neuen
  } else if (n.isLeaf()) {
      nodeIt = n;
  } else {
      if (seekedNode.compareTo(n) < 1) {
    if (n.getLeft() == null)
        nodeIt = n;
    else
        findKey(n.getLeft(), seekedNode);
      } else { // seekedNode.compareTo(n) > 1
    if (n.getRight() == null)
        nodeIt = n;
    else
        findKey(n.getRight(), seekedNode);
      }
  }
  return found;
    }

    // ////////////////////////////////
    // GetHeight-Methoden
    // ////////////////////////////////

    public int getHeigthTree() { // Gibt die Baumhoehe = maximaler Weg root-leaf
  // zurueck [OK]
  return (getHeigthNode(getRoot()));
    }

    public int getHeigthNode(AVLNode n) { // Gibt die Hoehe = maximaler Weg
  // n-leaf
  // zurueck [OK]
  if (n == null) // steht hier weil wenn in Node Klasse:
      return -1; // Wird mit AVLNode.getHeight drauf zugegriffen,
  else { // wenn der aber null is dann null.getHeigth() -> Error
      heigthCounter = 0;
      getHeigth(n, 0);
      return heigthCounter;
  }
    }

    private void getHeigth(AVLNode n, int heigth) {
  if (heigth > heigthCounter)
      heigthCounter = heigth;

  if (n.getLeft() != null)
      getHeigth(n.getLeft(), heigth + 1);
  if (n.getRight() != null)
      getHeigth(n.getRight(), heigth + 1);
    }

    // ////////////////////////////////
    // AVL-Eigenschaft-Methoden
    // ////////////////////////////////

    public boolean isAVLTree() { // ob der Baum AVL Eigenschaft hat
  if (!isEmpty()) {
      avlNature = true;
      isAVL(root);
      return avlNature;
  } else
      return true;

    }

    private void isAVL(AVLNode n) {
  if (!isAVLNode(n))
      avlNature = false;
  else {
      if (n.getLeft() != null)
    isAVL(n.getLeft());
      if (n.getRight() != null)
    isAVL(n.getRight());
  }
    }

    public boolean isAVLNode(AVLNode n) { // ob ein Knoten AVL Eigenschaft hat
  int a = getHeigthNode(n.getLeft());
  int b = getHeigthNode(n.getRight());

  if (a == b)
      return true;
  else if (a + 1 == b || a == b + 1)
      return true;
  else
      return false;
    }

    // Direkte syso Ausgabe in inorder (=sortiert)
    public void toStringDirectOut() {
  System.out.println("");
  toStringDirectOut(root);
    }

    private void toStringDirectOut(AVLNode n) {
  if (n.getLeft() != null)
      toStringDirectOut(n.getLeft());
  System.out.println(n.toString() + " Vater: " + n.getParent()); // das
  // +vater
  // kann
  // weg
  if (n.getRight() != null)
      toStringDirectOut(n.getRight());
    }

    // ////////////////////////////////
    // Rotate-Methoden
    // ////////////////////////////////

    public AVLNode rol(AVLNode n) throws Exception {

  System.out.println("\n -> Mache rol(" + n + ")");

  // wichtig, sonst geht kein ROL!
  if (n == null)
      throw new Exception(n + " ist null -> kein ROL möglich!");
  if (n.getRight() == null)
      throw new Exception(n + " hat kein RightChild -> kein ROL möglich!");

  boolean nIsLeftChild;

  AVLNode grandParent = n.getParent();
  AVLNode kind = n.getRight();
  AVLNode innererEnkel = kind.getLeft();

  if (grandParent != null) {
      if (grandParent.getLeft() == n) // n is linkes kind
    nIsLeftChild = true;
      else
    // n is rechtes kind
    nIsLeftChild = false;
  }

  n.setParent(kind);
  n.setRight(innererEnkel);

  kind.setLeft(n);
  kind.setParent(null);

  if (innererEnkel != null)
      innererEnkel.setParent(n);

  // betrachten ob n einen Vater hat:
  if (grandParent != null) {

      kind.setParent(grandParent);

      if (grandParent.getLeft() == n) // n is linkes kind
    grandParent.setLeft(kind);
      else
    // n is rechtes kind
    grandParent.setRight(kind);

  }

  // System.out.println("root vorher: " + root);

  // root neu bestimmen:
  AVLNode it = n;
  while (it.getParent() != null)
      it = it.getParent();
  root = it;

  // System.out.println("root nachher: " + root);

  ausgabe2();

  return kind; // oder return n !?!??!??!?!??! WICHTIG
    }

    public AVLNode ror(AVLNode n) throws Exception {

  System.out.println("\n -> Mache ror(" + n + ")");

  // wichtig, sonst geht kein ROL!
  if (n == null)
      throw new Exception(n + " ist null -> kein ROR möglich!");
  if (n.getLeft() == null)
      throw new Exception(n + " hat kein LeftChild -> kein ROR möglich!");

  boolean nIsLeftChild;

  AVLNode grandParent = n.getParent();
  AVLNode kind = n.getLeft();
  AVLNode innererEnkel = kind.getRight();

  if (grandParent != null) {
      if (grandParent.getRight() == n) // n is linkes kind
    nIsLeftChild = true;
      else
    // n is rechtes kind
    nIsLeftChild = false;
  }

  n.setParent(kind);
  n.setLeft(innererEnkel);

  kind.setRight(n);
  kind.setParent(null);

  if (innererEnkel != null)
      innererEnkel.setParent(n);

  // betrachten ob n einen Vater hat:
  if (grandParent != null) {

      kind.setParent(grandParent);

      if (grandParent.getRight() == n) // n is linkes kind
    grandParent.setRight(kind);
      else
    // n is rechtes kind
    grandParent.setLeft(kind);

  }

  // System.out.println("root vorher: " + root);

  // root neu bestimmen:
  AVLNode it = n;
  while (it.getParent() != null)
      it = it.getParent();
  root = it;

  // System.out.println("root nachher: " + root);

  ausgabe2();

  return kind; // oder return n !?!??!??!?!??! WICHTIG
    }

    public void doppelRor(AVLNode n) throws Exception {
  System.out.println("\n -> Mache doppelRor(" + n + ")");
  try {
      AVLNode temp = n.getLeft();
      rol(temp);
      ror(n);
      System.out.println("\n -> doppelRor erfolgreich");
  } catch (Exception e) {
      System.out.println("\n -> " + e);
      System.out.println("\n -> doppelRor klappte nicht");
  }
  ausgabe2();
    }

    public void doppelRol(AVLNode n) throws Exception {
  System.out.println("\n -> Mache doppelRol(" + n + ")");
  try {
      AVLNode temp = n.getRight();
      ror(temp);
      rol(n);
      System.out.println("\n -> doppelRol erfolgreich");
  } catch (Exception e) {
      System.out.println("\n -> " + e);
      System.out.println("\n -> doppelRol klappte nicht");
  }
  ausgabe2();
    }

    public void getHilfeTree() {
  getHilfeTree(root);
    }

    private void getHilfeTree(AVLNode n) {
  n.hilfe();
  System.out.println(n + " is AVL: " + isAVLNode(n));
  if (n.getLeft() != null)
      getHilfeTree(n.getLeft());
  if (n.getRight() != null)
      getHilfeTree(n.getRight());
    }

    // ////////////////////////////////
    // Ausgabe-Methode (Matrix)
    // ////////////////////////////////

    private String[][] arr;
    private int hoch;
    private String leerFeld = "       ";

    public void ausgabe2() {

  System.out.println("\n==== Ausgabe2: Hierarchisch ====");

  // Wenn Baum leer = Hoehe -1
  if (isEmpty()) // wenn Baum leer = Hoehe -1
      System.out.println("\n    null");

  // Wenn Baum nur root = Hoehe 0
  else if (root.getLeft() == null && root.getRight() == null)
      System.out.println("\n    " + root);

  // Wenn Baum nur 2-3 Elemente = Hoehe 1
  else if (getHeigthTree() == 1) {

      arr = new String[3][3];

      for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        arr[i][j] = leerFeld;
    }
      }

      arr[0][1] = root.toString();
      if (root.getLeft() != null && root.getRight() != null) {
    arr[1][1] = "--+--";
    arr[2][0] = "" + root.getLeft();
    arr[1][0] = "  .--";
    arr[2][2] = "" + root.getRight();
    arr[1][2] = "--.  ";
      } else {
    if (root.getLeft() != null) {
        arr[1][1] = "--+  ";
        arr[2][0] = "" + root.getLeft();
        arr[1][0] = "  .--";
    } else { // = (root.getRight() != null)
        arr[1][1] = "  +--";
        arr[2][2] = "" + root.getRight();
        arr[1][2] = "--.  ";
    }

      }

      for (int i = 0; i < 3; i++) { // tatsaechliche ausgabe
    System.out.print("\n    ");
    for (int j = 0; j < 3; j++) {
        System.out.print(arr[i][j]);
    }
      }
      System.out.println("");

      // Wenn Baum nur mehr als 3 Elemente = Hoehe 2(+)
  } else {

      // Array initialisieren
      int tiefe = this.getHeigthTree();
      int breit = (int) (Math.pow(2, (tiefe + 1))) - 1;
      hoch = (2 * tiefe) + 1;
      arr = new String[hoch][breit];

      for (int i = 0; i < hoch; i++) {
    for (int j = 0; j < breit; j++) {
        arr[i][j] = leerFeld;
    }
      }

      // -------- xwert initialisieren ---------
      arr[0][(breit / 2)] = root.toString();

      arr[1][breit / 2] = "  +  ";

      if (root.getLeft() != null)
    xwert(root.getLeft(), (breit / 2), ((int) Math.pow(2,
      getHeigthNode(root))), 1, 0);
      if (root.getRight() != null)
    xwert(root.getRight(), (breit / 2), ((int) Math.pow(2,
      getHeigthNode(root))), 2, 0);
      // ---------------------------------------

      // ------- leere Spalten wegstreichen ----
      int ersteBeschriebeneSpalte = 0;
      boolean boo = false;
      ; // false wenn unbeschrieben
      for (int i = 0; i < breit; i++) {
    for (int j = 0; j < hoch; j++) {
        if (arr[j][i] != leerFeld)
      boo = true;
    }
    if (!boo)
        ersteBeschriebeneSpalte++;
      }
      // ---------------------------------------

      for (int i = 0; i < hoch; i++) { // tatsaechliche ausgabe
    System.out.print("\n    ");
    for (int j = ersteBeschriebeneSpalte; j < breit; j++) {
        System.out.print(arr[i][j]);
    }
      }
      System.out.println("");

  }

  System.out.print("\n======== / Ausgabe2 ==========\n");

    }

    // die special funktion:
    // vater is der xwert von weiter oben,
    // richtung: 1=von rechts, 2=von links
    // nullig: ob das null is un dann weiter null nach unten geben soll
    //
    // system: kindsknoten ist um +/- (potenzDesVaters/2) verschoben
    private void xwert(AVLNode thisNode, int vater, int potenz, int richtung,
      int ywert) {

  int ergebnis;

  if (richtung == 1)
      ergebnis = (vater - (potenz / 2));
  else
      ergebnis = (vater + (potenz / 2));

  // wenn thisNode von rechts angesprochen wird
  if (richtung == 1) {
      arr[(ywert + 1)][ergebnis] = "   .---";

      // solange bis du auf was anderes als leerFeld kommst
      int ii = ergebnis;
      while (arr[(ywert + 1)][ii + 1] == leerFeld) {
    ii++;
    arr[(ywert + 1)][ii] = "------";
      }
      // wenn thisNode von links angesprochen wird
  } else {
      arr[(ywert + 1)][ergebnis] = "---.  ";
      int ii = ergebnis;
      while (arr[(ywert + 1)][ii - 1] == leerFeld) {
    ii--;
    arr[(ywert + 1)][ii] = "------";
      }

  }

  arr[(ywert + 2)][ergebnis] = "" + thisNode; // ausgabe von thisNode

  // fuegt das + unter thisNode ein
  if (thisNode.getLeft() != null && thisNode.getRight() != null)
      arr[(ywert + 3)][ergebnis] = "--+--";
  else if (thisNode.getLeft() != null)
      arr[(ywert + 3)][ergebnis] = "--+  ";
  else if (thisNode.getRight() != null)
      arr[(ywert + 3)][ergebnis] = "  +--";

  // rekursiv mit den Kindsknoten weiter wenn vorhanden
  if (thisNode.getLeft() != null)
      xwert(thisNode.getLeft(), ergebnis, (potenz / 2), 1, (ywert + 2));
  if (thisNode.getRight() != null)
      xwert(thisNode.getRight(), ergebnis, (potenz / 2), 2, (ywert + 2));

    }

    // ////////////////////////////////
    //
    // ** Getter / Setter **
    //
    // ////////////////////////////////

    public AVLNode getRoot() {
  return this.root;
    }

    public static void main(String[] args) throws Exception {
  AVLTreeTest.main(args);
    }

}