Algoritma pokok binari dalam PHP dan Soalan Lazim

Dengan pembangunan berterusan pembangunan Web, PHP, sebagai bahasa skrip pelayan yang digunakan secara meluas, algoritma dan struktur datanya menjadi semakin penting. Di antara algoritma dan struktur data ini, algoritma pokok binari adalah konsep yang sangat penting. Artikel ini akan memperkenalkan algoritma pokok binari dan aplikasinya dalam PHP, serta jawapan kepada soalan biasa.

Apakah pokok binari?

Pokok binari ialah struktur pokok di mana setiap nod mempunyai paling banyak dua nod anak, iaitu nod anak kiri dan nod anak kanan. Jika nod tidak mempunyai nod anak, ia dipanggil nod daun. Pokok binari biasanya digunakan dalam algoritma carian dan pengisihan.

Dalam PHP, anda boleh menggunakan kelas untuk melaksanakan pepohon binari. Berikut ialah contoh kelas nod pokok binari:

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

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

Dalam kelas TreeNode ini, $val mewakili nilai nod, $left dan $right mewakili nod anak kiri dan nod anak kanan nod masing-masing.

Bagaimana untuk membina pokok binari?

Dalam PHP, anda boleh membina pokok binari ringkas dengan kod berikut:

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

Ini akan mencipta pokok binari yang nod akarnya mempunyai nilai 1 dan nod anak kirinya mempunyai nilai daripada 2 , nilai nod anak kanannya ialah 3, nilai nod anak kiri nod anak kirinya ialah 4, dan nilai nod anak kanan nod anak kirinya ialah 5.

Bagaimana untuk melintasi pokok binari?

Biasanya terdapat tiga cara untuk melintasi pokok binari: prapesan traversal, tertib traversal dan pasca pesanan traversal.

Preorder traversal bermaksud melawati nod akar dahulu, dan kemudian melintasi subpokok kiri dan subpokok kanan. Dalam PHP, traversal prapesanan boleh dilaksanakan melalui kod berikut:

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

Traversal tertib bermaksud mula-mula melintasi subpokok kiri, kemudian melawati nod akar, dan akhirnya melintasi subpokok kanan. Dalam PHP, traversal tertib boleh dicapai melalui kod berikut:

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

Traversal pasca pesanan bermaksud terlebih dahulu melintasi subpokok kiri dan subpokok kanan, dan kemudian melawati nod akar. Dalam PHP, traversal pasca pesanan boleh dicapai melalui kod berikut:

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

Bagaimana untuk mencari nod dalam pokok binari?

Untuk mencari nod dalam pokok binari, algoritma rekursif boleh digunakan. Berikut ialah contoh kod:

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

Dalam kod ini, jika nilai nod adalah sama dengan $val, maka nod itu dikembalikan. Jika tidak, jika $val kurang daripada nilai nod, cari dalam subpokok kiri. Jika tidak, cari dalam subpokok yang betul.

Bagaimana untuk memasukkan nod ke dalam pokok binari?

Untuk memasukkan nod ke dalam pokok binari, anda boleh menggunakan algoritma rekursif. Berikut ialah kod sampel:

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;
}

Dalam kod ini, jika pepohon binari kosong, nod baharu dikembalikan. Jika tidak, jika $val kurang daripada nilai nod, masukkan dalam subpokok kiri. Jika tidak, masukkan dalam subpokok yang betul.

Bagaimana untuk memadamkan nod dalam pokok binari?

Untuk memadamkan nod dalam pepohon binari, anda perlu mempertimbangkan tiga situasi berikut:

1. Nod yang akan dipadamkan tidak mempunyai nod anak, anda hanya perlu memadamkan nod secara langsung.
2. Nod yang akan dipadamkan mempunyai nod anak, yang perlu digunakan untuk menggantikan nod.
3. Nod yang akan dipadamkan mempunyai dua nod anak Anda perlu mencari nod pengganti nod (iaitu, nod terkecil dalam subpokok kanan nod), gantikan nod dengan nod pengganti, dan kemudian padamkan nod pengganti.

Berikut ialah kod sampel:

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;
}

Kesimpulan

Algoritma pokok binari ialah konsep yang sangat penting dalam PHP. Melalui algoritma rekursif, pelbagai fungsi seperti pembinaan pokok binari, traversal, carian nod, sisipan nod, dan pemadaman nod boleh direalisasikan. Memahami aplikasi ini sangat membantu untuk membangunkan aplikasi web yang cekap.

Atas ialah kandungan terperinci Algoritma pokok binari dalam PHP dan Soalan Lazim. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!