球探比分网-足球即时比|球探比分足球即时比分手机版捷报|球探足球比分旧版本卡塔尔|188bet足球,计算器竞彩足球胜平负玩法,西超杯赛程比分排名,竞彩足球胜平负开奖结果公告

<?php

/**
 * Class Node 節(jié)點
 */
class Node {
    public $value;
    public $left;
    public $right;

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

/**
 * Class BinaryTree 二叉樹
 */
class BinaryTree {

    public $data;

    public function __construct($data = []) {
        $this->data = $data;
    }

    /**
     * 前序遍歷：
     *      根節(jié)點 -> 左子樹 -> 右子樹
     * 利用棧先進后出的特性，先訪問根節(jié)點，再把右子樹壓入，再壓入左子樹。
     * 這樣取出的時候是先取出左子樹，最后取出右子樹。
     *
     * @param $tree
     *
     * @return array
     */
    public function pre_order($tree) {
        $stack = [];
        $output = [];
        array_push($stack, $tree);
        while (!empty($stack)) {
            $center_node = array_pop($stack);
            // 先輸出根節(jié)點
            $output[] = $center_node->value;
            if ($center_node->right) {
                // 壓入右子樹
                array_push($stack, $center_node->right);
            }
            if ($center_node->left) {
                // 壓入左子樹
                array_push($stack, $center_node->left);
            }
        }
        return $output;
    }

    /**
     * 前序遍歷（遞歸）
     *
     * @param $tree
     * @param $output
     *
     * @return array|void
     */
    public function pre_order_recursive($tree, &$output) {
        if (is_null($tree)) return; else {
            $output[] = $tree->value;
            $this->pre_order_recursive($tree->left, $output);
            $this->pre_order_recursive($tree->right, $output);
        }
        return $output;
    }

    /**
     * 中序遍歷
     *      左子樹 -> 根節(jié)點 -> 右子樹
     * 需要從下向上遍歷，先把左子樹壓入棧，然后逐個訪問根節(jié)點和右子樹。
     *
     * @param $tree
     *
     * @return array
     */
    public function in_order($tree) {
        $stack = [];
        $output = [];
        $center_node = $tree;
        while (!empty($stack) || $center_node != null) {
            while ($center_node) {
                array_push($stack, $center_node);
                $center_node = $center_node->left;
            }

            $center_node = array_pop($stack);
            if ($center_node->value) {
                $output[] = $center_node->value;
            }
            $center_node = $center_node->right;
        }
        return $output;
    }

    /**
     * 中序遍歷（遞歸）
     *
     * @param $tree
     * @param $output
     *
     * @return array|void
     */
    public function in_order_recursive($tree, &$output) {
        if (is_null($tree)) return; else {
            $this->in_order_recursive($tree->left, $output);
            $output[] = $tree->value;
            $this->in_order_recursive($tree->right, $output);
        }
        return $output;
    }

    /**
     * 后序遍歷
     *      左子樹 -> 右子樹 -> 根節(jié)點
     * 先把根節(jié)點存起來，然后依次儲存左子樹和右子樹。然后輸出。
     *
     * @param $tree
     *
     * @return array
     */
    public function tail_order($tree) {
        $stack = [];
        $output = [];
        array_push($stack, $tree);
        while (!empty($stack)) {
            $center_node = array_pop($stack);
            $output[] = $center_node->value;
            if ($center_node->left) {
                array_push($stack, $center_node->left);
            }
            if ($center_node->right) {
                array_push($stack, $center_node->right);
            }
        }
        return array_reverse($output);
    }

    /**
     * 后序遍歷（遞歸）
     *
     * @param $tree
     * @param $output
     *
     * @return array|void
     */
    public function tail_order_recursive($tree, &$output) {
        if (is_null($tree)) return; else {
            $this->tail_order_recursive($tree->left, $output);
            $this->tail_order_recursive($tree->right, $output);
            $output[] = $tree->value;
        }
        return $output;
    }

    /**
     * 前序生成二叉樹
     *
     * @param $root
     *
     * @return Node|string|void
     */
    public function pre_order_create(&$root) {
        $data = array_shift($this->data);
        if (is_null($data)) return; elseif ($data == '#') return $root = null;
        else {
            $root = new Node($data);
            $this->pre_order_create($root->left);
            $this->pre_order_create($root->right);
        }
        return $root;
    }
}

// 構造二叉樹數據
$data = array(0 => 'A',
              1 => 'B',
              2 => '#',
              3 => 'D',
              4 => '#',
              5 => '#',
              6 => 'C',
              7 => '#',
              8 => '#',);

$bt = new BinaryTree($data);
// 前序生成
$tree = $bt->pre_order_create($root);

// 前序遍歷
// $output = $bt->pre_order($tree);
// $output = $bt->pre_order_recursive($tree, $output);

// 中序遍歷
// $output = $bt->in_order($tree);
// $output = $bt->in_order_recursive($tree, $output);

// 后序遍歷
// $output = $bt->tail_order($tree);
// $output = $bt->tail_order_recursive($tree, $output);

print_r($tree);