PHP数据结构（13）-动态查找表（二进制排序树）

1. 动态查询表的功能

搜索动态查找表时，如果搜索成功，将返回搜索结果. 如果搜索失败，则将搜索结果插入动态查找表中，并根据各种类型的动态查找表的性质对其进行动态调整.

2. 二进制排序树（也称为二进制搜索树）

二进制排序树要么是空树，要么具有以下特征:

1）如果左子树不为空，则左子树的所有节点都小于根节点；

2）如果右子树不为空，则右子树的所有节点都大于根节点；

3）左右子树及其子树也是二进制排序树.

1. 查找

二叉排序树搜索相对简单，从根节点开始，如果关键字大于根节点，则搜索右子树，否则搜索左子树.

根据二进制排序树的性质，通过对二进制排序树执行中阶遍历，可以获得从小到大的线性序列.

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);

-由linhxx撰写2017.07.14

此分享来自公共微通道号-获奖的机器学习（phpthinker），作者: linhxx

文本中详细说明了原始来源和转载的信息. 如果有任何侵权，请联系yunjia_community@tencent.com将其删除.

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

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