PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

1. 前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。

ABDHECFG

2.中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。

HDBEAFCG

3.后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

HDEBFGCA

```function preorder(\$root){
\$stack = array();
array_push(\$stack, \$root);
while(!empty(\$stack)){
\$center_node = array_pop(\$stack);
echo \$center_node->value; // 根节点
if(\$center_node->right != null)
array_push(\$stack, \$center_node->right); // 压入右子树
if(\$center_node->left != null)
array_push(\$stack, \$center_node->left); // 压入左子树
}
}

```

```function inorder(\$root){
\$stack = array();
\$center_node = \$root;
while(!empty(\$stack) || \$center_node != null){
while(\$center_node != null){
array_push(\$stack, \$center_node);
\$center_node = \$center_node->left;
}
\$center_node = array_pop(\$stack);
echo \$center_node->value;
\$center_node = \$center_node->right;
}
}

```

```function tailorder(\$root){
\$stack = array();
\$outstack = array();
array_push(\$\$stack, \$root);
while(\$empty(\$stack)){
\$center_node = array_pop(\$stack);
array_push(\$outstack, \$center_node);
if(\$center_node->right != null)
array_push(\$stack, \$center_node->right);
if(\$center_node->left != null)
array_push(\$stack, \$center_node->left);
}
while(\$empty(\$outstack)){
\$center_node = array_pop(\$outstack);
echo \$center_node->value;
}
}

```