How to implement binary tree in php (code example)

Binary tree is a basic data structure in computer science. It is the most common tree structure, such as used in computer science for searching and sorting, and used in many other fields in computer science. PHP is a widely used server-side scripting language that supports dynamic web development. In this article, we will introduce how to implement a binary tree using PHP.

What is a binary tree?

Binary tree is composed of several nodes, each node has at most two child nodes. It has three attributes:

• Node value
• Left subtree pointer
• Right subtree pointer

The binary tree is divided into the following Class:

• Full binary tree: Except for leaf nodes, other nodes have two child nodes
• Complete binary tree: If the depth of the binary tree is d, except for the dth layer, all other layers are Full, and on the dth level, all leaf nodes are in continuous positions on the left
• Binary search tree: all nodes in the left subtree have values ​​less than the root node, and all nodes in the right subtree have values ​​greater than the root node Value

Implementing binary tree

We can use classes to define binary tree structures. Each node is an object containing the following properties:

• value: node value
• left: left subtree pointer
• right: right subtree pointer

Create a class to represent the node.

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

Next, we need to create a class to represent the binary tree.

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

Next, we will define the following binary tree methods:

• insert(value): Insert a value into the binary tree
• search(value): Search the binary tree The value of
• delete(value): Delete the value from the binary tree

Insert node

The insert node method will insert the new node to the correct position. If the tree is empty, the new node is the root node. Otherwise, we start comparing the current node's value from the root node.

• If the value of the new node is less than the value of the current node, then we insert the new node into the left subtree.
• If the value of the new node is greater than the value of the current node, then we insert the new node into the right subtree.
• If the value of the new node is equal to the value of the current node, the node already exists and does not need to be inserted.

This is the code for the insert method:

function insert($value) {
    $newNode = new Node($value);
    if ($this -> root == null) {
        $this -> root = $newNode;
    } else {
        $current = $this -> root;
        while (true) {
            if ($value  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

The Find Node method is a simple recursive method. Compare node values ​​starting from the root node. If the values ​​are equal, return the current node. Otherwise, if the node's value is less than the value you are looking for, continue searching the left subtree. If the value is greater than the value you are looking for, continue searching the right subtree.

This is the code for the find method:

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

Delete Node

The delete node method is one of the most complex methods in the entire implementation. How a node is deleted depends on the number of children of the node. There can be the following situations:

• The node is a leaf node and has no child nodes. Delete the node directly.
• Node has only one child node. Replace child nodes with this node.
• Node has two child nodes. Find the minimum value in the right subtree of the node, replace the minimum value with that node, and remove the minimum value from the right subtree.

This is the code for the delete method:

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  value) {
            $parent = $current;
            $current = $current -> left;
        } else {
            $parent = $current;
            $current = $current -> right;
        }
    }
}

Conclusion

Now, we have learned how to implement a binary tree with php. Binary trees are a basic data structure in computer science, and many algorithms and applications involve it. We have learned how to insert nodes, find nodes and delete nodes. We can also extend this class to implement other practical methods.

The above is the detailed content of How to implement binary tree in php (code example). For more information, please follow other related articles on the PHP Chinese website!