PHP Двоичное дерево, Как Traverse

Question

Ну я построить базовый Двоичное дерево, используя класс под названием Node для простоты я буду включать в себя метод ядра, который используется для insert Узлов

public function addNode($node) 
    { 
     if ($this->left == null && $node->getValue() < $this->value) { 
      $this->left = $node; 
      $this->left->parent = $this; 
      return; 
     } 

     if ($this->right == null && $node->getValue() > $this->value) { 
      $this->right = $node; 
      $this->right->parent = $this; 
      return; 
     } 

     if ($node->getValue() < $this->getValue()) { 
      $this->left->addNode($node); 
      return; 
     } 

     if ($node->getValue() > $this->getValue()) { 
      $this->right->addNode($node); 
      return; 
     } 

    } 

У меня есть эти основные элемента vars в классе узлов

private $left = null; 

private $right = null; 

private $value = null; 

private $parent = null; 

Я могу построить дерево, просто добавив к нему узлы.

$node = new Node(5); 
$node->addNode(new Node(7)); 
$node->addNode(new Node(3)); 
$node->addNode(new Node(4)); 

Теперь вопрос в том, как я пересекаю дерево, если хочу напечатать красивую текстовую диаграмму дерева. Я смущен тем, как правильно перемещаться на определенном уровне дерева. я пропустил важную переменную при построении дерева?

Answer 1

Ответ будет зависеть от того, что заказ вы хотите, чтобы пройти через дерево, а общая глубина первого обхода будет выглядеть следующим образом:

function traverseTree($rootNode) { 
    if($rootNode->left != null) 
     traverseTree($rootNode->left); 
    if($rootNode->right != null) 
     traverseTree($rootNode->right); 
    echo $rootNode->value; 
} 

Из комментария вы хотите в ширину первого обхода. См. Этот вопрос о первом прохождении в Java. Вы можете применить тот же алгоритм. How do implement a breadth first traversal?

Answer 2

широтой первый обход является то, что вы ищете:

printTree($root) { 
    $queue = array($root); 
    while (count($queue)) { 
     $node = array_shift($queue); 
     echo $node; 
     if($node->left != null) 
      array_unshift($node->left); 
     if($node->right != null) 
      array_unshift($node->right); 
    } 
} 

Ну Самуэль уже говорил вам о широте первого обхода, как я писал эту маленькую функцию, но все же ... Я думаю, что это то, что вы находясь в поиске.