/********************************************************************************************
**   erstellt von ...
**
**   Autor: Thomas Meyer   Homepage: www.all-community.de
**
**   nicht für Firmen oder kommerzielle Nutzung, keine unerlaubte Weitergabe, kein Verkauf
**
**   © 2002, 2003, 2004 Thomas Meyer - Copyright Hinweis nicht entfernen!
**
*********************************************************************************************/

Klasse Tree:

Implementierung des Binärbaums

function Tree() { // constructor

  this.constructor = Tree;
  this.key = new Key();
  this.left = null;
  this.right = null;
  this.info = new Info();
  this.empty = empty
  this.search = search;
  this.insert = insert;

};

function insert(key, info) {

  if (this.empty()) {
    this.key.setKey(key);
    this.info.setInfo(info);
  } else if (this.key.compare(key) > 0) {
    if (this.right == null) {
      this.right = new Tree();
      this.right.insert(key, info);
    } else {
      this.right.insert(key, info);
    };
  } else if (this.key.compare(key) == 0) {
      this.info.setInfo(info);
  } else {
    if (this.left == null) {
      this.left = new Tree();
      this.left.insert(key, info);
    } else {
      this.left.insert(key, info);
    };
  };

};

function search(key) {

  if (this.empty()) {
    return null;
  } else if (this.key.compare(key) == 0) {
    return this.info;
  } else if (this.key.compare(key) > 0) {
    if (this.right != null) {
      return this.right.search(key);
    };
  } else {
    if (this.left != null) {
      return this.left.search(key);
    };
  };

  return null;

};

function empty() {

  if (this.key.getKey() == null) { return true; }
  else { return false; };

};

Klasse Key:

Diese Klasse repräsentiert den Schlüssel eines Knotens. Schlüssel haben folgende Eigenschaften:
1. ein Schlüssel darf nicht nachträglich verändert werden, es sei denn, er ist leer
2. Schlüssel müssen miteinander verglichen werden können. Die Funktion zum Vergleichen der Schlüssel wird in der Klasse angegeben.
Der Vorteil dieser Implementierung ist: die Klasse "Key" ist austauschbar.

function Key(key) { // constructor

  this.constructor = Key;
  this.key = key;
  this.getKey = getKey;
  this.setKey = setKey;
  this.compare = compare;

};

function getKey() {

  return this.key;

};

function setKey(key) {

  if (this.key == null) {
    this.key = key;
    return true;
  } else {
    return false;
  }

};

function compare(other_key) {

  for (var i = 0; i < this.key.length; i++) {
     if (i > other_key.length) { return 1; break; }
     else if (this.key.charCodeAt(i) < other_key.charCodeAt(i)) { return -1; break; }
     else if (this.key.charCodeAt(i) > other_key.charCodeAt(i)) { return  1; break; }
     else { };
  };
  return 0;

};

Klasse Info:

Diese Klasse repräsentiert den Wert eines Knotens.

function Info(info) { // constructor

  this.constructor = Info;
  this.info = (info!=null) ? new Array(info) : new Array();
  this.getInfo = getInfo;
  this.setInfo = setInfo;
  this.contains = contains;
  // overwrites the native function "toString()"
  // "toString()" always automatically inherites from the "Object" - super-class !!!
  this.toString = infoToString;

};

function getInfo(i) {

  if (i != null && parseInt(i) != NaN && i < this.info.length) {
    return this.info[i];
  } else {
    return this.info;
  }

};

function setInfo(info) {

  if (! this.contains(info)) {
    this.info[this.info.length] = info;
    return true;
  } else {
    return false;
  }

};

function contains(info) {

  for (var i = 0; i < this.info.length; i++) {
    if (this.info[i] == info) { return true };
  };

  return false;

};

// As an default, "toString()" returns the String "[OBJECT]" for all reference types.
// If possible (and if it makes sense) each class should overwrite the original function
// to provide an String that has some more meaning ...
function infoToString() {

  // This is a recursive call of "toString()" for the underlying data-structure.
  // Doing so, we demand the underlying type to determine on itself, how to represent the content.
  // Sometimes this is a good idea - esp. when you don't know, which type your data actually belongs to.
  return (this.getInfo()).toString();

};

var myTree = new Tree();
myTree.insert("b", 1);
myTree.insert("b", 2);
myTree.insert("b", 3);
myTree.insert("a", "test");
myTree.insert("c", 5.5);

Beispiel:

var myTree = new Tree();
myTree.insert("b", 1);
myTree.insert("b", 2);
myTree.insert("b", 3);
myTree.insert("a", "test");
myTree.insert("c", 5.5);

var myInfo = myTree.search("c");
document.writeln(+myInfo);

Ausgabe:

myInfo = myTree.search("b");
document.writeln(+myInfo);

Ausgabe:

document.writeln(myInfo.getInfo(0));

Ausgabe:

// © 2002, 2003, 2004 Thomas Meyer www.All-Community.de
// Copyright Hinweis nicht entfernen!