Wie implementiert man Binärbaum-Traversal- und Suchoperationen in PHP mithilfe rekursiver Algorithmen?

Wie verwende ich einen rekursiven Algorithmus, um Binärbaum-Traversal- und Suchoperationen in PHP zu implementieren?

Binärbaum ist eine häufig verwendete Datenstruktur und seine Operationen umfassen Durchlaufen und Suchen. In PHP können wir rekursive Algorithmen verwenden, um diese Operationen zu implementieren. Im Folgenden wird die Verwendung rekursiver Algorithmen zur Implementierung von Binärbaum-Traversal- und Suchoperationen in PHP vorgestellt und spezifische Codebeispiele bereitgestellt.

1. Definieren Sie die Binärbaumknotenklasse

Zuerst müssen wir eine Binärbaumknotenklasse definieren, die den Wert des Knotens und Verweise auf die linken und rechten untergeordneten Knoten enthält. Der Code lautet wie folgt:

class TreeNode {
    public $value;
    public $left;
    public $right;

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

2. Erstellen Sie einen Binärbaum.

Wir können den folgenden Code verwenden, um einen einfachen Binärbaum zu erstellen:

// 创建二叉树
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);
$root->right->left = new TreeNode(6);
$root->right->right = new TreeNode(7);

3. Durchquerung eines Binärbaums.

Die Durchquerung eines Binärbaums ist unterteilt in Durchquerung vor der Bestellung, Durchquerung in der Reihenfolge und Durchquerung nach der Bestellung. Im Folgenden werden die rekursiven Implementierungen dieser drei Traversierungsmethoden vorgestellt.

• Durchquerung vor der Bestellung

Durchquerung vor der Bestellung besucht zuerst den Wurzelknoten, durchquert dann den linken Teilbaum und durchläuft schließlich den rechten Teilbaum. Der Code lautet wie folgt:

function preorderTraverse($root) {
    if ($root == null) {
        return;
    }

    echo $root->value . " ";  // 访问根节点
    preorderTraverse($root->left);  // 遍历左子树
    preorderTraverse($root->right);  // 遍历右子树
}

// 示例运行
echo "前序遍历结果：";
preorderTraverse($root);
echo "
";

• In-Order-Traversal

In-Order-Traversal durchläuft zuerst den linken Teilbaum, besucht dann den Wurzelknoten und durchläuft schließlich den rechten Teilbaum. Der Code lautet wie folgt:

function inorderTraverse($root) {
    if ($root == null) {
        return;
    }

    inorderTraverse($root->left);  // 遍历左子树
    echo $root->value . " ";  // 访问根节点
    inorderTraverse($root->right);  // 遍历右子树
}

// 示例运行
echo "中序遍历结果：";
inorderTraverse($root);
echo "
";

• Post-Order-Traversal

Post-Order-Traversal durchläuft zuerst den linken Teilbaum, dann den rechten Teilbaum und besucht schließlich den Wurzelknoten. Der Code lautet wie folgt:

function postorderTraverse($root) {
    if ($root == null) {
        return;
    }

    postorderTraverse($root->left);  // 遍历左子树
    postorderTraverse($root->right);  // 遍历右子树
    echo $root->value . " ";  // 访问根节点
}

// 示例运行
echo "后序遍历结果：";
postorderTraverse($root);
echo "
";

4. Binäre Baumsuche

Die binäre Baumsuche kann mithilfe eines rekursiven Algorithmus durch Vergleich der Werte von Knoten erreicht werden. Das Folgende ist ein Beispielcode zum Suchen eines bestimmten Werts in einem Binärbaum:

function searchValue($root, $value) {
    if ($root == null) {
        return false;
    }

    if ($root->value == $value) {  // 找到目标值
        return true;
    }

    // 在左子树中查找
    if (searchValue($root->left, $value)) {
        return true;
    }

    // 在右子树中查找
    if (searchValue($root->right, $value)) {
        return true;
    }

    return false;  // 未找到目标值
}

// 示例运行
$searchValue = 5;
if (searchValue($root, $searchValue)) {
    echo "二叉树中存在值为 {$searchValue} 的节点
";
} else {
    echo "二叉树中不存在值为 {$searchValue} 的节点
";
}

Mit dem obigen Codebeispiel können wir rekursive Algorithmen verwenden, um Binärbaumdurchquerungen und Suchoperationen in PHP zu implementieren. Sie können die binäre Baumstruktur und die Suchwerte im Beispiel nach Bedarf anpassen, um den Code tatsächlich auszuführen und zu testen.

Das obige ist der detaillierte Inhalt vonWie implementiert man Binärbaum-Traversal- und Suchoperationen in PHP mithilfe rekursiver Algorithmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!