php如何遍历树状结构

php 如何遍历树状结构

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

前序遍历

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

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

登录后复制

代码示例：

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

登录后复制

中序遍历

中序遍历的顺序为：

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

登录后复制

代码示例：

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

登录后复制

后序遍历

后序遍历的顺序为：

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

登录后复制

代码示例：

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

登录后复制

层次遍历

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

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

代码示例：

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

登录后复制

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