<?php
class Node {
public $data = null;
public $parent = null;
public $left = null;
public $right = null;
}
#使用数组构造完全二叉树
function build_cbtree($a) {
$root = new Node();
$root->data = $a[0];
for ($i = 1; $i < count($a); $i++) {
$node = new Node();
$node->data = $a[$i];
insert_node($root, $node);
}
return $root;
}
#插入完全二叉树节点
function insert_node($root, $inode) {
#使用树的广度优先遍历顺序取出节点,直到找到第一个左右子节点没满的节点,将待插入节点插入节点左边或右边
$queue = array();
array_unshift($queue, $root);
while (!empty($queue)) {
$cnode = array_pop($queue);
if ($cnode->left == null) {
$cnode->left = $inode;
$inode->parent = $cnode;
return $root;
} else {
array_unshift($queue, $cnode->left);
}
if ($cnode->right == null) {
$cnode->right = $inode;
$inode->parent = $cnode;
return $root;
} else {
array_unshift($queue, $cnode->right);
}
}
return $root;
}
#树的广度优先遍历
function bf_traverse($root) {
$queue = array();
array_unshift($queue, $root);
while (!empty($queue)) {
$cnode = array_pop($queue);
echo $cnode->data . " ";
if ($cnode->left !== null) array_unshift($queue, $cnode->left);
if ($cnode->right !== null) array_unshift($queue, $cnode->right);
}
echo "<br>";
}
$a = array(9, 8, 7, 6, 8, 4, 3, 2, 1);
$root = build_cbtree($a);
bf_traverse($root); #广度优先遍历
?>
preferences:
41.67 ms | 402 KiB | 5 Q