PHP 递归函数如何进行二叉树遍历- 技术经验 -卓越飞翔博客

php 递归函数提供三种方法进行二叉树遍历：前序遍历（自顶向下，先根节点后左子树再右子树）；中序遍历（自底向上，先左子树后根节点再右子树）；后序遍历（自底向上，先左子树后右子树再根节点）。

PHP 递归函数如何进行二叉树遍历

PHP 递归函数如何进行二叉树遍历

前言

二叉树是一种广泛用于数据结构和算法的数据结构。遍历二叉树是访问和处理其所有节点的常见操作。PHP 提供了递归函数来实现不同类型的二叉树遍历，例如：

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

前序遍历 (pre-order)

前序遍历以根节点开始，然后先遍历其左子树，再遍历其右子树。

function preOrderTraversal($node) {
    if ($node) {
        echo $node->data;
        preOrderTraversal($node->left);
        preOrderTraversal($node->right);
    }
}

中序遍历 (in-order)

中序遍历先遍历左子树，然后访问根节点，最后遍历右子树。

function inOrderTraversal($node) {
    if ($node) {
        inOrderTraversal($node->left);
        echo $node->data;
        inOrderTraversal($node->right);
    }
}

后序遍历 (post-order)

后序遍历先遍历左子树，然后遍历右子树，最后访问根节点。

function postOrderTraversal($node) {
    if ($node) {
        postOrderTraversal($node->left);
        postOrderTraversal($node->right);
        echo $node->data;
    }
}

实战案例

假设我们有一个二叉树：

我们可以使用这些函数遍历这棵二叉树并打印其节点数据：

class Node {
    public $data;
    public $left;
    public $right;
}

$root = new Node();
$root->data = 1;
$root->left = new Node();
$root->left->data = 2;
$root->left->left = new Node();
$root->left->left->data = 4;
$root->left->right = new Node();
$root->left->right->data = 5;
$root->right = new Node();
$root->right->data = 3;

preOrderTraversal($root);  // 输出：1 2 4 5 3
inOrderTraversal($root);   // 输出：4 2 5 1 3
postOrderTraversal($root); // 输出：4 5 2 3 1

相关推荐