再帰アルゴリズムを使用して PHP でバイナリ ツリーのトラバーサルと検索操作を実装するにはどうすればよいですか?

再帰アルゴリズムを使用して、PHP でバイナリ ツリーのトラバーサルと検索操作を実装するにはどうすればよいですか?

バイナリ ツリーは一般的に使用されるデータ構造であり、その操作にはトラバーサルと検索が含まれます。 PHP では、再帰アルゴリズムを使用してこれらの操作を実装できます。以下では、再帰アルゴリズムを使用して PHP でバイナリ ツリーのトラバーサルと検索操作を実装する方法を紹介し、具体的なコード例を示します。

1. バイナリ ツリー ノード クラスの定義

まず、ノードの値と左右の子への参照を含むバイナリ ツリー ノード クラスを定義する必要があります。ノード。コードは次のとおりです:

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

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

2. バイナリ ツリーの作成

次のコードを使用して、単純なバイナリ ツリーを作成できます:

// 创建二叉树
$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. バイナリ ツリーのトラバーサル

バイナリ ツリーのトラバーサルは、pre-order トラバーサル、in-order トラバーサル、および post-order トラバーサルに分類されます。これら 3 つのトラバーサル メソッドの再帰的実装を以下に紹介します。

• 事前順序トラバーサル

事前順序トラバーサルでは、最初にルート ノードにアクセスし、次に左側のサブツリーを横断し、最後に右側のサブツリーを横断します。コードは次のとおりです。

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

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

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

• インオーダー トラバーサル

インオーダー トラバーサルでは、最初に左側のサブツリーを走査し、次にルート ノードにアクセスし、最後に右側のサブツリーを走査します。サブツリー。コードは次のとおりです。

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

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

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

• 事後トラバーサル

事後トラバーサルでは、最初に左側のサブツリーをトラバースし、次に右側のサブツリーをトラバースし、最後にルートにアクセスします。ノード。コードは次のとおりです。

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

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

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

4. 二分木検索

二分木検索は、再帰的アルゴリズムを使用して、ノードの値を比較することによって実現できます。以下は、バイナリ ツリーで指定された値を検索するためのサンプル コードです。

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} 的节点
";
}

上記のコード例を通じて、再帰アルゴリズムを使用して、PHP でバイナリ ツリーのトラバーサルと検索操作を実装できます。実際にコードを実行してテストするために、必要に応じて例のバイナリ ツリー構造とルックアップ値を調整できます。

以上が再帰アルゴリズムを使用して PHP でバイナリ ツリーのトラバーサルと検索操作を実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。