<?php
/**
* 二叉树的顺序结构的实现比较适合实现完全二叉树和满二叉树。
* 我们可以使用数组来存储二叉树每个结点的数据元素，使用数组
* 下标表示结点之间的关系，根据完全（满）二叉树的定义，结点间的关系如下：
* 1.第i层上，结点序号范围是pow(2,i-1)-1——pow(2,i)-2；
* 2.k层的完全(满)二叉树最多有pow(2,k)-1个结点；
* 3.序号为i的结点，其双亲节点的序号为(i+1)/2-1；
* 4.序号为i的节点，其左右孩子的序号分别为2i+1和2i+2
* 5.除了根节点，序号为奇数的节点是其双亲的左孩子，它的右兄弟是它的序号加1；
* 6.除了根节点，序号为偶数的节点是其双亲的右孩子，它的左兄弟是它的序号减1；
*
*/
class SqBiTree{
public $SqArr; //用于存储完全二叉树节点数据元素，数据元素之间的关系用数组下标表示
public $root; //表示完全二叉树的根节点
/**
* @var int
*/
public $length;//表示完全二叉树当前几点的个数
public static $preArr;
public static $inArr;
public static $postArr;
/**
* @param $arr
* 初始化
*/
public function __construct($arr=array()){
$this->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;
}
}