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; } } } } 

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