PHP实现的二叉搜索树（BST）原理及实现代码

PHP实现了二叉搜索树（BST）。实现的代码还是很简单的。下面我们来总结一下。

首先介绍一下二叉搜索树。二叉搜索树本质上是一棵二叉树。它不一定是满二叉树，也不一定是完全二叉树，但是二叉搜索树中每个非叶节点的值一定大于它的值。该节点的值还必须小于其右子节点的值。看下图可以更好地理解二叉搜索树。

二叉搜索树的基本概念非常简单易懂。基于以上概念，我们很容易得出以下结论：

（1）：任意非叶子节点的左子树中所有节点的值都必须小于该非叶子节点，并且必须小于非叶子节点右子树上的所有节点，这对于后期删除节点至关重要。

(2)：整个二叉搜索树中的最大值节点必须是二叉搜索树中最左边的叶子节点，最小值节点必须是二叉搜索树中最右边的叶子节点。根据这个，我们后面就可以很容易的找到整棵树中的最大值和最小值了。

(3)：由于上述特性，二叉搜索树被广泛应用于“字典”等数据类型的实现中，例如PHP中的数组数据类型。参考上图，如果我们每个节点中的值代表了数组中的键，那么如果我们在每个节点中放入一个值，我是否得到了键值对key=>value？ 。说到这里，有的同学会问为什么要用树这样的数据结构来实现key=>value这样的键值对。也可以实现常规数组。关于这一点，主要原因是，如果通过数组实现，查找、修改等操作的平均时间复杂度为O(N)，但如果使用二叉搜索树实现，平均时间复杂度仅为O(谎言）。下面我们如果有具体代码的话可以分析一下。

上面提到了二分查找的一些基本概念。接下来，我们将使用PHP来实现二叉搜索树。这里需要说的是，二叉搜索树没有堆的特殊性质，而且它仍然是链式结构，所以很难用数组来实现。当我第一次学习算法和数据结构时，我使用C中的指针来实现这种典型的链式结构。现在我已经切换到 PHP，没有指针。一开始确实不太习惯，后来发现在PHP中使用对象完全可以模拟指针来实现二叉搜索树。好了，废话不多说，我们直接用PHP来实现一个满足key=>value对的二叉搜索树。

(1)：定义用于描述二叉搜索树中节点的Node类

<?php
//Node类
class  Node{
    //当前节点的key
    public $key = null;
    //当前节点的value
    public $value = null;
    //当前节点的左子节点
     public $left = null;
    //当前节点的右子节点
     public $right = null;
}
//每一个实例化Node类的对象都用来描述二分搜索树中一个节点
//其中的属性key,value是来存放键值对信息
//属性right用来记录该节点的右子节点，属性left用来记录该节点的左子节点。
?>

(2)：初始化并构建二叉搜索树

//使用数组构建二分搜索树
//将数组传递到函数中,遍历循环数组，将数组中的元素依次添加到二分搜索树中
function bulid_binary_search_tree($arr){
    if(empty($arr)){
        return null;
    }
    //初始情况下，创建一个根节点
    $root = new Node();
    $level = 1;
    foreach($arr as $key=>$value){
        //为根节点进行赋值操作
        if($level == 1){
            $root->key = $key;
            $root->value = $value;
        }else{
            //创建一个新节点
            $new_node = new Node();
            $new_node->key = $key;
            $new_node->value = $value;
            //将新创建的节点，添加到初始化好的二分搜索树中
            /*
            添加操作，是初始化二分搜索树的关键操作
            因为在处理添加节点的过程之中要根据传入的数据的大小，不断的分析新节点需要存放的位置
            */
            insert_binary_search_tree($root,$new_node);
        }
        $level++;
    }
    return $root;
}

//添加节点到二分搜索树中
//思路如下:如果待添加的节点的key大于(小于)根节点，就将该节点与根节点的右(左)子节点继续比较
          //如果根节点的右(左)节点为空，也就是说根节点并不存在右(左)子节点，就将该节点放置到
          //根节点的右(左)子节点的位置上。如果存在右(左)子节点，就将该新增的节点与右(左)子节
          点继续按照上面的方式比较，直到放置到合适的位置为止 
function insert_binary_search_tree($root,$new_node){
    //新添加的节点与根节点进行比较
    //如果新节点的key与根节点的key一致的话,就使用新的节点中的value替换root节点的value
    if($root->key == $new_node->key){
        //进行替换操作
        $root->value = $new_node->value;
        return true;
    }elseif($root->key > $new_node->key){ //如果新添加的节点的key小于root节点的key
        if($root->left == null){
            $root->left = $new_node;
            return true;
        }else{
            $root = $root->left;
            insert_binary_search_tree($root,$new_node);
        }
    }else{ //如果新添加的节点的key大于root节点的key
        if($root->right == null){
            $root->right = $new_node;
            return true;
        }else{
            $root = $root->right;
            insert_binary_search_tree($root,$new_node);
        }
    }
}
//已经准备好的初始化的数组
$node_arr = [2=>"222",1=>"111",0=>"000",4=>"444",3=>"333"];
//调用初始化函数，创建二分搜索树
$result = build_binary_search_tree($node_arr);
echo "<pre/>";
//打印生成的二分搜索树
var_dump($result);

OK，上面的代码实现了二叉搜索树和打印以下内容。结果一目了然吧？

这里需要说明的是，我们插入的node_arr数组中第一个新节点就是key=2的节点，所以这个节点就是我们整个二叉搜索树的根节点。上面我们已经成功初始化了一棵二叉搜索树。这只是一小步。我们还需要实现二叉搜索树中查找元素、遍历、删除节点等功能。

(3)：找出二叉搜索树中是否存在某个键值

我们一开始就提到，使用二叉搜索树数据结构进行数据搜索的平均时间复杂度为O(logN)，对于顺序数据，它比 O(N) 更好。以下是两个查找密钥的函数。一是用来查找key是否存在，二是返回key使用的值。从功能上来说，它与PHP中的isset()函数和数组名[key]非常相似。

<?php
//查找key是否存在
function contain_key($root,$key){
    //如果递归到null,直接进行返回
    if($root == null){
        return false;
    }
    //比较当前节点的key是否和需要查询的key相等
    if($root->key == $key){
        return true;
    }elseif($root->key > $key){ //如果当前节点的key大于需要查找的key
        return contain_key($root->left,$key);
    }elseif($root->key < $key){ //如果当前节点的key小于需要查找的key
        return contain_key($root->right,$key);
    }
}

//查找key所对应的value
function get_value($root,$key){
    //如果递归到null,直接进行返回
    if($root == null){
        return false;
    }
    //比较当前节点的key是否和需要查询的key相等
    if($root->key == $key){
        return $root->value;
    }elseif($root->key > $key){ //如果当前节点的key大于需要查找的key
        return get_value($root->left,$key);
    }elseif($root->key < $key){ //如果当前节点的key小于需要查找的key
        return get_value($root->right,$key);
    }
}
?>

我们之前也提到过二叉搜索树中最大值和最小值的位置的特点。现在我们将使用上述属性来查找二分搜索元素中的最大值和最小值。功能上与 PHP 中的 max() 函数和 min() 函数非常相似。

<?php
//获取最大值
function find_max($root){
    if($root->right !=null ){
        return find_max($root->right);
    }else{
        return $root->key;
    }
}

//获取最小值
function find_min($root){
    if($root->left !=null ){
        return find_min($root->left);
    }else{
        return $root->key;
    }
}
?>

上面的代码逻辑非常简单。相信大家都能理解，这里就不详细说了。

(4): 我们已经完成了上面的数据查找。接下来我们实现二叉搜索树的遍历操作

二叉搜索树的遍历操作分为两类，一类是深度优先遍历，一类是深度优先遍历。这是第一次横切的宽度。深度优先遍历是连续递归向下遍历，而广度优先遍历是根据二叉搜索树的层次，从上到下，每次遍历一层的所有节点，然后向下搜索。人们常说的前序遍历、中序遍历、后序遍历都是深度优先遍历。三者的区别在于获取当前节点的顺序不同。下面我们用代码来实现上面的不同的遍历方法。 ？ 3)：后续pass

