PHP实现树的层次遍历(附完整源码)
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val) {
$this->val = $val;
$this->left = null;
$this->right = null;
}
}
class BinaryTree {
public $root;
public function __construct() {
$this->root = null;
}
public function levelOrderTraversal() {
if ($this->root === null) {
return;
}
$queue = array();
array_push($queue, $this->root);
while (!empty($queue)) {
$currentNode = array_shift($queue);
echo $currentNode->val . " ";
if ($currentNode->left !== null) {
array_push($queue, $currentNode->left);
}
if ($currentNode->right !== null) {
array_push($queue, $currentNode->right);
}
}
}
}
// Create a binary tree
$tree = new BinaryTree();
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->right = new TreeNode(5);
// Perform level order traversal
$tree->levelOrderTraversal();
`