このツリーノードの挿入ロジックを変更して、バランスのとれたバイナリツリーにするにはどうすればよいですか？

Question

私は木をコーディングするのが初めてです。私はその後、最初の要素（ノードの左の子が挿入されるべきであるから出発し、これらの値を一つずつ挿入することによって、平衡二分木を作製したい

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

-

は、次の入力配列が与えられます次のノードをチェックして左と右の子を挿入する必要があります。すべての挿入は、上位レベルに挿入する前にレベルに最初に行われる必要があります）。結果は次のように表示されるべきである - ここ

これはとツリーに得られている私は今（私はhereを発見BSTコードからビットを変更し）たコード

<?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(); 

?> 

あります次の出力に示すように、子供を残しただけ -

Answer 1

この：

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

あなたはとても$root->left、nullであるためにあなたのノードを初期化するには、ヌルされ、elseパスダウンあなたを送る、falseと評価されます。 $root->rightもnullなので、insertNode($root->left)に行きます。最終的にヌルノードになり、無条件でleftに割り当てられます。

あなたは、PHPの酔った命名規則について

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