php如何實(shí)現(xiàn)二叉樹(shù)

PHP
小億
83
2024-10-11 15:37:17

在PHP中，要實(shí)現(xiàn)一個(gè)二叉樹(shù)，首先需要?jiǎng)?chuàng)建一個(gè)表示樹(shù)節(jié)點(diǎn)的類，然后通過(guò)節(jié)點(diǎn)類來(lái)構(gòu)建二叉樹(shù)。以下是一個(gè)簡(jiǎn)單的二叉樹(shù)實(shí)現(xiàn)示例：

  1. 創(chuàng)建一個(gè)表示二叉樹(shù)節(jié)點(diǎn)的類：
class TreeNode {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}
  1. 使用節(jié)點(diǎn)類構(gòu)建二叉樹(shù)：
// 創(chuàng)建根節(jié)點(diǎn)
$root = new TreeNode(1);

// 創(chuàng)建左子節(jié)點(diǎn)
$root->left = new TreeNode(2);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);

// 創(chuàng)建右子節(jié)點(diǎn)
$root->right = new TreeNode(3);
$root->right->left = new TreeNode(6);
$root->right->right = new TreeNode(7);

以上代碼創(chuàng)建了一個(gè)如下結(jié)構(gòu)的二叉樹(shù)：

    1
   / \
  2   3
 / \ / \
4  5 6  7
  1. 實(shí)現(xiàn)二叉樹(shù)的基本操作（例如遍歷、查找等）：
// 前序遍歷
function preOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    echo $node->value . " ";
    preOrderTraversal($node->left);
    preOrderTraversal($node->right);
}

// 中序遍歷
function inOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    inOrderTraversal($node->left);
    echo $node->value . " ";
    inOrderTraversal($node->right);
}

// 后序遍歷
function postOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    postOrderTraversal($node->left);
    postOrderTraversal($node->right);
    echo $node->value . " ";
}

// 查找節(jié)點(diǎn)
function findNode($node, $target) {
    if ($node === null || $node->value === $target) {
        return $node;
    }

    $left = findNode($node->left, $target);
    if ($left !== null) {
        return $left;
    }

    return findNode($node->right, $target);
}

// 測(cè)試遍歷函數(shù)
echo "前序遍歷: ";
preOrderTraversal($root);
echo "\n中序遍歷: ";
inOrderTraversal($root);
echo "\n后序遍歷: ";
postOrderTraversal($root);
echo "\n";

// 測(cè)試查找函數(shù)
$target = 5;
$foundNode = findNode($root, $target);
if ($foundNode !== null) {
    echo "找到節(jié)點(diǎn)，值為: " . $foundNode->value . "\n";
} else {
    echo "未找到節(jié)點(diǎn)\n";
}

以上代碼展示了如何實(shí)現(xiàn)一個(gè)簡(jiǎn)單的二叉樹(shù)，并實(shí)現(xiàn)了前序遍歷、中序遍歷、后序遍歷和查找節(jié)點(diǎn)的基本操作。你可以根據(jù)需要擴(kuò)展這個(gè)示例，實(shí)現(xiàn)更多的二叉樹(shù)操作。

0 踩