香水电影完整版在线观看未删减|久草在线国产|欧美伊人电影|美女福利视频在线,大开色戒完整版迅雷,久艹久,动画片大尺度未删减电影

<?php

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

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

/**
 * Class BinaryTree 二叉樹(shù)
 */
class BinaryTree {

    public $data;

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

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

    /**
     * 中序遍歷
     *      左子樹(shù) -> 根節(jié)點(diǎn) -> 右子樹(shù)
     * 需要從下向上遍歷，先把左子樹(shù)壓入棧，然后逐個(gè)訪問(wèn)根節(jié)點(diǎn)和右子樹(shù)。
     *
     * @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;
    }

    /**
     * 后序遍歷
     *      左子樹(shù) -> 右子樹(shù) -> 根節(jié)點(diǎn)
     * 先把根節(jié)點(diǎn)存起來(lái)，然后依次儲(chǔ)存左子樹(shù)和右子樹(shù)。然后輸出。
     *
     * @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;
    }

    /**
     * 前序生成二叉樹(shù)
     *
     * @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;
    }
}

// 構(gòu)造二叉樹(shù)數(shù)據(jù)
$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);