<?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；**/classSqBiTree{public$SqArr;//用于存储完全二叉树节点数据元素，数据元素之间的关系用数组下标表示public$root;//表示完全二叉树的根节点/***@varint*/public$length;//表示完全二叉树当前几点的个数publicstatic$preArr;publicstatic$inArr;publicstatic$postArr;/***@param$arr*初始化*/publicfunction__construct($arr=array()){$this->SqArr=$arr;$this->root=$this->SqArr[0];$this->length=count($this->SqArr);}/***@returnbool*判断完全二叉树是否为空*/publicfunctionBiTreeEmpty(){if(!$this->root){//如果为null，0，‘’，false等都是表示空树returntrue;}else{returnfalse;}}/***@returnint|string*思路：1.如果树的节点总个数大于最大层数上一层的节点个数，并且小于等于最大层的个数，则即可找出最大层数.*/publicfunctionBiTreeDepth(){$i=1;//$i表示树的层数while($i){//此判断是根据上面关系2.k层的节点数最多为pow(2,k)-1if($this->length>pow(2,$i-1)-1&&$this->length<=pow(2,$i)-1){return$i;}$i++;}return'ERROR';}/***@param$level表示要返回的节点在第几层*@param$pos表示要返回的节点在此层的位置,$pos的值是大于等于1的整合素*@returnstring表示如果输入的层数大于最大层数，就返回Error*思路：1.如果$level大于树的最大深度并且$pos小于1，则返回错误*2.如果返回元素的下标序号<=当前层的最大下标序号，则说明存在应用元素*/publicfunctionValue($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*@returnstring*给第几层，第几个位置的节点赋予新值*思路：同上*/publicfunctionAssign($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条)，返回此元素(除了根节点)的双亲节点;*/publicfunctionParent($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*@returnstring*返回给定元素的左孩子*思路：1.找出$elem元素所在的下标；*2.根据最上面的4条，得出左孩子的下标为2*$i+1。但2*$i+1必须小于$this->length,否则就过界了*/publicfunctionLeftChild($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*@returnstring*返回给定元素的右孩子*思路：1.找出$elem元素所在的下标；*2.根据最上面的4条，得出右孩子的下标为2*$i+2。但2*$i+2必须小于$this->length,否则就过界了*/publicfunctionRightChild($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*@returnstring*返回给定元素的左兄弟*思路：1.找出$elem元素所在的下标；*2.根据最上面的6条，得出左孩子的下标为$i-1，并且$i对2取余必须为0**/publicfunctionLeftSibling($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*@returnstring*返回给定元素的右兄弟*思路：1.找出$elem元素所在的下标；*2.根据最上面的5条，得出右孩子的下标为$i+1，并且$i对2取余必须为1.并且$i+1必须小于$this->length,否则就会出界.**/publicfunctionRightSibling($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本身就是一棵树*在类中无法给自己传递参数，只能间接调用。*/publicfunctionpreTraverse(){if(!$this->root){return'Error';}$this->PreOrderTraverse($this->SqArr[0],0);returnself::$preArr;}publicfunctionPreOrderTraverse($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);}}//中序遍历publicfunctioninTraverse(){if(!$this->root){return'Error';}$this->InOrderTraverse($this->SqArr[0],0);returnself::$inArr;}publicfunctionInOrderTraverse($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);}}//后序遍历publicfunctionpostTraverse(){if(!$this->root){return'Error';}$this->PostOrderTraverse($this->SqArr[0],0);returnself::$postArr;}publicfunctionPostOrderTraverse($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;}//层序遍历publicfunctionLevelOrderTraverse(){for($i=0;$i<$this->length;$i++){$arr[]=$this->SqArr[$i];}return$arr;}}