<?php
function tree_next($root){
    if($root != null){
        tree_next($root->left);
        tree_next($root->right);
        echo $root->value."<br/>";
    }
}
?>

打印结果如下：000.111.333.444.222

如您所见，上面的pass代码非常简单。三者的区别在于访问当前节点的顺序不同。其他的完全一样，都是递归调用。这里需要说的是，二叉搜索树的数据结构非常适合用递归的方式进行处理，这也是它的特点之一。还有很重要的一点是，中序遍历的结果是有序的。通过简单分析节点的访问路径就可以明白这一点。因此，如果要对二叉搜索树的元素进行排序，就必须使用二叉搜索树是再合适不过了。

接下来我们来说说广度优先遍历的实现。广度优先遍历的实现必须使用队列来实现。请参阅下面的代码。

<?php
function tree_level($root,&$queue){
    if($root == null){
        return;
    }else{
        echo $root->key."<br/>";
    }
    if($root->left != null){
        $queue[] = $root->left;
    }
    if($root->right != null){
        $queue[] = $root->right;
    }
    if(count($queue)>=1){
        $item = array_shift($queue);
        tree_level($item,$queue);
    }
}
$array = [];
tree_level($result,$array);
?>

基本思路是这样的：首先访问根节点，然后将根节点的两个子节点存储在array()中，然后每次从array()中取出一个未遍历到的节点，输出节点。并将该节点的左、右节点存储在array()中，以此类推，直到所有节点都没有左或右子节点。

