php二叉树怎样遍历节点

在 PHP 中，可以使用递归或迭代方法来遍历二叉树节点。这里，我们将介绍两种方法：前序遍历、中序遍历和后序遍历。

首先，定义一个简单的二叉树节点类：

class TreeNode {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}

递归遍历

1. 前序遍历（根->左->右）

function preOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    echo $node->value . " ";
    preOrderTraversal($node->left);
    preOrderTraversal($node->right);
}

2. 中序遍历（左->根->右）

function inOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    inOrderTraversal($node->left);
    echo $node->value . " ";
    inOrderTraversal($node->right);
}

3. 后序遍历（左->右->根）

function postOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    postOrderTraversal($node->left);
    postOrderTraversal($node->right);
    echo $node->value . " ";
}

迭代遍历

1. 前序遍历（根->左->右）

function preOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [$node];

    while ($stack) {
        $current = $stack[count($stack) - 1];
        $stack = array_slice($stack, 0, -1);
        echo $current->value . " ";

        if ($current->right !== null) {
            $stack[] = $current->right;
        }
        if ($current->left !== null) {
            $stack[] = $current->left;
        }
    }
}

2. 中序遍历（左->根->右）

function inOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [];
    $current = $node;

    while ($current !== null || count($stack) > 0) {
        while ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        }

        $current = array_pop($stack);
        echo $current->value . " ";
        $current = $current->right;
    }
}

3. 后序遍历（左->右->根）

function postOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [];
    $lastVisitedNode = null;

    $current = $node;
    while ($current !== null || count($stack) > 0) {
        if ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        } else {
            $topNode = array_pop($stack);
            if ($topNode->right !== null && $lastVisitedNode !== $topNode->right) {
                $current = $topNode->right;
            } else {
                echo $topNode->value . " ";
                $lastVisitedNode = $topNode;
            }
        }
    }
}

使用这些遍历函数，可以方便地遍历二叉树的节点。