php如何遍历树状结构-php教程-PHP中文网

php如何遍历树状结构

小老鼠

发布： 2024-08-04 01:50:16

原创

1152人浏览过

php 如何遍历树状结构

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

前序遍历

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

<code class="php">1. 访问当前节点
2. 遍历左子树
3. 遍历右子树</code>

登录后复制

代码示例：

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

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

登录后复制

中序遍历

中序遍历的顺序为：

<code class="php">1. 遍历左子树
2. 访问当前节点
3. 遍历右子树</code>

登录后复制

代码示例：

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

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

登录后复制

后序遍历

BibiGPT-哔哔终结者

B站视频总结器-一键总结音视频内容

查看详情

后序遍历的顺序为：

<code class="php">1. 遍历左子树
2. 遍历右子树
3. 访问当前节点</code>

登录后复制

代码示例：

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

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

登录后复制

层次遍历

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

将根节点入队
只要队列不为空：
- 出队并访问队首元素
- 如果队首元素存在左子树，将左子树入队
- 如果队首元素存在右子树，将右子树入队

代码示例：

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

<code class="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()); // 入队右子树
    }
  }
}</code>

登录后复制

以上就是php如何遍历树状结构的详细内容，更多请关注php中文网其它相关文章！