Php
Version vom 23. Mai 2011, 13:58 Uhr von Pascal (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „= Einführung = = Installation & Konfiguration = = Sprace & Syntax = = Befehlsreferenz = = Sonstiges & Beispiele = == Bäume == <source lang="php"> <?php /* * Au…“)
Einführung
Installation & Konfiguration
Sprace & Syntax
Befehlsreferenz
Sonstiges & Beispiele
Bäume
<?php
/*
* Author: Pascal Briehl
* Ein simpler unbalancierter Baum.
*/
define("DEBUG",1);
class Node {
public $rChild = NULL;
public $lChild = NULL;
private $data = NULL;
function __construct($data) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "Node created<br>\n";
}
}
$this->data = $data;
}
function value() {
if (defined("DEBUG")) {
if (DEBUG >= 4) {
echo "value " . $this->data . "<br>\n";
}
}
return $this->data;
}
public function compareTo($o) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo $this->data . " compareTo $o<br>\n";
}
}
if ($this->data == $o) {
return 0;
} else if ($this->data < $o) {
return -1;
} else {
return 1;
}
}
}
class Tree {
private $root = NULL;
function __construct() {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "Tree created<br>\n";
}
}
}
public function insert($data) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "insert $data<br>\n";
}
echo "Wert ($data) wird eingefügt!<br>\n";
}
if ($this->root == NULL) {
$this->root =& new Node($data);
} else {
if ($this->root->compareTo($data) > 0) {
if ($this->root->rChild == NULL) {
$this->root->rChild =& new Node($data);
} else {
$this->ins(&$this->root->rChild,$data);
}
} else if ($this->root->compareTo($data) < 0) {
if ($this->root->lChild == NULL) {
$this->root->lChild =& new Node($data);
} else {
$this->ins(&$this->root->lChild,$data);
}
} else {
if (defined("DEBUG")) {
echo "Wert ($data) ist bereits im Baum enthalten!<br>\n";
}
}
}
}
private function ins(&$node,$data) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "ins $data<br>\n";
}
}
if ($node == NULL) {
$node =& new Node($data);
} else {
if ($node->compareTo($data) > 0) {
if ($node->rChild == NULL) {
$node->rChild =& new Node($data);
} else {
$this->ins(&$node->rChild,$data);
}
} else if ($node->compareTo($data) < 0) {
if ($node->lChild == NULL) {
$node->lChild =& new Node($data);
} else {
$this->ins(&$node->lChild,$data);
}
} else {
if (defined("DEBUG")) {
if (DEBUG >= 1) {
echo "Wert ($data) ist bereits im Baum enthalten!<br>\n";
}
}
}
}
}
private function ins_node(&$ins,&$node) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "ins_node " . $ins->value() . "<br>\n";
}
}
if ($node == NULL) {
$node =& $ins;
} else {
if ($node->compareTo($ins->value()) > 0) {
if ($node->rChild == NULL) {
$node->rChild =& $ins;
} else {
$this->ins_node(&$ins,&$node->rChild);
}
} else if ($node->compareTo($ins->value()) < 0) {
if ($node->lChild == NULL) {
$node->lChild =& $ins;
} else {
$this->ins_node(&$ins,&$node->lChild);
}
} else {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "Wert (" . $ins->value() . ") ist bereits im Baum enthalten!\n";
}
}
}
}
}
public function remove($data) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "remove $data<br>\n";
}
echo "Wert ($data) wird gelöscht!<br>\n";
}
if ($this->root->compareTo($data) == 0) {
if ($this->root->rChild != NULL) {
if ($this->root->lChild != NULL) {
$cache =& $this->root->lChild;
}
$this->root =& $this->root->rChild;
if ($cache != NULL) {
$this->ins_node(&$cache,$this->root);
}
} else {
$this->root =& $this->root->lChild;
}
} else {
$this->rem(&$this->root,$data);
}
}
private function rem(&$node,$data) {
if (defined("DEBUG")) {
if (DEBUG >= 2) {
echo "rem $data<br>\n";
}
}
if ($node->compareTo($data) > 0) {
if ($node->rChild != NULL) {
if ($node->rChild->compareTo($data) == 0) {
if ($node->rChild->rChild != NULL) {
if ($node->rChild->lChild != NULL) {
$cache =& $node->rChild->lChild;
}
$node->rChild =& $node->rChild->rChild;
if ($cache != NULL) {
$this->ins_node(&$cache,$this->root);
}
} else {
$node->rChild =& $node->rChild->lChild;
}
} else {
if ($node->rChild != NULL) {
$this->rem(&$node->rChild,$data);
}
}
}
} else if ($node->compareTo($data) < 0) {
if ($node->lChild != NULL) {
if ($node->lChild->compareTo($data) == 0) {
if ($node->lChild->rChild != NULL) {
if ($node->lChild->lChild != NULL) {
$cache =& $node->lChild->lChild;
}
$node->lChild =& $node->lChild->rChild;
if ($cache != NULL) {
$this->ins_node(&$cache,$this->root);
}
} else {
$node->lChild =& $node->lChild->lChild;
}
} else {
if ($node->lChild != NULL) {
$this->rem(&$node->lChild,$data);
}
}
}
}
}
public function toString() {
if (defined("DEBUG")) {
if (DEBUG >= 5) {
echo "toString";
}
}
if ($this->root->rChild != NULL) {
echo $this->getString($this->root->rChild);
}
if ($this->root != NULL) {
echo $this->root->value() . "<br>\n";
/*echo "root: ";
echo $this->root->value();
echo " , rChild: ";
echo ($this->root->rChild != NULL) ? $this->root->rChild->value() : "null";
echo " , lChild: ";
echo ($this->root->lChild != NULL) ? $this->root->lChild->value() : "null";
echo "<br>\n";*/
}
if ($this->root->lChild != NULL) {
echo $this->getString($this->root->lChild);
}
}
private function getString(&$node) {
if (defined("DEBUG")) {
if (DEBUG >= 5) {
echo "getString<br>\n";
}
}
if ($node->rChild != NULL) {
echo $this->getString($node->rChild);
}
if ($node != NULL) {
echo $node->value() . "<br>\n";
/*echo $node->value();
echo " , rChild: ";
echo ($node->rChild != NULL) ? $node->rChild->value() : "null";
echo " , lChild: ";
echo ($node->lChild != NULL) ? $node->lChild->value() : "null";
echo "<br>\n";*/
}
if ($node->lChild != NULL) {
echo $this->getString($node->lChild);
}
}
}
// test
$test = new Tree();
$test->insert(50);
$test->insert(75);
$test->insert(25);
$test->insert(10);
$test->insert(20);
$test->insert(30);
$test->insert(40);
$test->insert(60);
$test->insert(70);
$test->insert(80);
$test->insert(90);
$test->insert(10); // das 2. mal die 10!
$test->insert(11);
$test->insert(45);
$test->insert(34);
$test->toString();
echo "#################<br>\n";
$test->remove(25);
$test->toString();
echo "#################<br>\n";
$test->remove(75);
$test->toString();
echo "#################<br>\n";
$test->remove(11);
$test->toString();
echo "#################<br>\n";
$test->remove(50);
$test->toString();
?>