二叉树简单实现

php - 二叉树简单实现

data = $data;
    }
}

class BtTree{
    public $btData;

    public function __construct($data=null)
    {
        $this->btData = $data;
    }

    public  function preOrderCreateBT(&$root = null){  // 引用 ， 通过 root 实例化 传值 的 $root->lChild

        $elem = array_shift($this->btData);
        if( $elem==null ){
            return;
        }elseif( $elem == '#' ){    // 当为 # 时，不再进行设置节点，退出进行下一个循环
            $root = null;
            return;
        }else{
            $root = new BtNode($elem);
            $this->preOrderCreateBT( $root->lChild );  // 递归调用
            $this->preOrderCreateBT( $root->rChild );
        }
        return $root;
    }

    /**
     * TODO:: 先序遍历二叉树
     * @param $tree     object  需要遍历的二叉树
     * @param $temp     array   一个空数组
     * @return array    array   遍历后的数组
     */
    public function printBTPreorder($tree , &$temp=[])
    {
        if( !$tree == null ){
            $temp[] = $tree->data;
            $this->printBTPreorder( $tree->lChild , $temp);
            $this->printBTPreorder( $tree->rChild , $temp);
        }else{
            return;
        }

        return $temp;
    }


    /**
     * TODO:: 中序遍历二叉树  - 先进行遍历节点再完成赋值
     * @param $tree     object  需要遍历的二叉树
     * @param $temp     array   一个空数组
     * @return array    array   遍历后的数组
     */
    public function printBTInorder($tree , &$temp=[])
    {
        if( !$tree == null ){
            $this->printBTPreorder( $tree->lChild , $temp);
            $temp[] = $tree->data;
            $this->printBTPreorder( $tree->rChild , $temp);
        }else{
            return;
        }

        return $temp;
    }


    /**
     * TODO:: 后序遍历二叉树  - 先进行遍历节点再完成赋值
     * @param $tree     object  需要遍历的二叉树
     * @param $temp     array   一个空数组
     * @return array    array   遍历后的数组
     */
    public function printBTPosorder($tree , &$temp=[])
    {
        if( !$tree == null ){
            $this->printBTPreorder( $tree->lChild , $temp);
            $this->printBTPreorder( $tree->rChild , $temp);
            $temp[] = $tree->data;
        }else{
            return;
        }

        return $temp;
    }

    function LeverOrder($root)           //层序遍历二叉树
    {
        $queue = new SplQueue();
        if ($root == null)
            return;
        else
            $queue->enqueue($root);

        while (!$queue->isEmpty()) {
            $node = $queue->bottom();
            $queue->dequeue();
            echo $node->data . " ";
            if ($node->lChild)
                $queue->enqueue($node->lChild);
            if ($node->rChild)
                $queue->enqueue($node->rChild);
        }
    }


}

$data = [
    '0' => 'A',
    '1' => 'B',
    '2' => '#',
    '3' => 'C',
    '5' => '#',
    '6' => '#',
    '7' => 'D',
];

$object = new BtTree($data);

$tree = $object->preOrderCreateBT();
$result = [];
$orderTree = $object->LeverOrder($tree);

die;

本文由 邓尘锋 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: May 4, 2019 at 11:41 am