php怎麼實作二元樹（程式碼範例）

二元樹是電腦科學中的一種基本資料結構，是最常見的樹狀結構，如在電腦科學中用於搜尋和排序，以及在電腦科學中的許多其他領域使用。 php是一種廣泛使用的伺服器端腳本語言，支援動態網頁開發。在本篇文章中，我們將介紹如何用php實作二元樹。

什麼是二元樹？

二元樹是由若干個節點組成的，每個節點最多有兩個子節點。它有三個屬性：

• 節點值
• 左子樹指標
• #右子樹指標

##二元樹分為以下幾類別：

滿二元樹：除了葉節點，其他節點都有兩個子節點
• #完全二元樹：如果二元樹的深度為d，除了第d層，其他層都是滿的，而且在第d層上，所有的葉子節點都在左邊連續的位置
• 二元搜尋樹：左子樹所有節點小於根節點值，右子樹所有節點值大於根節點值

實作二元樹

我們可以用類別來定義二元樹結構。每個節點都是一個對象，包含以下屬性：

value：節點值
• left：左子樹指標
• ##right：右子樹指標
• 建立一個類別來表示節點。

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

接下來，我們需要建立一個類別來表示二元樹。

class BinarySearchTree {
    public $root;
    function __construct() {
        $this -> root = null;
    }
}

接下來，我們將定義以下二元樹的方法：

insert(value)：將值插入二元樹

• search(value)：尋找二元樹中的值
• delete(value)：從二元樹中刪除值
• #插入節點

插入節點方法將插入新節點到正確的位置。如果樹為空，新節點是根節點。否則，我們開始從根節點比較目前節點的值。

如果新節點的值小於目前節點的值，則我們將新節點插入左子樹。

• 如果新節點的值大於目前節點的值，則我們將新節點插入右子樹。
• 如果新節點的值等於目前節點的值，則節點已經存在，不需要插入。
• 這是插入方法的程式碼：

function insert($value) {
    $newNode = new Node($value);
    if ($this -> root == null) {
        $this -> root = $newNode;
    } else {
        $current = $this -> root;
        while (true) {
            if ($value < $current -> value) {
                if ($current -> left == null) {
                    $current -> left = $newNode;
                    return;
                } else {
                    $current = $current -> left;
                }
            } else if ($value > $current -> value) {
                if ($current -> right == null) {
                    $current -> right = $newNode;
                    return;
                } else {
                    $current = $current -> right;
                }
            } else {
                return;
            }
        }
    }
}

尋找節點

#尋找節點方法是一個簡單的遞歸方法。從根節點開始比較節點的值。如果值相等，則傳回目前節點。否則，如果節點的值小於要尋找的值，則繼續尋找左子樹。如果值大於要尋找的值，則繼續尋找右子樹。

這是尋找方法的程式碼：

function search($value) {
    $current = $this -> root;
    while ($current != null) {
        if ($value == $current -> value) {
            return $current;
        } else if ($value < $current -> value) {
            $current = $current -> left;
        } else {
            $current = $current -> right;
        }
    }
    return null;
}

刪除節點

刪除節點方法是整個實作中最複雜的方法之一。如何刪除節點取決於節點的子節點數。可以有以下幾種情況：

節點是葉子節點，沒有子節點。直接刪除節點。

• 節點只有一個子節點。將子節點替換為該節點。
• 節點有兩個子節點。找到節點右子樹中的最小值，將最小值替換為該節點，並從右子樹中刪除最小值。
• 這是刪除方法的程式碼：

function delete($value) {
    $current = $this -> root;
    $parent = null;
    while ($current != null) {
        if ($value == $current -> value) {
            if ($current -> left == null && $current -> right == null) {
                if ($parent == null) {
                    $this -> root = null;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = null;
                    } else {
                        $parent -> right = null;
                    }
                }
            } else if ($current -> left == null) {
                if ($parent == null) {
                    $this -> root = $current -> right;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> right;
                    } else {
                        $parent -> right = $current -> right;
                    }
                }
            } else if ($current -> right == null) {
                if ($parent == null) {
                    $this -> root = $current -> left;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> left;
                    } else {
                        $parent -> right = $current -> left;
                    }
                }
            } else {
                $replacementNode = $current -> right;
                while ($replacementNode -> left != null) {
                    $replacementNode = $replacementNode -> left;
                }
                $removeValue = $replacementNode -> value;
                $this -> delete($replacementNode -> value);
                $current -> value = $removeValue;
            }
            return;
        } else if ($value < $current -> value) {
            $parent = $current;
            $current = $current -> left;
        } else {
            $parent = $current;
            $current = $current -> right;
        }
    }
}

結論

#現在，我們已經學習如何用php實作二元樹。二元樹是計算機科學中的一種基本資料結構，許多演算法和應用都涉及到它。我們已經學習如何插入節點，尋找節點和刪除節點。我們還可以擴展這個類，實作其他實用的方法。

以上是php怎麼實作二元樹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！