бинарное дерево поиска в переполнении стека
У меня возникли некоторые проблемы с реализацией функции __toString () для печати двоичного дерева, я искал в Интернете, но ничего не смог найти. Буду признателен, если кто-нибудь сможет мне помочь!
Вот код:
class Noeud {
public $element;
public $fd;
public $fg;
public function __construct($element){
$this -> element = $element;
$this-> fd = NULL;
$this-> fg = NULL;
}
}class Arbre {
private $racine;
public function __construct(){
$this->racine = NULL;
}
public function isEmpty() {
return $this->racine === null;
}
//public function remove($element);
public function add($element){
$noeud = new Noeud($element);
if($this->isEmpty()){
$this->racine = $noeud;
}
else{
$this->addNode($noeud,$this->racine);
}
}
public function addNode($noeud, &$new){
if($new === null){
$new = $noeud;
}
else{
if($node->element > $new->element){
$this->addNode($node,$new->fd);
}
else if($node->element < $new->element){
$this->addNode($node,$new->fg);
}
else{
return;
}
}
}
public function __toString(){
//
}
Решение
Делайте то же, что и для метода addNode (), с точки зрения рекурсивного обхода дерева, и на каждом проходящем узле просто распечатывайте содержимое. Таким образом, на каждом узле вы будете распечатывать содержимое, а затем распечатывать содержимое любых дочерних узлов. Я не программист PHP, но что-то вроде этого:
printNode()
{
// print contents of current node
if left child exists
left child->printNode()
if right child exists
right child->printNode()
}
Другие решения
Попробуйте обход в порядке:
class Arbre {
//
// The existing code
//
public function __toString()
{
$this->printSubTree($this->racine, 0);
}
protected function printSubTree(Noeud $node, $depth)
{
if ($node === NULL) {
return;
}
// Print the right subtree
$this->printSubTree($node->fd, $depth + 1);
// Print some spaces for alignment
echo(str_pad('', $level, ' '));
// Print the value in $node
echo($node->element);
// That's all for this line
echo("\n");
// Print the left subtree
$this->printSubTree($node->fg, $depth + 1);
}
}
Это хорошо работает на консольных сценариях или, в HTML, если вы поместите вывод внутри <PRE> блок. Она печатает дерево, повернутое на 90 градусов против часовой стрелки. Каждый узел остается на своей собственной линии, корень начинается на столбце 1 и каждый узел, который находится на расстоянии N из корня выводится его значение, начиная со столбца N+1, Вы можете настроить расстояние, изменив + 1 с большим значением в вызовах printSubTree(),