<?php/***ClearBiTree()清空二叉树*CreateBiTree()创建二叉树*BiTreeEmpty()判断二叉树是否为空*BiTreeDepth()返回二叉树的深度*root()返回二叉树的根*Parent()返回给定元素的双亲*LeftChild()要返回左孩子的元素*RightChild()要返回右孩子的元素*LeftSibling()要返回左兄弟的元素*RightSibling()要返回右兄弟的元素*Insert($data)插入节点——递归算法*insert2($data)插入节点——非递归算法*DeleteSubtree($elem,$LR)删除某个节点的左（右）子树*PreOrderTraverse()先序遍历——递归算法*InOrderTraverse()中序遍历——递归算法*PostOrderTraverse()后序遍历——非递归算法*preOrderTraverse2()先序遍历——非递归算法*preOrderTraverse3()先序遍历——非递归算法*inOrderTraverse2()中序遍历——非递归算法*inOrderTraverse3()中序遍历——非递归算法*postOrderTraverse2()后序遍历——非递归算法*/classBiNode{public$data;public$lchild;public$rchild;publicfunction__construct($data){$this->data=$data;//节点数据$this->lchild=null;//左孩子的指针$this->rchild=null;//右孩子的指针}}classLinkBiTree{private$root;//二叉树的根节点privatestatic$preArr;//用于保存先序遍历后的数据privatestatic$inArr;//用于保存中序遍历后的数据privatestatic$postArr;//用于保存后序遍历后的数据privatestatic$levelArr;//用于保存后序遍历后的数据privatestatic$count;//记录创建二叉树结点的个数constMAX_LEVEL=2;//二叉树最大的层数publicstatic$test;publicfunction__construct(){$this->root=null;//指向根节点,初始化时为空树self::$count=0;}/***清空二叉树*/publicfunctionClearBiTree(){$this->clearTree($this->root);}/***@param$root表示树的根节点*/privatefunctionclearTree($root){if($root){if($root->lchild){$this->clearTree($root->lchild);//清空左子树}if($root->rchild){$this->clearTree($root->rchild);//清空右子树}unset($root);//释放根节点$root=null;}}//先序遍历publicfunctionPreOrderTraverse(){$this->preTraverse($this->root);returnself::$preArr;}privatefunctionpreTraverse($root){if($root){self::$preArr[]=$root->data;//先访问根节点$this->preTraverse($root->lchild);//再先序遍历左子树$this->preTraverse($root->rchild);//最后先序遍历右子树}}//中序遍历publicfunctionInOrderTraverse(){$this->inTraverse($this->root);returnself::$inArr;}privatefunctioninTraverse($root){if($root){$this->inTraverse($root->lchild);//先中序遍历左子树self::$inArr[]=$root->data;//再访问根节点$this->inTraverse($root->rchild);//最后中序遍历右子树}}//后序遍历publicfunctionPostOrderTraverse(){$this->postTraverse($this->root);returnself::$postArr;}privatefunctionpostTraverse($root){if($root){$this->postTraverse($root->lchild);//先后序遍历左子树$this->postTraverse($root->rchild);//再后序遍历右子树self::$postArr[]=$root->data;//最后再访问根节点}}//层序遍历publicfunctionLevelOrderTraverse(){for($i=1;$i<=$this->BiTreeDepth();$i++){$this->levelTraverse($this->root,$i);}returnself::$levelArr;}privatefunctionlevelTraverse($root,$level){if($root){if($level==1){self::$levelArr[]=$root->data;}$this->levelTraverse($root->lchild,$level-1);$this->levelTraverse($root->rchild,$level-1);}}//创建二叉树publicfunctionCreateBiTree(){$this->createTree($this->root);}//此处使用先序输入数据的方式来创建的privatefunctioncreateTree(&$root){$node=newBiNode(mt_rand(1,20));self::$count++;if(self::$count<=pow(2,self::MAX_LEVEL)-1){$root=$node;self::$test[]=$root->data;$this->createTree($root->lchild);$this->createTree($root->rchild);}}//判断二叉树是否为空publicfunctionBiTreeEmpty(){//if($this->root){//returnfalse;//}else{//returntrue;//}return$this->root==null;}//返回二叉树的深度publicfunctionBiTreeDepth(){return$this->treeDepth($this->root);}privatefunctiontreeDepth($root){//求左子树的深度$arr=array();$root=$this->root;$level=0;$num=0;array_push($arr,$root);while(count($arr)!=0){$root=array_shift($arr);$num++;if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}while($num>pow(2,$level-1)-1){$level++;}$level--;return$level;}//返回二叉树的根publicfunctionRoot(){return$this->root==null?'Null':$this->root->data;}//返回给定元素的双亲//此处分别使用php内部的array_push()和array_shift()这两个函数模拟队列/***@param$elem*@returnstring*返回给定元素的双亲*思路：1.使用数组队列来保存节点的指针*2.将根节点从队尾压入数组队列中*3.然后取出队首元素，使其左节点、右节点分别于给定的元素比较*4.相等的就返回上一步中取出的队首元素，否则，将此队首元素的左右节点指针分别压入队尾*5.重复第3步*/publicfunctionParent($elem){if($this->root){$arr=array();//此处数组是当队列来使用的，用于存放树（包括子树）的根指针array_push($arr,$this->root);while(count($arr)!=0){$root=array_shift($arr);if($root->lchild&&$root->lchild->data==$elem||$root->rchild&&$root->rchild->data==$elem){return$root->data;}else{if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}}}returnfalse;}/***@param$elem要返回左孩子的元素*@returnstring*思路：同上*/publicfunctionLeftChild($elem){if($this->root){$arr=array();array_push($arr,$this->root);while(count($arr)!=0){$root=array_shift($arr);if($root->data==$elem&&$root->lchild){return$root->lchild->data;}if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}}returnfalse;}/***@param$elem要返回左孩子的元素*@returnstring*思路：同上*/publicfunctionRightChild($elem){if($this->root){$arr=array();array_push($arr,$this->root);while(count($arr)!=0){$root=array_shift($arr);if($root->data==$elem&&$root->rchild){return$root->rchild->data;}if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}}returnfalse;}/***@param$elem要返回左兄弟的元素*@returnstring*/publicfunctionLeftSibling($elem){$parent=$this->Parent($elem);$leftChild=$this->LeftChild($parent);$rightChild=$this->RightChild($elem);if($rightChild==$elem&&$leftChild){return$leftChild;}return'Error';}/***@param$elem要返回右兄弟的元素*@returnstring*/publicfunctionRightSibling($elem){$parent=$this->Parent($elem);$leftChild=$this->LeftChild($parent);$rightChild=$this->RightChild($elem);if($leftChild==$elem&&$rightChild){return$rightChild;}return'Error';}/***@param$data要插入的数据*思路：1.插入的数据比树中的根(包括子树)节点小时，就放在根节点的左子树上；*2.比根节点大时，插入到右子树上；*注意：因为插入的位置不是叶节点就是只有左(或右)子树的节点，所以可以得知此递归的出口肯定是某个节点的左(或右)子树指针为空的时候。当此节点的左(右)都不为空的时候，递归就会持续下去，直到为左(右)子树有一边或全部为空的节点出现为止。*/publicfunctionInsert($data){$node=newBiNode($data);$this->insertNode($node,$this->root);}privatefunctioninsertNode($node,&$root){if(!$root){$root=$node;}else{if($node->data>$root->data){$this->insertNode($node,$root->rchild);}elseif($node->data<$root->data){$this->insertNode($node,$root->lchild);}else{return;}}}//非递归算法实现插入节点操作publicfunctioninsert2($data){$node=newBiNode($data);if(!$this->root){$this->root=$node;}else{$arr=array();array_push($arr,$this->root);while(count($arr)!=0){$root=array_shift($arr);//表示如果要插入的数据$node->data大于根节点的数据$root->data并且根节点的//左子树为空的话，那么就将$node->data赋值给左子树if($node->data<$root->data&&!$root->lchild){$root->lchild=$node;break;//此处为大于，思路与小于相似}elseif($node->data>$root->data&&!$root->rchild){$root->rchild=$node;break;}//以下两个if语句，表示如果上面的两个条件都不满足的话，那么就将跟的左右节点分别要入队列，继续循环if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}}}/***@param$elem要删除的那个节点的子树*@param$LR表示是要删除左子树还是右子树*/publicfunctionDeleteSubtree($elem,$LR){if($this->root){$arr=array();array_push($arr,$this->root);while(count($arr)!=0){$root=array_shift($arr);if($root->data==$elem&&$LR==0){$root->lchild=null;}if($root->data==$elem&&$LR==1){$root->rchild=null;}if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}}}/*以下是先序，中序，后序，层序的非递归实现算法除了层序遍历使用了队列外，其他的是利用栈来实现的思路:1.输出当前根节点2.将当前根节点的右孩子做压栈处理3.将当前节点的右孩子作为新的根节点，如果为空的话，将栈顶元素弹出作为新的根节点。4.重复1,2,3*/publicfunctionpreOrderTraverse2(){$arr=array();$root=$this->root;$arrPre=array();while($root||count($arr)!=0){$arrPre[]=$root->data;if($root->rchild){$rootR=$this->rchild;array_push($arr,$rootR);}$root=$root->lchild;if(!$root){$root=array_pop($arr);}}return$arrPre;}/**思路：1.将根节点压栈*2.弹出栈顶元素作为新的根节点*3.根据栈——先进后出的特性，先进根节点的右孩子做压栈处理，再将其左孩子做压栈处理；*4.重复2,3*注：此算法与上面的算法基本思想是相同的，只是细节处理上有所不同。*/publicfunctionpreOrderTraverse3(){$arr=array();$root=$this->root;array_push($arr,$root);while(count($arr)!=0){$root=array_pop($arr);$arrPre[]=$root->data;if($root->rchild){array_push($arr,$root->rchild);}if($root->lchild){array_push($arr,$root->lchild);}}return$arrPre;}//中序遍历算法2/**思路：1.将根节点压栈*2.将根节点的左孩子作为新的根节点,对其进行遍历*3.如果左子树遍历完毕，就将栈中的左子树结点弹出并输出，然后将此弹出结点的右孩子作为新的根节点。*4.重复1,2,3*注：此处或许有人对while循环的判断条件有所不理解。因为假如说我们只用$root是否为空来作为判断条件的话，那么当我们遍历完左子树后，程序就结束了，显然不是我们要的结果；假如我们只用栈$arr是否为空为判断条件的话，那么循环根本无法进行。**/publicfunctioninOrderTraverse2(){$arr=array();$root=$this->root;while($root||count($arr)!=0){if($root){//根指针进栈，遍历左子树.此处之所以没有在循环外先将整棵树的根节点做压栈处理，是因为，如果这样做了，那么此处对左子树的遍历就会出现死循环，因为这是的判断条件就是$root->lchild，而不是$root了，倘若还是$root那么栈中就会有两个根(整棵树)。array_push($arr,$root);$root=$root->lchild;}else{//根指针退栈，访问根节点，遍历右子树$root=array_pop($arr);$arrIn[]=$root->data;$root=$root->rchild;}}return$arrIn;}//中序遍历算法3/**思路：1.先进根做压栈处理*2.遍历左子树*3.取出栈顶元素并将输出的节点作为新的根节点*4.将根节点的右孩子压栈并重新作为新的根节点*5.重复2，3，4*注：此算法和上面的算法的整体思想是一样的*/publicfunctioninOrderTraverse3(){$arr=array();$root=$this->root;array_push($arr,$root);while(count($arr)!=0){while($root){array_push($arr,$root->lchild);$root=$root->lchild;}array_pop($arr);if(count($arr)!=0){$root=array_pop($arr);$arrIn[]=$root->data;array_push($arr,$root->rchild);$root=$root->rchild;}}return$arrIn;}//因为先序是根左右，而后序是左右根，如果将后序反转180度的话，那么顺序就是根右左.根据递归转换为非递归（栈）的方法——如果一个函数内有多于一个的递归调用那么此时，栈的进入顺序应该与递归调用的顺序相反。因为栈的特性是先进后出。//后序遍历算法2publicfunctionpostOrderTraver2(){$arr=array();$root=$this->root;array_push($arr,$root);while(count($arr)!=0){$root=array_pop($arr);$arrPost[]=$root->data;if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}returnarray_reverse($arrPost);}//层级遍历算法2publicfunctionlevelOrderTraverse2(){$arr=array();$root=$this->root;array_push($arr,$root);while(count($arr)!=0){$root=array_shift($arr);$arrLevel[]=$root->data;if($root->lchild){array_push($arr,$root->lchild);}if($root->rchild){array_push($arr,$root->rchild);}}return$arrLevel;}/**递归转非递归算法小结：*1.如果函数体内只有一个递归调用，那么直接使用栈或队列等转换即可；*2.如果有多个递归调用并且相邻，比如先序和后序遍历算法，那么转为非递归算法时，先后顺序要倒转；*3.如果有多个递归但不相邻，比如中序遍历，那么就直接按照原先的顺序依次转换即可。但如果里面依然有部分相邻，那么就按小结2操作。*4.转换时，我们应该将哪些数据放入栈中呢。根据函数调用的原理，在调用一个函数时，内存中就会开辟一个栈空间，里面保存了函数的实参，局部变量和函数调用时的返回地址等，而我们要放入栈中的就是实参和局部变量（此处的局部变量是指后序递归要用到的局部变量）。*/}