阅读量:0
在 PHP 中，可以使用递归或迭代方法来遍历二叉树节点。这里，我们将介绍两种方法：前序遍历、中序遍历和后序遍历。
首先，定义一个简单的二叉树节点类：
class TreeNode { public $value; public $left; public $right; public function __construct($value) { $this->value = $value; $this->left = null; $this->right = null; } } 递归遍历
- 前序遍历（根->左->右）
function preOrderTraversal($node) { if ($node === null) { return; } echo $node->value . " "; preOrderTraversal($node->left); preOrderTraversal($node->right); } - 中序遍历（左->根->右）
function inOrderTraversal($node) { if ($node === null) { return; } inOrderTraversal($node->left); echo $node->value . " "; inOrderTraversal($node->right); } - 后序遍历（左->右->根）
function postOrderTraversal($node) { if ($node === null) { return; } postOrderTraversal($node->left); postOrderTraversal($node->right); echo $node->value . " "; } 迭代遍历
- 前序遍历（根->左->右）
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; } } } - 中序遍历（左->根->右）
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; } } - 后序遍历（左->右->根）
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; } } } } 使用这些遍历函数，可以方便地遍历二叉树的节点。
