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

バイナリ ツリーは、コンピュータ サイエンスの基本的なデータ構造です。コンピュータ サイエンスで検索や並べ替えに使用されるなど、コンピュータ サイエンスの他の多くの分野で使用される、最も一般的なツリー構造です。 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 サイトの他の関連記事を参照してください。