PHP – 建立二叉树 – 反转二叉树


一、先建立树节点类:

/**
 * 二叉树节点
 * Class of TreeNode
 */
class TreeNode
{
    // 子左节点
    public $left = null;

    // 子右节点
    public $right = null;

    // 节点值
    public $value = null;

    public function __construct ($val)
    {
        $this->value = $val;
    }
}

二、创建二叉树处理类:

require_once 'TreeNode.php';

/* 
 * 二叉树遍历
 * Class of TreeTraverse
 */
class TreeTraverse
{
    // 二叉树
    private $tree = null;

    // 二叉树前序遍历数组
    private $treeString = [1, 2, 3, '#', 4, '#', '#', 5, 6, '#', '#', '#', 7, 8, '#', '#', 9, 10, '#', '#', 11, '#', '#'];

    /**
     * 创建文件夹中图片里的二叉树
     * @param TreeNode $root
     * @return TreeNode
     */
    public function createTree (TreeNode $root = null)
    {
        $val = array_shift($this->treeString);
        if ($val == '#') {
            return null;
        }
        $root = new TreeNode($val);
        echo("输入的数据为:" . $val . '<br/>');
        $root->left = $this->createTree($root->left);
        $root->right = $this->createTree($root->right);
        return $root;
    }

    // 原二叉树的层次遍历数组
    private $treeStringTmp = [];
    /**
     * 层次遍历二叉树
     * @param TreeNode $root
     */
    public function levelTraverse (TreeNode $root = null)
    {
        if ($root == null) {
            return;
        }
        array_push($this->treeStringTmp, $root->value);
        $this->levelTraverseRecursion($root);
    }

    /**
     * 层次遍历二叉树递归
     * @param TreeNode $root
     */
    public function levelTraverseRecursion (TreeNode $root = null)
    {
        if ($root->left) {
            array_push($this->treeStringTmp, $root->left->value);
            $this->levelTraverseRecursion($root->left);
        }
        // 打出空子节点用#代替
        else {
            array_push($this->treeStringTmp, '#');
        }
        if ($root->right) {
            array_push($this->treeStringTmp, $root->right->value);
            $this->levelTraverseRecursion($root->right);
        }
        // 打出空子节点用#代替
        else {
            array_push($this->treeStringTmp, '#');
        }
        if (!$root->left && !$root->right) {
            return null;
        }
    }

    /**
     * 得到二叉树的镜像  —— 递归的方式
     * @param TreeNode $root
     */
    public function mirrorRecursive (TreeNode $root = null)
    {
        if($root == null) {
            return;
        }
        if (!$root->left && !$root->right) {
            return null;
        }
        // 左右子节点调换
        $temp = $root->left;
        $root->left = $root->right;
        $root->right = $temp;
        $this->mirrorRecursive($root->left);
        $this->mirrorRecursive($root->right);
    }

    /**
     * 得到二叉树的镜像 —— 不使用递归
     * @param TreeNode $root
     */
    public function mirrorNotRecursive (TreeNode $root = null)
    {
        if($root == null) {
            return null;
        }
        // 队列数组
        $queue = array();
        array_push($queue, $root);
        // 遍历队列
        while(! empty($queue)){
            // 删除第一个元素
            $node = array_shift($queue);

            // 左右子节点调换
            $temp = $node->left;
            $node->left = $node->right;
            $node->right = $temp;
            if($node->left) {
                array_push($queue, $node->left);
            }
            if($node->right) {
                array_push($queue, $node->right);
            }
        }
        return $root;
    }

    /**
     * 执行二叉树操作
     */
    public function main ()
    {
        $root = null;
        echo '<h3>"原二叉树的节点值"</h3>';
        $root = $this->createTree($root);

        // 层次遍历(先序遍历)二叉树
        $this->levelTraverse($root);
        echo '<h3>"原二叉树的层次遍历(先序遍历)"</h3>';
        echo implode(' ', $this->treeStringTmp);

        // 递归反转二叉树镜像
        $this->mirrorRecursive($root);
        // 层次遍历(先序遍历)二叉树
        $this->treeStringTmp = [];
        $this->levelTraverse($root);
        echo '<h3>"递归反转输出该二叉树的镜像"</h3>';
        echo implode(' ', $this->treeStringTmp);

        // 非递归反转二叉树镜像
        $root = $this->mirrorNotRecursive($root);
        // 层次遍历(先序遍历)二叉树
        $this->treeStringTmp = [];
        $this->levelTraverse($root);
        echo '<h3>"非递归反转输出该二叉树的镜像"</h3>';
        echo implode(' ', $this->treeStringTmp);
    }
}

三、建立入口文件:

require_once 'TreeTraverse.php';

$treeTraverse = new TreeTraverse();
$treeTraverse->main();

执行后的结果截图:

参考来源https://www.cnblogs.com/Leo_wl/p/7559772.html#undefined