PHP 函数中递归如何用于二叉树的遍历或操作？- 技术经验 -卓越飞翔博客

递归在 php 二叉树操作中的运用包括：递归遍历：前序、中序和后序遍历二叉树。递归操作：在二叉树中查找、插入和删除元素。

PHP 函数中递归如何用于二叉树的遍历或操作？

PHP 函数中的递归：二叉树遍历和操作

简介
递归是一种强大的编程技术，它允许函数调用自身。在二叉树操作中，递归特别有用，因为它自然契合二叉树的数据结构。本文将探讨如何使用 PHP 函数的递归功能，高效地遍历或操作二叉树。

二叉树的数据结构
二叉树是一种非线性数据结构，其中每个节点最多有两个子节点：左子节点和右子节点。可以使用以下 PHP 类来表示二叉树的节点：

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

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

    public function __construct($data) {
        $this->data = $data;
        $this->left = null;
        $this->right = null;
    }
}

递归遍历二叉树

前序遍历：
前序遍历首先访问根节点，然后递归地遍历左子树和右子树。

function preorderTraversal($root) {
    if ($root != null) {
        echo $root->data . " ";
        preorderTraversal($root->left);
        preorderTraversal($root->right);
    }
}

中序遍历：
中序遍历首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

function inorderTraversal($root) {
    if ($root != null) {
        inorderTraversal($root->left);
        echo $root->data . " ";
        inorderTraversal($root->right);
    }
}

后序遍历：
后序遍历首先递归地遍历左子树和右子树，最后访问根节点。

function postorderTraversal($root) {
    if ($root != null) {
        postorderTraversal($root->left);
        postorderTraversal($root->right);
        echo $root->data . " ";
    }
}

操作二叉树

查找元素：
递归可用于在二叉树中查找特定元素。

function findElement($root, $data) {
    if ($root == null) {
        return false;
    }

    if ($root->data == $data) {
        return true;
    }

    return findElement($root->left, $data) || findElement($root->right, $data);
}

插入元素：
递归也可用于在二叉树中插入元素，保持二叉搜索树的性质。

function insertElement($root, $data) {
    if ($root == null) {
        return new Node($data);
    }

    if ($data < $root->data) {
        $root->left = insertElement($root->left, $data);
    } else {
        $root->right = insertElement($root->right, $data);
    }

    return $root;
}

实战案例

我们使用以下二叉树作为实战案例：

遍历输出：

前序遍历：5 3 2 4 7 8
中序遍历：2 3 4 5 7 8
后序遍历：2 4 3 8 7 5

查找元素：

查找元素 4： true
查找元素 9： false

插入元素：

插入元素 1：二叉树变为：

            5
          /   
         3     7
        /    / 
       2   4 1   8

相关推荐