PHP實作二元樹的方式與應用-php教程-PHP中文網

PHP實作二元樹的方式與應用

王林

發布： 2023-06-18 18:30:02

原創

1349 人瀏覽過

在電腦科學中，二元樹是一種重要的資料結構。它由節點和指向它們的邊組成，每個節點最多連接兩個子節點。二叉樹的應用廣泛，例如搜尋演算法、編譯器、資料庫、記憶體管理等領域。許多程式語言都支援二元樹資料結構的實現，其中PHP是其中之一。本文將介紹PHP實作二元樹的方式以及其應用。

二元樹的定義

二元樹是一種資料結構，它由節點和指向它們的邊組成。每個節點最多連接兩個子節點，左節點和右節點。

PHP實作二元樹的方式

在PHP中，二元樹可以使用類別和物件表示。下面是一個基本的二元樹類別範例：

class BinaryTree {
   public $value;
   public $left_child;
   public $right_child;
    
   function __construct($value) {
      $this->value = $value;
      $this->left_child = NULL;
      $this->right_child = NULL;
   }
}

登入後複製

在這個類別中，我們定義了一個節點的值，左子節點和右子節點。構造函數用於設定節點的初始狀態。

接下來，我們可以實作插入和搜尋節點的方法。以下是這些方法的程式碼範例：

class BinaryTree {
   // …

   function insert_left($value) {
      if ($this->left_child == NULL) {
         $this->left_child = new BinaryTree($value);
      } else {
         $t = new BinaryTree($value);
         $t->left_child = $this->left_child;
         $this->left_child = $t;
      }
   }

   function insert_right($value) {
      if ($this->right_child == NULL) {
         $this->right_child = new BinaryTree($value);
      } else {
         $t = new BinaryTree($value);
         $t->right_child = $this->right_child;
         $this->right_child = $t;
      }
   }

   function get_left_child() {
      return $this->left_child;
   }

   function get_right_child() {
      return $this->right_child;
   }

   function set_root_val($obj) {
      $this->value = $obj;
   }

   function get_root_val() {
      return $this->value;
   }
}

登入後複製

在這些方法中，insert_left()和insert_right()方法用於插入新節點。 get_left_child()和get_right_child()方法用來取得左子樹和右子樹。 set_root_val()和get_root_val()方法用來設定和取得根值。此外，我們還可以實作刪除節點、遍歷二元樹等方法。