建立二叉树 先序、中序、后序遍历二叉树

二叉树是一种树形结构，其中每个节点最多有两个子节点。建立二叉树的方法有很多种，其中一种常用的方法是通过输入带空格的前序序列建立二叉链表。具体步骤如下：

1. 读取输入的带空格的前序序列，将其存储在一个数组中。
2. 定义一个栈，将根节点入栈。
3. 从数组中取出下一个元素，如果该元素不为空，则将其作为当前节点的左子节点，并将该节点入栈。
4. 如果该元素为空，则从栈中弹出一个节点，将其作为当前节点，并从数组中取出下一个元素，将其作为当前节点的右子节点，并将该节点入栈。
5. 重复步骤3和4，直到数组中的所有元素都被处理完毕。

建立二叉树后，可以通过递归或非递归的方式进行先序、中序和后序遍历。其中，先序遍历的顺序是先遍历根节点，然后遍历左子树，最后遍历右子树；中序遍历的顺序是先遍历左子树，然后遍历根节点，最后遍历右子树；后序遍历的顺序是先遍历左子树，然后遍历右子树，最后遍历根节点。

以下是PHP基于非递归算法实现先序、中序及后序遍历二叉树的代码示例：

// 定义二叉树节点类
class TreeNode {
    public $val;
    public $left;
    public $right;
    public function __construct($val) {
        $this->val = $val;
        $this->left = null;
        $this->right = null;
    }
}

// 建立二叉树
function buildTree($preorder) {
    $stack = array();
    $root = new TreeNode(array_shift($preorder));
    array_push($stack, $root);
    while (!empty($preorder)) {
        $node = array_shift($preorder);
        if ($node !== null) {
            $cur = new TreeNode($node);
            $stack[count($stack) - 1]->left = $cur;
            array_push($stack, $cur);
        } else {
            $stack[count($stack) - 1]->right = null;
            array_pop($stack);
        }
    }
    return $root;
}

// 非递归实现先序遍历
function preorderTraversal($root) {
    $stack = array();
    $res = array();
    array_push($stack, $root);
    while (!empty($stack)) {
        $node = array_pop($stack);
        if ($node !== null) {
            array_push($res, $node->val);
            array_push($stack, $node->right);
            array_push($stack, $node->left);
        }
    }
    return $res;
}

// 非递归实现中序遍历
function inorderTraversal($root) {
    $stack = array();
    $res = array();
    $cur = $root;
    while ($cur !== null || !empty($stack)) {
        while ($cur !== null) {
            array_push($stack, $cur);
            $cur = $cur->left;
        }
        $node = array_pop($stack);
        array_push($res, $node->val);
        $cur = $node->right;
    }
    return $res;
}

// 非递归实现后序遍历
function postorderTraversal($root) {
    $stack = array();
    $res = array();
    array_push($stack, $root);
    while (!empty($stack)) {
        $node = array_pop($stack);
        if ($node !== null) {
            array_push($res, $node->val);
            array_push($stack, $node->left);
            array_push($stack, $node->right);
        }
    }
    return array_reverse($res);
}