php實(shí)現(xiàn)二叉樹的方法是什么

這篇“php實(shí)現(xiàn)二叉樹的方法是什么”文章的知識點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“php實(shí)現(xiàn)二叉樹的方法是什么”文章吧。

什么是二叉樹

二叉樹是由若干個(gè)節(jié)點(diǎn)組成的，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。它有三個(gè)屬性：

• 節(jié)點(diǎn)值

• 左子樹指針

• 右子樹指針

二叉樹分為以下幾類：

• 滿二叉樹：除了葉節(jié)點(diǎn)，其他節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)

• 完全二叉樹：如果二叉樹的深度為d，除了第d層，其他層都是滿的，而且在第d層上，所有的葉子節(jié)點(diǎn)都在左邊連續(xù)的位置

• 二叉搜索樹：左子樹所有節(jié)點(diǎn)小于根節(jié)點(diǎn)值，右子樹所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)值

實(shí)現(xiàn)二叉樹

我們可以用類來定義二叉樹結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都是一個(gè)對象，包含以下屬性：

• value：節(jié)點(diǎn)值

• left：左子樹指針

• right：右子樹指針

創(chuàng)建一個(gè)類來表示節(jié)點(diǎn)。

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

接下來，我們需要?jiǎng)?chuàng)建一個(gè)類來表示二叉樹。

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

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

• insert(value)：將值插入二叉樹

• search(value)：查找二叉樹中的值

• delete(value)：從二叉樹中刪除值

插入節(jié)點(diǎn)

插入節(jié)點(diǎn)方法將插入新節(jié)點(diǎn)到正確的位置。如果樹為空，新節(jié)點(diǎn)是根節(jié)點(diǎn)。否則，我們開始從根節(jié)點(diǎn)比較當(dāng)前節(jié)點(diǎn)的值。

• 如果新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，則我們將新節(jié)點(diǎn)插入左子樹。

• 如果新節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的值，則我們將新節(jié)點(diǎn)插入右子樹。

• 如果新節(jié)點(diǎn)的值等于當(dāng)前節(jié)點(diǎn)的值，則節(jié)點(diǎn)已經(jīng)存在，不需要插入。

這是插入方法的代碼：

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

查找節(jié)點(diǎn)

查找節(jié)點(diǎn)方法是一個(gè)簡單的遞歸方法。從根節(jié)點(diǎn)開始比較節(jié)點(diǎn)的值。如果值相等，返回當(dāng)前節(jié)點(diǎn)。否則，如果節(jié)點(diǎn)的值小于要查找的值，則繼續(xù)查找左子樹。如果值大于要查找的值，則繼續(xù)查找右子樹。

這是查找方法的代碼：

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

刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn)方法是整個(gè)實(shí)現(xiàn)中最復(fù)雜的方法之一。如何刪除節(jié)點(diǎn)取決于節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)。可以有以下幾種情況：

• 節(jié)點(diǎn)是葉子節(jié)點(diǎn)，沒有子節(jié)點(diǎn)。直接刪除節(jié)點(diǎn)。

• 節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)。將子節(jié)點(diǎn)替換為該節(jié)點(diǎn)。

• 節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。找到節(jié)點(diǎn)右子樹中的最小值，將最小值替換為該節(jié)點(diǎn)，并從右子樹中刪除最小值。

這是刪除方法的代碼：

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

以上就是關(guān)于“php實(shí)現(xiàn)二叉樹的方法是什么”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。