PHP のバイナリ ツリー アルゴリズムと FAQ

Web 開発の継続的な発展に伴い、サーバー スクリプト言語として広く使用されている PHP は、そのアルゴリズムとデータ構造の重要性をますます高めています。これらのアルゴリズムやデータ構造の中でも、二分木アルゴリズムは非常に重要な概念です。この記事では、PHP におけるバイナリ ツリー アルゴリズムとその応用、およびよくある質問への回答を紹介します。

二分木とは何ですか?

バイナリ ツリーは、各ノードが最大 2 つの子ノード、つまり左の子ノードと右の子ノードを持つツリー構造です。ノードに子ノードがない場合、そのノードはリーフ ノードと呼ばれます。バイナリ ツリーは、検索および並べ替えアルゴリズムでよく使用されます。

PHP では、クラスを使用してバイナリ ツリーを実装できます。以下はバイナリ ツリー ノード クラスの例です。

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

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

この TreeNode クラスでは、$val はノードの値を表し、$left と $right はそれぞれノードの左の子ノードと右の子ノードを表します。

バイナリ ツリーを構築するにはどうすればよいですか?

PHP では、次のコードを使用して単純なバイナリ ツリーを構築できます。

$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);

これにより、ルート ノードの値が 1 で、左側の子ノードの値が 1 であるバイナリ ツリーが作成されます。 2 の右の子ノードの値は 3、その左の子ノードの左の子ノードの値は 4、その左の子ノードの右の子ノードの値は 5 です。

バイナリ ツリーをトラバースするにはどうすればよいですか?

バイナリ ツリーを走査するには、通常、事前順序トラバーサル、順序内トラバーサル、事後順序トラバーサルの 3 つの方法があります。

事前順序トラバーサルとは、最初にルート ノードにアクセスし、次に左のサブツリーと右のサブツリーをトラバースすることを指します。 PHP では、事前順序トラバーサルは、次のコードを通じて実装できます。

function preorderTraversal($root) {
  if ($root == null) {
    return;
  }
  echo $root->val . " ";
  preorderTraversal($root->left);
  preorderTraversal($root->right);
}

順序トラバーサルとは、最初に左側のサブツリーをトラバースし、次にルート ノードにアクセスし、最後に右側のサブツリーをトラバースすることを意味します。 PHP では、次のコードによって順序トラバーサルを実現できます。

function inorderTraversal($root) {
  if ($root == null) {
    return;
  }
  inorderTraversal($root->left);
  echo $root->val . " ";
  inorderTraversal($root->right);
}

事後トラバーサルとは、最初に左のサブツリーと右のサブツリーをトラバースし、次にルート ノードにアクセスすることを意味します。 PHP では、次のコードを通じて事後探索を実現できます:

function postorderTraversal($root) {
  if ($root == null) {
    return;
  }
  postorderTraversal($root->left);
  postorderTraversal($root->right);
  echo $root->val . " ";
}

バイナリ ツリーでノードを見つけるにはどうすればよいですか?

バイナリ ツリー内のノードを見つけるには、再帰アルゴリズムを使用できます。以下はサンプル コードです。

function search($root, $val) {
  if ($root == null || $root->val == $val) {
    return $root;
  }
  if ($val < $root->val) {
    return search($root->left, $val);
  }
  return search($root->right, $val);
}

このコードでは、ノードの値が $val に等しい場合、ノードが返されます。それ以外の場合、$val がノードの値より小さい場合は、左側のサブツリーを検索します。それ以外の場合は、正しいサブツリーを検索します。

ノードをバイナリ ツリーに挿入するにはどうすればよいですか?

ノードをバイナリ ツリーに挿入するには、再帰アルゴリズムを使用できます。以下はサンプル コードです。

function insert($root, $val) {
  if ($root == null) {
    return new TreeNode($val);
  }
  if ($val < $root->val) {
    $root->left = insert($root->left, $val);
  } else {
    $root->right = insert($root->right, $val);
  }
  return $root;
}

このコードでは、バイナリ ツリーが空の場合、新しいノードが返されます。それ以外の場合、$val がノードの値より小さい場合は、左側のサブツリーに挿入します。それ以外の場合は、右側のサブツリーに挿入します。

バイナリ ツリー内のノードを削除するにはどうすればよいですか?

バイナリ ツリー内のノードを削除するには、次の 3 つの状況を考慮する必要があります。

1. 削除するノードには子ノードがないため、ノードを削除するだけで済みます。直接。
2. 削除するノードには子ノードがあり、この子ノードに置き換える必要があります。
3. 削除するノードには 2 つの子ノードがあります。ノードの後継ノード (つまり、ノードの右側のサブツリーにある最小のノード) を見つけて、そのノードを後継ノードに置き換える必要があります。その後、後続ノードを削除します。

以下はサンプル コードです:

function deleteNode($root, $val) {
  if ($root == null) {
    return null;
  }
  if ($val < $root->val) {
    $root->left = deleteNode($root->left, $val);
  } else if ($val > $root->val) {
    $root->right = deleteNode($root->right, $val);
  } else {
    if ($root->left == null) {
      return $root->right;
    } else if ($root->right == null) {
      return $root->left;
    }
    $successor = $root->right;
    while ($successor->left != null) {
      $successor = $successor->left;
    }
    $root->val = $successor->val;
    $root->right = deleteNode($root->right, $successor->val);
  }
  return $root;
}

結論

バイナリ ツリー アルゴリズムは、PHP における非常に重要な概念です。再帰的アルゴリズムにより、バイナリツリーの構築、トラバーサル、ノード検索、ノードの挿入、ノードの削除などのさまざまな機能を実現できます。これらのアプリケーションを理解することは、効率的な Web アプリケーションを開発するのに非常に役立ちます。

以上がPHP のバイナリ ツリー アルゴリズムと FAQの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。