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 条评论
登录 后参与评论

相关文章

来自专栏Java3y

List集合就这么简单【源码剖析】

1934
来自专栏数据结构笔记

数据结构(三):线性表

该序列中所含的元素个数叫做线性表的长度,用 n表示(n>=0)。当 n=0时,表示线性表是一个空表,即表中不包含任何数据元素。

1356
来自专栏青玉伏案

算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中...

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

java中大数类的学习

java中提供了大数类BigInteger和BigDecimal分别表示大整数类和大浮点数类,这两个类都在java.math.*包中,因此每次必须在开头处引用该...

1745
来自专栏mini188

多用多学之Java中的Set,List,Map

        很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了。ArrayList是用于实现动态数组...

1895
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

5799
来自专栏后端之路

双向队列之ArrayDeque

背景 前几篇主要介绍的都是java的普通集合,包括list,set,map等 本篇要介绍和ArrayList对应的ArrayDeque 上一篇和Deque相关的...

2838
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

892
来自专栏小鄧子的技术博客专栏

算法与数据结构(1),List

哦,对了,记得前一阵子,遇到一个问题,大概的意思就是说,不使用List集合,实现对象的增加和删除,我之所要写这篇博,是因为我现在仍然不能写出满意的结果,希望你能...

673
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

912

扫码关注云+社区