【PHP 实现数据结构】遍历二叉查找树

1. 先序：访问结点均是第一次经过结点时进行的（根节点 -> 左节点 -> 右节点）。
2. 中序：访问结点均是第二次经过结点时进行的（左节点 -> 根节点 -> 右节点）。
3. 后序：访问结点均是第三次经过结点时进行的（左节点 -> 右节点 -> 根节点）。

public function preOrder()
{
$stack = []; // 先访问根结点$current = $this->root;$pre = [];

while (!empty($stack) ||$current != null) {

// 访问左子树
while ($current != null) {$pre[] = $current->data;$stack[] = $current;$current = $current->left; }$current = array_pop($stack); // 访问右子树$current = $current->right; } return$pre;
}

public function inOrder()
{
$stack = []; // 先访问根结点$current = $this->root;$sort = [];
while (!empty($stack) ||$current != null) {

// 访问左子树
while ($current != null) {$stack[] = $current;$current = $current->left; }$current = array_pop($stack);$sort[] = $current->data; // 访问右子树$current = $current->right; } return$sort;
}

public function postOrder()
{
$stack = [];$visitStack = [];
$current =$this->root;
while ($current != null) {$visitStack[] = $current; if ($current->left != null) {
$stack[] =$current->left;
}
if ($current->right != null) {$stack[] = $current->right; }$current = array_pop($stack); }$next = [];
while ($current = array_pop($visitStack)) {
$next[] =$current->data;
}

return \$next;
}