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

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

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

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

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

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

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

ログイン後にコピー

バイナリツリーの作成

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

// 创建二叉树 $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);

ログイン後にコピー

バイナリツリーのトラバーサル

バイナリツリーのトラバーサルは、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 " ";

ログイン後にコピー

二分木検索

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

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 サイトの他の関連記事を参照してください。