二进制搜索树[binary sorting tree] PHP版本的构造和搜索算法

Laravel / 697/0 / 8个月前发布/ 8个月前更新

二进制搜索树是一个动态查找表，可以在搜索过程中插入或删除数据.

其基础是基于二叉树，但是其特点是左子树节点的值始终小于右子树节点的值.

二叉树: 由左和右子树组成的二叉树.

分类: 倾斜树[即只有左或右子树]，完整的二叉树[节点级别是一致的]，完整的二叉树.

遍历算法: [前，中，后，层序列]遍历算法

本节将根据数据动态构建二进制排序号，并完成在树中查找节点并删除特定节点的功能！ ！ ！ ，用于创建，删除，搜索和显示树.

<?php
/**
 * Created by PhpStorm.
 * User: 1655664358@qq.com
 * Date: 2019/6/1
 * Time: 13:04
 */
/**
 * 树结点
 * Class Tree
 */
class Tree
{
    public $data;
    public $LChild;
    public $RChild;
}
/**
 * 二叉查找树【二叉排序树】
 * @param $tree
 * @param $data
 * @param $f
 * @param $temp
 * @return bool
 */
function searchBSTree(&$tree,$data,$f,&$temp)
{
    if (is_null($tree)){
        $temp = $f;
        return false;
    }
    else if ($data==$tree->data){
        $temp = $tree;
        return true;
    }
    else if ($data<$tree->data){
        return searchBSTree($tree->LChild,$data,$tree,$temp);
    }else{
        return searchBSTree($tree->RChild,$data,$tree,$temp);
    }
}
/**
 * 构建二叉排序树
 * @param $tree
 * @param $data
 */
function createBSTree(&$tree,$data)
{
    $temp = new Tree();
    if (!searchBSTree($tree,$data,null,$temp)){
        $obj = new Tree();
        $obj->data = $data;
        $obj->LChild=$obj->RChild=null;
        if (is_null($temp)){
            $tree=$obj;
        }
        elseif($data<$temp->data){
            $temp->LChild = $obj;
        }else{
            $temp->RChild = $obj;
        }
    }
}
/**
 * 删除二叉排序树某个结点
 * @param $tree
 * @return bool
 */
function removeBST(&$tree)
{
    if (is_null($tree->RChild)&&is_null($tree->LChild)){
        $tree=null;
        return true;
    }
    else if (is_null($tree->LChild)){
        $tree = $tree->RChild;
    }else if (is_null($tree->RChild)){
        $tree = $tree->LChild;
    }else{
        $temp = $tree;
        /** @var Tree $left */
        $left = $tree->LChild;
        while ($left->RChild){
            $temp = $left;
            $left = $left->RChild;
        }
        $tree->data = $left->data;//欲删除结点替换操作
        if ($temp!=$tree){
            $temp->RChild=$left->LChild;//右子树替换，因为右子树的数据已经替换为删除的结点
        }else{
            $tree->LChild=$left->LChild;//没有右子树的情况下，直接替换左子树
        }
    }
}
function deleteBSTree(&$tree,$data)
{
    if (is_null($tree)){
        return false;
    }
    elseif($data==$tree->data){
        removeBST($tree);
        return true;
    }else if($data<$tree->data){
        return deleteBSTree($tree->LChild,$data);
    }else{
        return deleteBSTree($tree->RChild,$data);
    }
}
/**
 * 前【先】序遍历
 * @param $tree
 */
function displayTree($tree)
{
    if (!is_null($tree))
    {
        fwrite(STDOUT,$tree->data."\n",10);
        displayTree($tree->LChild);
        displayTree($tree->RChild);
    }
}
(function(){
    $data = [50,25,30,12,6,20,18,15,26,27,28,29];
    $tree = null;
    for ($i=0;$i<12;$i++){
        createBSTree($tree,$data[$i]);
    }
    displayTree($tree);
    deleteBSTree($tree,50);
    fwrite(STDOUT,"************************\n",512);
    displayTree($tree);
})();

算法已过时，请您亲自检查代码^ _ ^

基础取决于二叉树

该作品采用“抄送协议”，转载时必须注明作者和本文的链接

仅来自php crud的败类

汤匙结束了

550声望

放牧专家捡拾垃圾@ Rural Grazing Co.，Ltd.

一个来自乡下的农民！技能: 农业，捡垃圾，放牧牛，割草

“ L01基本介绍”

我们将带您从零开始开发一个项目，并将其部署. 该课程教授Web开发方面的和实践技能创建二叉排序树，例如Git工作流和Laravel Mix前端工作流.

“ L03体系结构API服务器”

您将学习高级知识创建二叉排序树，例如RESTFul设计风格，PostMan的使用，OAuth流程，JWT概念和用法以及API开发.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-166827-1.html