PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三)

——动态查找表(二叉排序树)

(原创内容,转载请注明来源,谢谢)

一、概念

1、动态查找表特点

当对动态查找表进行查找时,如果查找成功,会返回查找结果;如果查找失败,会对动态查找表插入查找结果,并且根据各类动态查找表的性质,对表进行动态调整。

2、二叉排序树(又称二叉查找树)

二叉排序树或者是一棵空树,或者满足以下特性:

1)若左子树非空,则左子树的所有节点小于根节点;

2)若右子树非空,则右子树的所有节点大于根节点;

3)左子树和右子树及其子树也都是二叉排序树。

二、二叉排序树

1、查找

二叉排序树的查找较为简单,从根节点开始查找,如果key大于根节点,则到其右子树进行查找,否则到其左子树进行查找。

根据二叉排序树的性质,对二叉排序树进行中序遍历,则可以得到一个从小到大的线性序列。

2、插入

二叉排序树的插入都是在叶子节点之后,当查找不成功时,会在遍历到的最后一个节点的左边或者右边插入节点。

3、删除

1)当删除的是叶子节点时,只需要改变父节点的指向(指为null)。

2)当删除的不是叶子节点时,如果其只有左子树或右子树的一边,则让子树接到父节点上(根据大小比较判断是父节点的左子树还是右子树)。

3)当删除的不是叶子节点,且同时有左子树和右子树,则根据中序遍历的结果,将左右子树分别接到其前驱或后继上。

4、二叉排序树图

5、二叉排序树生成与查询

二叉排序树属于动态查找表,因此生成的过程也就是查找和插入的过程。当一开始没有节点时,查找即插入节点,而后根据查找,逐步进行插入的过程。

二叉排序树的插入和遍历的结果如下:

源代码如下:

         <?php
class Node{
         public$index;
         public$data;
         public$left;
         public$right;
         public$parent;
}
class BinarySearchTree{
         private$tree = null;
         //构造二叉查找树
         //arrNodes= array(array($index, $value), array($index2, $value2)...)
         publicfunction generate($arrNodes){
                   if(empty($arrNodes)){
                            returnfalse;
                   }
                   $arrInsert= array();//记录插入的结果
                   $arrSearch= array();//记录查询的结果
                   foreach($arrNodesas $node){
                            $arr= $this->searchNode($node);
                            if($arr[0]){
                                     array_push($arrSearch,array($arr[1], $arr[2]));
                            }else{
                                     array_push($arrInsert,array($arr[1], $arr[2]));
                            }
                   }
                   returnarray($arrSearch, $arrInsert);
         }
         //查找结点,如果没有则插入
         //返回array(bool,int,string)
         //第一个参数如果是true表示查找到,如果是false表示没查到调用了插入函数
         //第二个参数是index,第三个参数是data
         publicfunction searchNode($node){
                   $index= $node[0];
                   $data= $node[1];            
                   if(null== $this->tree){
                            $this->tree= new Node();
                            $this->tree->index= $index;
                            $this->tree->data= $data;
                            returnarray(false, $index, $data);
                   }
                   $curNode= $this->tree;
                   while(null!= $curNode){
                            if($index== $curNode->index){
                                     //如果等于,则查到,返回查询结果
                                     returnarray(true, $curNode->index, $curNode->data);
                            }
                            if($index> $curNode->index){
                                     //如果查询的点比节点大,则往右边查,如果没有右子树,则插入,否则查右子树
                                     if(null== $curNode->right){
                                               $this->insertNode($curNode,$index, $data, 'right');                                         
                                               returnarray(false, $index, $data);
                                     }else{
                                               $curNode= $curNode->right;
                                               continue;
                                     }                          
                            }
                            if($index< $curNode->index){
                                     //如果查询的点比节点小,则往左边查,如果没有左子树,则插入,否则查左子树
                                     if(null== $curNode->left){
                                               $this->insertNode($curNode,$index, $data, 'left');                                   
                                               returnarray(false, $index, $data);
                                     }else{
                                               $curNode= $curNode->left;
                                               continue;
                                     }                          
                            }                          
                   }
         }
         //插入节点
         publicfunction insertNode(Node &$curNode, $index, $data, $pos){
                   if('left'== $pos){
                            $curNode->left= new Node();
                            $curNode->left->data= $data;
                            $curNode->left->index= $index;
                   }else{
                            $curNode->right= new Node();
                            $curNode->right->data= $data;
                            $curNode->right->index= $index;                    
                   }
         }
         //中序遍历二叉树
         publicfunction centerSearch(){
                   if(null== $this->tree || !($this->tree instanceof Node)){
                            returnfalse;
                   }
                   $resultStack= array();
                   $nodeStack= array();
                   $centerNode= $this->tree;
                   while(!empty($nodeStack)|| null != $centerNode){
                            while(null!= $centerNode){
                                     array_push($nodeStack,$centerNode);
                                     $centerNode= $centerNode->left;
                            }
                            $centerNode= array_pop($nodeStack);
                            array_push($resultStack,array($centerNode->index, $centerNode->data));
                            $centerNode= $centerNode->right;
                   }
                   return$resultStack;
         }
}
$binarySearchTree = new BinarySearchTree();
$arr =$binarySearchTree->generate(array(array(50, 'a'), array(40, 'b'), array(60,'c'), array(30, 'd'), array(45, 'e'), array(70, 'f'), array(65, 'g')));
echo '共计插入的节点:';
print_r($arr[1]);
echo '<br />共计查找到的节点:';
print_r($arr[0]);
echo '<br />';
$arr =$binarySearchTree->centerSearch();
echo '中序遍历的结果:';
print_r($arr);

——written by linhxx 2017.07.14

相关阅读:

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python疯子

python数据清洗

数据的质量直接关乎最后数据分析出来的结果,如果数据有错误,在计算和统计后,结果也会有误。 所以在进行数据分析前,我们必须对数据进行清洗。需要考虑数据是否需要修...

722
来自专栏Python小屋

Python标准库base64用法简介

base64模块提供了大量函数用来把二进制数据编码为可打印的ASCII字符,以及将其解码为二进制数据。提供了RFC3548中Base16、Base32、Base...

3568
来自专栏数据结构与算法

BZOJ2783: [JLOI2012]树(树上前缀和+set)

Description 数列 提交文件:sequence.pas/c/cpp 输入文件:sequence.in 输出文件:sequence.out 问题描述:...

2704
来自专栏aCloudDeveloper

经典排序之 选择排序

Author: bakari  Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

1968
来自专栏我的博客

哈希算法

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。 通常用于加密和查找 加密...

3258
来自专栏蜉蝣禅修之道

关于Havel算法判断度数序列能否构成简单图的思考

1572
来自专栏赵俊的Java专栏

落单的数

1632
来自专栏软件开发 -- 分享 互助 成长

C++STL 之排列

固然我们可以自己使用递归编写全排列程序,但是既然STL里面已将有了这个功能为什么不直接用呢,下面就写一下直接使用C++ STL生成全排序的程序 函数名:next...

1847
来自专栏决胜机器学习

PHP数据结构(二十二) ——快速排序

PHP数据结构(二十二)——快速排序 (原创内容,转载请注明来源,谢谢) 一、概述 前面的插入排序,都是以移动的方式进行排序。快速排序,则是以交换的方式进行...

3529
来自专栏数据结构与算法

计算(calc.cpp)

计算(calc.cpp) 【问题描述】 小明在你的帮助下,破密了Ferrari设的密码门,正要往前走,突然又出现了一个密码门,门上有一个算式,其中只有“(”,“...

34210

扫描关注云+社区