<?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() 后序遍历——非递归算法
 */
 
 
class BiNode{
    public $data;
    public $lchild;
    public $rchild;
    public function __construct($data){
        $this->data=$data; //节点数据
        $this->lchild=null;//左孩子的指针
        $this->rchild=null;//右孩子的指针
    }
}
class LinkBiTree{
    private  $root; //二叉树的根节点
    private static $preArr; //用于保存先序遍历后的数据
    private static $inArr; //用于保存中序遍历后的数据
    private static $postArr; //用于保存后序遍历后的数据
    private static $levelArr; //用于保存后序遍历后的数据
    private static $count; //记录创建二叉树结点的个数
    const MAX_LEVEL=2;//二叉树最大的层数
    public static  $test;

    public function __construct(){
        $this->root=null;//指向根节点,初始化时为空树
        self::$count=0;
    }

    /**
     * 清空二叉树
     */
    public function ClearBiTree(){
        $this->clearTree($this->root);
    }
    /**
     * @param $root 表示树的根节点
     */
    private function clearTree($root){
        if($root){
            if($root->lchild){
                $this->clearTree($root->lchild); //清空左子树
            }
            if($root->rchild){
                $this->clearTree($root->rchild); //清空右子树
            }
            unset($root); //释放根节点
            $root=null;
        }
    }
    //先序遍历
    public function PreOrderTraverse(){
        $this->preTraverse($this->root);
        return self::$preArr;
    }
    private function preTraverse($root){
        if($root){
            self::$preArr[]=$root->data; //先访问根节点
            $this->preTraverse($root->lchild);//再先序遍历左子树
            $this->preTraverse($root->rchild);//最后先序遍历右子树
        }
    }

    //中序遍历
    public function  InOrderTraverse(){
        $this->inTraverse($this->root);
        return self::$inArr;
    }
    private function inTraverse($root){
        if($root){
            $this->inTraverse($root->lchild); //先中序遍历左子树
            self::$inArr[]=$root->data; //再访问根节点
            $this->inTraverse($root->rchild);//最后中序遍历右子树
        }
    }

    //后序遍历
    public function PostOrderTraverse(){
        $this->postTraverse($this->root);
        return self::$postArr;
    }
    private function postTraverse($root){
        if($root){
            $this->postTraverse($root->lchild); //先后序遍历左子树
            $this->postTraverse($root->rchild); //再后序遍历右子树
            self::$postArr[]=$root->data; //最后再访问根节点
        }
    }

    //层序遍历
    public function LevelOrderTraverse(){
        for($i=1;$i<=$this->BiTreeDepth();$i++){
            $this->levelTraverse($this->root,$i);
        }
        return self::$levelArr;
    }
    private function levelTraverse($root,$level){
        if($root){
            if($level==1){
                self::$levelArr[]=$root->data;
            }
            $this->levelTraverse($root->lchild,$level-1);
            $this->levelTraverse($root->rchild,$level-1);
        }
    }

    //创建二叉树
    public function CreateBiTree(){
        $this->createTree($this->root);
    }
    //此处使用先序输入数据的方式来创建的
    private function createTree(&$root){
        $node=new BiNode(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);
        }
    }

    //判断二叉树是否为空
    public function BiTreeEmpty(){
//        if($this->root){
//            return false;
//        }else{
//            return true;
//        }
        return $this->root==null;
    }

    //返回二叉树的深度
    public function BiTreeDepth(){
       return $this->treeDepth($this->root);
    }
    private function treeDepth($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;
    }

    //返回二叉树的根
    public function Root(){
        return $this->root==null ? 'Null':$this->root->data;
    }

    //返回给定元素的双亲
    //此处分别使用php内部的array_push()和array_shift()这两个函数模拟队列

    /**
     * @param $elem
     * @return string
     * 返回给定元素的双亲
     * 思路：1.使用数组队列来保存节点的指针
     *       2.将根节点从队尾压入数组队列中
     *       3.然后取出队首元素，使其左节点、右节点分别于给定的元素比较
     *       4.相等的就返回上一步中取出的队首元素，否则，将此队首元素的左右节点指针分别压入队尾
     *       5.重复第3步
     */
    public function Parent($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);
                    }
                }
            }
        }
        return false;
    }

    /**
     * @param $elem 要返回左孩子的元素
     * @return string
     * 思路：同上
     */
    public function LeftChild($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);
                }
            }
        }
        return false;
    }

    /**
     * @param $elem 要返回左孩子的元素
     * @return string
     * 思路：同上
     */
    public function RightChild($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);
                }
            }
        }
        return false;
    }


    /**
     * @param $elem 要返回左兄弟的元素
     * @return string
     */
    public function LeftSibling($elem){
        $parent=$this->Parent($elem);
        $leftChild=$this->LeftChild($parent);
        $rightChild=$this->RightChild($elem);
        if($rightChild==$elem && $leftChild){
            return $leftChild;
        }
        return 'Error';
    }

    /**
     * @param $elem 要返回右兄弟的元素
     * @return string
     */
    public function RightSibling($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.比根节点大时，插入到右子树上；
     *  注意：因为插入的位置不是叶节点就是只有左(或右)子树的节点，所以可以得知此递归的出口肯定是某个节点的左(或右)子树指针为空的时候。当此节点的左(右)都不为空的时候，递归就会持续下去，直到为左(右)子树有一边或全部为空的节点出现为止。
     */
    public function Insert($data){
        $node = new BiNode($data);
        $this->insertNode($node,$this->root);
    }
    private function insertNode($node,&$root){
        if(!$root){
            $root=$node;
        }else{
            if($node->data > $root->data){
                $this->insertNode($node,$root->rchild);
            }else if($node->data < $root->data){
                $this->insertNode($node,$root->lchild);
            }else{
                return;
            }
        }
    }

    //非递归算法实现插入节点操作
    public function insert2($data){
        $node=new BiNode($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;
                    //此处为大于，思路与小于相似
                }else if($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 表示是要删除左子树还是右子树
     */
    public function DeleteSubtree($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
    */
    public function preOrderTraverse2(){
        $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
     * 注：此算法与上面的算法基本思想是相同的，只是细节处理上有所不同。
     */
    public function preOrderTraverse3(){
        $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是否为空为判断条件的话，那么循环根本无法进行。
     *
     */
    public function inOrderTraverse2(){
        $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
     * 注：此算法和上面的算法的整体思想是一样的
     */
    public function inOrderTraverse3(){
        $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度的话，那么顺序就是根右左.根据递归转换为非递归（栈）的方法——如果一个函数内有多于一个的递归调用那么此时，栈的进入顺序应该与递归调用的顺序相反。因为栈的特性是先进后出。
    //后序遍历算法2
    public function postOrderTraver2(){
        $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);
            }
        }
        return array_reverse($arrPost);
    }

    //层级遍历算法2
    public function levelOrderTraverse2(){
        $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.转换时，我们应该将哪些数据放入栈中呢。根据函数调用的原理，在调用一个函数时，内存中就会开辟一个栈空间，里面保存了函数的实参，局部变量和函数调用时的返回地址等，而我们要放入栈中的就是实参和局部变量（此处的局部变量是指后序递归要用到的局部变量）。
     */

}