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