亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

php 遞歸函數(shù)提供三種方法進(jìn)行二叉樹遍歷：前序遍歷（自頂向下，先根節(jié)點(diǎn)后左子樹再右子樹）；中序遍歷（自底向上，先左子樹后根節(jié)點(diǎn)再右子樹）；后序遍歷（自底向上，先左子樹后右子樹再根節(jié)點(diǎn)）。

PHP 遞歸函數(shù)如何進(jìn)行二叉樹遍歷

前言

二叉樹是一種廣泛用于數(shù)據(jù)結(jié)構(gòu)和算法的數(shù)據(jù)結(jié)構(gòu)。遍歷二叉樹是訪問和處理其所有節(jié)點(diǎn)的常見操作。PHP 提供了遞歸函數(shù)來實(shí)現(xiàn)不同類型的二叉樹遍歷，例如：

前序遍歷 (pre-order)

前序遍歷以根節(jié)點(diǎn)開始，然后先遍歷其左子樹，再遍歷其右子樹。

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

登錄后復(fù)制

中序遍歷 (in-order)

中序遍歷先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹。

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

登錄后復(fù)制

后序遍歷 (post-order)

后序遍歷先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)。

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

登錄后復(fù)制

實(shí)戰(zhàn)案例

假設(shè)我們有一個二叉樹：

        1
       / \
      2   3
     / \
    4   5

登錄后復(fù)制

我們可以使用這些函數(shù)遍歷這棵二叉樹并打印其節(jié)點(diǎn)數(shù)據(jù)：

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

登錄后復(fù)制