PHPでバイナリツリーを実装する方法（コード例）-PHPの問題-php.cn

PHPでバイナリツリーを実装する方法（コード例）

PHPz

リリース： 2023-04-10 13:39:54

オリジナル

740 人が閲覧しました

バイナリツリーは、コンピュータサイエンスの基本的なデータ構造です。コンピュータサイエンスで検索や並べ替えに使用されるなど、コンピュータサイエンスの他の多くの分野で使用される、最も一般的なツリー構造です。 PHP は、動的な Web 開発をサポートするサーバー側スクリプト言語として広く使用されています。この記事では、PHPを使ってバイナリツリーを実装する方法を紹介します。

二分木とは何ですか?

バイナリツリーは複数のノードで構成され、各ノードには最大 2 つの子ノードがあります。これには 3 つの属性があります。

ノード値
左サブツリーポインタ
右サブツリーポインタ

バイナリツリーは、次のクラス:

完全なバイナリツリー: リーフノードを除き、他のノードには 2 つの子ノードがあります
完全なバイナリツリー: バイナリツリーの深さが 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) の値: バイナリツリーから値を削除します。

Insert node

Insert Node メソッドは、新しいノードを挿入します。ノードを正しい位置に移動します。ツリーが空の場合、新しいノードがルートノードになります。それ以外の場合は、ルートノードから現在のノードの値の比較を開始します。

新しいノードの値が現在のノードの値より小さい場合、新しいノードを左側のサブツリーに挿入します。
新しいノードの値が現在のノードの値より大きい場合、新しいノードを右のサブツリーに挿入します。
新しいノードの値が現在のノードの値と等しい場合、ノードはすでに存在しているため、挿入する必要はありません。

これは挿入メソッドのコードです:

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

ログイン後にコピー

Find Node

Find Node メソッドは単純な再帰メソッドです。ルートノードからノード値を比較します。値が等しい場合は、現在のノードを返します。それ以外の場合、ノードの値が探している値より小さい場合は、左側のサブツリーの検索を続けます。値が探している値より大きい場合は、正しいサブツリーの検索を続けます。

これは find メソッドのコードです:

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

ログイン後にコピー

ノードの削除

ノードの削除メソッドは、実装全体の中で最も複雑なメソッドの 1 つです。ノードの削除方法は、ノードの子の数によって異なります。次のような状況が考えられます。

ノードはリーフノードであり、子ノードがありません。ノードを直接削除します。
ノードには子ノードが 1 つだけあります。子ノードをこのノードに置き換えます。
ノードには 2 つの子ノードがあります。ノードの右側のサブツリーで最小値を見つけ、その最小値をそのノードで置き換え、右側のサブツリーから最小値を削除します。

これは delete メソッドのコードです:

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 中国語 Web サイトの他の関連記事を参照してください。