(5)：最后我们看一下如何在二分查找中删除节点

删除节点的方法也很简单。通常我们使用哈伯德删除思想来实现这一点。基本思路是这样的：如果要删除一个节点，如果它不包含子节点，就可以直接删除。如果包含子节点，则在其子节点中查找一个节点来替换要删除的节点。这里需要注意的是，继续替换操作的子节点必须能够继续保持二叉搜索树的基本属性。那么哪个子节点可以做到这一点呢？答案是要删除的节点在 左子 树中的最大值，或者右子树中的最小值。为什么？因为根据二叉搜索树的基本性质，左子树中的所有节点都小于父节点，而右子节点中的所有节点都大于父节点。删除节点后，左子树中的最大值必须小于右子树中的所有值，然后才能替换要删除的节点。相反，也可以使用右子树中的最小值。

看下面的代码：

<?php

function find_min_node(&$root){
    if($root->left !=null ){
        return find_min_node($root->left);
    }else{
        return $root;
    }
}

function delete_node(&$root,$key){
    //根据传递进来的key,找到这个节点，并且要找到这个节点的父节点
    //如果需要删除的节点是根节点
    if($root->key == $key){
        $parent_node = $root->right;
        //根据$parent_node，查找到右子树中的最小的节点
        $node = find_min_node($parent_node);
        //将root节点进行替换
        $root->key = $node->key;
        $root->value = $node->value;
        //删除子节点
        unset($node);
        return $root;
    }else{
        //如果需要删除的节点并不是根节点
        //如果这个节点没有子节点
        if($root->left == null && $root->right == null){
            //直接删除这个节点
            //pass
            //return
        }
        //如果这个节点没有右子节点
        if($root->right ==null ){
            //获取左子树中的最大值节点
            //进行替换删除的操作
            //pass
            //return
        }else{
            //获取右子树中的最小值节点
            //进行替换删除的操作
            //pass
            //return
        }
    }
}
?>

最后我们来谈谈二叉搜索树的缺点。假设我们需要将数组[1,2,3,4,5]的元素按顺序存储在一个空的二叉搜索树中，那么就会生成一个以1为根节点、2为1、3的右子节点。一棵二叉搜索树，其中2是右子节点，4是3的右子节点，5是4的右子节点。你会发现这棵二叉搜索树的任何非叶子节点中都没有左子树。我们可以将这种情况视为二叉搜索树的最坏情况。整棵树的高度为n（平均为logN）。当执行搜索等操作时，时间复杂度将降低到O(N)。等级。对于这种情况没有解决办法。可以使用平衡树来解决。有兴趣的同学可以研究一下。

作者：codefly
链接：https://juejin.im/post/586278248d6d810065fc519c
来源：掘金
。商业转载请联系作者获取授权。非商业转载请注明出处。