首页  >  文章  >  后端开发  >  php怎么实现二叉树(代码示例)

php怎么实现二叉树(代码示例)

PHPz
PHPz原创
2023-04-10 09:43:14894浏览

二叉树是计算机科学中的一种基本数据结构,是最常见的树形结构,如在计算机科学中用于搜索和排序,以及在计算机科学中的许多其他领域使用。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中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn