php - How do I modify this tree node insertion logic to result into a balanced binary tree? -
i new coding trees.
given following input array -
array(10,7,13,5,6,8,11,15,14,4,3,16) i prepare balanced binary tree inserting these values 1 one, starting first element (left child of node should inserted, right child, next node should checked insert it's left , right children. insertions should happen level first, before inserting higher level). result should appear -
here code have (modified bit bst code found here)
<?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 first node 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 root */ public function insertnode(&$root,$node) { if($root === null) {//root not occupied, set root 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 avoid duplicate values { $root->right==$node; } else { $this->insertnode($root->left,$node); //search place in right side insert } } } } /* array , insert items in tree in array order */ public function multiinsert($array) { foreach($array $data) $this->insert($data); } /* draw tree left right line same color in same level of tree */ public function draw($node = 'root', $depth = 0) { if($node == 'root') $node = $this->root; /* if node not selected default tree root */ if ($node === null) return; return $this->draw($node->right, $depth + 1).str_repeat(" ", $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(); ?> this resulting tree left children, shown in following output -
this:
if($root->left && $root->left->data===null) ^^^^^^^^^^^ you initialize nodes null, $root->left, being null, evaluate false, sending down else path. $root->right null, go down insertnode($root->left), end null node, , assign left unconditionally.
you should doing
if (is_null($root->left)) { $root->left = $node } else if (is_null($root->right)) { $root->right = $node; } else ( $this->insertnode(...); }
Comments
Post a Comment