Wie ändere ich diese Baumknoten-Einfügelogik, um einen ausgeglichenen Binärbaum zu erhalten?

Question

Ich bin neu in der Codierung für Bäume.

die folgenden Eingabeanordnung gegeben wird -

array(10,7,13,5,6,8,11,15,14,4,3,16) 

Ich möchte einen ausgeglichenen Binärbaum herzustellen, indem man diese Werte einen nach dem anderen eingeführt wird, von dem ersten Element ausgehend (linke Kind eines Knotens sollte, dann eingesetzt werden Rechtes Kind, dann sollte der nächste Knoten überprüft werden, um seine linken und rechten Kinder einzufügen Alle Einfügungen sollten zuerst auf einer Ebene passieren, bevor sie auf eine höhere Ebene eingefügt werden. Das Ergebnis sollte so aussehen -

Hier ist der Code, den ich jetzt habe (ein bisschen von einem BST-Code geändert, dass ich here gefunden)

<?php 


class Node 
{ 

    public $left; 
    public $right; 
    public $data; 

    public function __construct($data) 
    { 
     $this->data = $data; 
     $this->right = NULL; 
     $this->left = NULL; 
    } 

} //End class Node 

class BTree 
{ 

    public $root; 

    public function __construct() 
    { 
     $this->root = NULL; 
    } 

    /* Insert the first node to the BST*/ 
    public function insert($data) 
    { 

     $node = new Node($data); 

     if($this->root === NULL) 
       $this->root = $node; 
     else 
      $this->insertNode($this->root,$node); 

    } 

    /* Insert node starting from root */ 
    public function insertNode(&$root,$node) 
    { 
      if($root === NULL) 
      {//root is not occupied, set root as the node 
       $root = $node; 
      } 
      else 
      { 
       if($root->left && $root->left->data===null) 
       { 
        $root->left==$node; 
       } 
       else 
       { 
        if($root->right && $root->right->data===null) //Not using else to avoid duplicate values 
        { 
         $root->right==$node; 
        } 
        else 
        { 
         $this->insertNode($root->left,$node); //Search for place in the right side to insert   
        } 
       } 
      }  
    } 

    /* Get an array and insert all items in it to the tree in the array order */ 
    public function multiInsert($array) 
    { 

     foreach($array as $data) 
      $this->insert($data); 
    } 


    /* 
    Draw the tree from left to right 
    Line with same color are in same level of the tree 
    */ 
    public function draw($node = 'root', $depth = 0) 
    { 

     if($node == 'root') $node = $this->root; /* If node not selected the default is the tree root */ 

     if ($node === null) return; 

     return 
      $this->draw($node->right, $depth + 1).str_repeat("&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;", $depth). 
      "<span style='color:".(($depth%2 == 0)? 'red' : 'blue')."'>".$node->data."</span><br>". 
      $this->draw($node->left, $depth + 1); 
    } 

} //End class BTree 


/* ########### EXAMPLE ########### */ 
echo '<h1>Binary Tree</h1>'; 
$tree = new BTree(); 
$tree->multiInsert(array(10,7,13,5,6,8,11,15,14,4,3,16)); 
echo'<br><br>'; 
echo $tree->draw(); 

?> 

Dies wird in einen Baum resultierende mit nur Kinder links, wie in der folgenden Ausgabe gezeigt -

Answer 1

Diese:

if($root->left && $root->left->data===null) 
    ^^^^^^^^^^^ 

Sie initialisieren Ihre Knoten null zu sein, so $root->left, null ist, wird false bewerten, Sie auf der else Weg zu schicken. $root->right ist auch Null, also gehen Sie runter zu insertNode($root->left), wo Sie schließlich mit einem Null-Knoten enden und es left bedingungslos zuweisen.

sollten Sie

if (is_null($root->left)) { 
    $root->left = $node 
} else if (is_null($root->right)) { 
    $root->right = $node; 
} else (
    $this->insertNode(...); 
}