php 如何遍历树状结构

树状结构是一种数据结构，其中的节点以分层方式组织，每个节点可以有多个子节点。在 PHP 中，遍历树状结构有几种方法。

前序遍历

前序遍历以递归的方式访问节点，遍历顺序为：

1. 访问当前节点
2. 遍历左子树
3. 遍历右子树

代码示例：

立即学习“PHP免费学习笔记（深入）”；

function preOrder(Node $node) {
  echo $node->getData(); // 访问当前节点
  if ($node->hasLeft()) {
    preOrder($node->getLeft()); // 遍历左子树
  }
  if ($node->hasRight()) {
    preOrder($node->getRight()); // 遍历右子树
  }
}

中序遍历

中序遍历的顺序为：

1. 遍历左子树
2. 访问当前节点
3. 遍历右子树

代码示例：

立即学习“PHP免费学习笔记（深入）”；

function inOrder(Node $node) {
  if ($node->hasLeft()) {
    inOrder($node->getLeft()); // 遍历左子树
  }
  echo $node->getData(); // 访问当前节点
  if ($node->hasRight()) {
    inOrder($node->getRight()); // 遍历右子树
  }
}

后序遍历

后序遍历的顺序为：

1. 遍历左子树
2. 遍历右子树
3. 访问当前节点

代码示例：

立即学习“PHP免费学习笔记（深入）”；

function postOrder(Node $node) {
  if ($node->hasLeft()) {
    postOrder($node->getLeft()); // 遍历左子树
  }
  if ($node->hasRight()) {
    postOrder($node->getRight()); // 遍历右子树
  }
  echo $node->getData(); // 访问当前节点
}

层次遍历

层次遍历使用队列来遍历节点，按照从上到下的顺序。遍历顺序为：

1. 将根节点入队

2. 只要队列不为空：

   • 出队并访问队首元素
   • 如果队首元素存在左子树，将左子树入队
   • 如果队首元素存在右子树，将右子树入队

代码示例：

立即学习“PHP免费学习笔记（深入）”；

function levelOrder(Node $node) {
  $queue = [$node];
  while (!empty($queue)) {
    $currentNode = array_shift($queue); // 出队
    echo $currentNode->getData(); // 访问当前节点
    if ($currentNode->hasLeft()) {
      array_push($queue, $currentNode->getLeft()); // 入队左子树
    }
    if ($currentNode->hasRight()) {
      array_push($queue, $currentNode->getRight()); // 入队右子树
    }
  }
}