SqArr=$arr;
$this->root=$this->SqArr[0];
$this->length=count($this->SqArr);
}
/**
* @return bool
* 判断完全二叉树是否为空
*/
public function BiTreeEmpty(){
if(!$this->root){ //如果为null，0，‘’，false等都是表示空树
return true;
}else{
return false;
}
}
/**
* @return int|string
* 思路：1.如果树的节点总个数大于最大层数上一层的节点个数，并且小于等于最大层的个数，则即可找出最大层数.
*/
public function BiTreeDepth(){
$i=1; //$i表示树的层数
while($i){
//此判断是根据上面关系2.k层的节点数最多为pow(2,k)-1
if($this->length>pow(2,$i-1)-1 && $this->length<=pow(2,$i)-1){
return $i;
}
$i++;
}
return 'ERROR';
}
/**
* @param $level 表示要返回的节点在第几层
* @param $pos 表示要返回的节点在此层的位置,$pos的值是大于等于1的整合素
* @return string 表示如果输入的层数大于最大层数，就返回Error
* 思路：1.如果$level大于树的最大深度并且$pos小于1，则返回错误
* 2.如果返回元素的下标序号<=当前层的最大下标序号，则说明存在应用元素
*/
public function Value($level,$pos){
if($level>$this->BiTreeDepth() && $pos<1){
return 'Error';
}
$elmpos=pow(2,$level-1)-2+$pos;//表示要返回的元素的下标
if($elmpos<=pow(2,$level)-2){
return $this->SqArr[$elmpos];
}
return 'Error';
}
/**
* @param $level
* @param $pos
* @param $value
* @return string
* 给第几层，第几个位置的节点赋予新值
* 思路：同上
*/
public function Assign($level,$pos,$value){
if($level>$this->BiTreeDepth() && $pos<1 && !$value){
return 'Error';
}
$elmpos=pow(2,$level-1)-2+$pos;//表示要返回的元素的下标
if($elmpos<=pow(2,$level)-2){
$this->SqArr[$elmpos]=$value;
}
}
/**
* @param $elem 表示给定要找双亲的元素
* 返回给定元素的双亲
* 思路：1.找出$elem元素所在的下标；
* 2.根据子节点与双亲节点之间的关系(最上面的第3条)，返回此元素(除了根节点)的双亲节点;
*/
public function Parent($elem){
//因为下标为0的节点为根节点，所以要从1开始计算
for($i=1;$i<$this->length;$i++){
if($this->SqArr[$i]==$elem){
return $this->SqArr[($i+1)/2-1];
}
}
return 'Error';
}
/**
* @param $elem
* @return string
* 返回给定元素的左孩子
* 思路：1.找出$elem元素所在的下标；
* 2.根据最上面的4条，得出左孩子的下标为2*$i+1。但2*$i+1必须小于$this->length,否则就过界了
*/
public function LeftChild($elem){
for($i=0;$i<$this->length;$i++){
if($this->SqArr[$i]==$elem && $i*2+1<$this->length){
return $this->SqArr[$i*2+1];
}
}
return 'Error';
}
/**
* @param $elem
* @return string
* 返回给定元素的右孩子
* 思路：1.找出$elem元素所在的下标；
* 2.根据最上面的4条，得出右孩子的下标为2*$i+2。但2*$i+2必须小于$this->length,否则就过界了
*/
public function RightChild($elem){
for($i=0;$i<$this->length;$i++){
if($this->SqArr[$i]==$elem && $i*2+2<$this->length){
return $this->SqArr[$i*2+2];
}
}
return 'Error';
}
/**
* @param $elem
* @return string
* 返回给定元素的左兄弟
* 思路：1.找出$elem元素所在的下标；
* 2.根据最上面的6条，得出左孩子的下标为$i-1，并且$i对2取余必须为0
*
*/
public function LeftSibling($elem){
for($i=0;$i<$this->length;$i++){
if($this->SqArr[$i]==$elem && $i%2==0){
return $this->SqArr[$i-1];
}
}
return 'Error';
}
/**
* @param $elem
* @return string
* 返回给定元素的右兄弟
* 思路：1.找出$elem元素所在的下标；
* 2.根据最上面的5条，得出右孩子的下标为$i+1，并且$i对2取余必须为1.并且$i+1必须小于$this->length,否则就会出界.
*
*/
public function RightSibling($elem){
for($i=0;$i<$this->length;$i++){
if($this->SqArr[$i]==$elem && $i%2 && $i+1<$this->length){
return $this->SqArr[$i+1];
}
}
return 'Error';
}
/**
* 先序遍历
* 注：此处之所以使用两个方法来完成是因为this->SqArr本身就是一棵树
* 在类中无法给自己传递参数，只能间接调用。
*/
public function preTraverse(){
if(!$this->root){
return 'Error';
}
$this->PreOrderTraverse($this->SqArr[0],0);
return self::$preArr;
}
public function PreOrderTraverse($root,$id){
if(!$root){
return 'Error';
}
self::$preArr[]=$root;
if($id*2+1<$this->length && $root){
$this->PreOrderTraverse($this->SqArr[$id*2+1],$id*2+1);
}
if($id*2+2<$this->length && $root){
$this->PreOrderTraverse($this->SqArr[$id*2+2],$id*2+2);
}
}
//中序遍历
public function inTraverse(){
if(!$this->root){
return 'Error';
}
$this->InOrderTraverse($this->SqArr[0],0);
return self::$inArr;
}
public function InOrderTraverse($root,$id){
if(!$root){
return 'Error';
}
if($id*2+1<$this->length && $root){
$this->InOrderTraverse($this->SqArr[$id * 2 + 1], $id * 2 + 1);
}
self::$inArr[]=$root;
if($id*2+2<$this->length && $root){
$this->InOrderTraverse($this->SqArr[$id * 2 + 2], $id * 2 + 2);
}
}
//后序遍历
public function postTraverse(){
if(!$this->root){
return 'Error';
}
$this->PostOrderTraverse($this->SqArr[0],0);
return self::$postArr;
}
public function PostOrderTraverse($root,$id){
if(!$root){
return 'Error';
}
if($id*2+1<$this->length && $root){
$this->PostOrderTraverse($this->SqArr[$id * 2 + 1], $id * 2 + 1);
}
if($id*2+2<$this->length && $root){
$this->PostOrderTraverse($this->SqArr[$id * 2 + 2], $id * 2 + 2);
}
self::$postArr[]=$root;
}
//层序遍历
public function LevelOrderTraverse(){
for($i=0;$i<$this->length;$i++){
$arr[]=$this->SqArr[$i];
}
return $arr;
}
}
新闻标题：数据结构之完全二叉树——顺序存储结构（php代码实现）
文章链接：
http://bzwzjz.com/article/gdiocd.html
