文档章节

二叉树遍历的非递归算法

seandor
 seandor
发布于 2013/11/02 19:21
字数 638
阅读 41
收藏 0
点赞 0
评论 0

以下代码实现了一个二叉树类,包含了它的4种遍历方法,分别是前序遍历,中序遍历,后序遍历和层序遍历。主要是前3种遍历的非递归写法。我们知道,用递归写这三种遍历是很简单也很容易理解的,但是非递归算法却有点难度,研究非递归的算法会加深我们对这一问题的理解。那么该怎么写非递归的程序呢,对于这个问题,我们看到无论哪种遍历,先访问到的节点总是后输出,因为这个特点,所以可以采用栈来模拟;如果是先访问的先输出,则采用队列来模拟。具体到每种遍历算法,代码本身写得写比较容易看懂,因为是python,所以就像写英文文章一样。其中后序遍历估计比较难看懂,本身也不好写,应该可以优化很多,但我暂时搞不定了。

后记:算法老师提示用两个栈解决了后序遍历的问题。确实这样代码简单多了,但方法比较难想出来。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class BinaryTreeNode:

    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

class BinaryTree:

    def __init__(self):
        self.root = None

    def maketree(self, data, left, right):
        self.root = BinaryTreeNode(data, left, right)

    def create(self):
        #data = input()
        data = testdata.pop()
        if data == 0:
            return None
        else:
            self.maketree(data, BinaryTree(), BinaryTree())
            if not self.root.left.create():
                self.root.left = None
            if not self.root.right.create():
                self.root.right = None
            return True

    def is_empty(self):
        if self.root is None:
            return True
        else:
            return False

    def pre_order(self, r):
        if r.root is not None:
            print r.root.data
            if r.root.left is not None:
                self.pre_order(r.root.left)
            if r.root.right is not None:
                self.pre_order(r.root.right)
                
    def pre_order_nonrecursion(self):
        stack = []
        # initialize stack
        stack.append(self.root)
        while len(stack) != 0:
            p = stack.pop()
            print p.data
            if p.right is not None:
                stack.append(p.right.root)
            if p.left is not None:
                stack.append(p.left.root)

    def in_order(self, r):
        if r.root is not None:
            if r.root.left is not None:
                self.in_order(r.root.left)
            print r.root.data
            if r.root.right is not None:
                self.in_order(r.root.right)

    def in_order_nonrecursion(self):
        stack = []
        # initialize stack
        stack.append(self.root)
        p = self.root
        while p.left is not None:
            stack.append(p.left.root)
            p = p.left.root

        while len(stack) != 0:
            p = stack.pop()
            print p.data
            if p.right is not None:
                stack.append(p.right.root)
                p = p.right.root
                while p.left is not None:
                    stack.append(p.left.root)
                    p = p.left.root

    def post_order_nonrecursion_v1(self):
        stack_1 = []
        stack_2 = []
        stack_1.append(self.root)

        while len(stack_1) != 0:
            p = stack_1.pop()
            stack_2.append(p.data)
            if p.left is not None:
                stack_1.append(p.left.root)
            if p.right is not None:
                stack_1.append(p.right.root)
        stack_2.reverse()
        print stack_2

    def level_order(self):
        q = []
        p = self.root
        print p.data
        while p is not None:
            if p.left is not None:
                q.append(p.left.root)
            if p.right is not None:
                q.append(p.right.root)
            if len(q) == 0:
                p = None
            else:
                p = q.pop(0)
                print p.data

if __name__ == '__main__':
    # build a simplest binary tree.
    r = BinaryTree()
    r.create()

    print 'pre_order:'
    # r.pre_order(r)
    r.pre_order_nonrecursion()

    print 'in_order:'
    # r.in_order(r)
    r.in_order_nonrecursion()

    print 'post_order:'
    #r.post_order(r)
    r.post_order_nonrecursion()

    print 'level_order:'
    r.level_order()


© 著作权归作者所有

共有 人打赏支持
seandor
粉丝 0
博文 15
码字总数 22346
作品 0
巢湖
二叉树的遍历,深度优先遍历和广度优先遍历

原文:http://www.cnblogs.com/joyang/p/4860441.html 二叉树的遍历: D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。 给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一...

not_in_mountain ⋅ 2017/09/29 ⋅ 0

二叉树创建与遍历,递归和非递归实现

title: 二叉树最大的权值和 date: 2017-09-16 09:32:32 category: 默认分类 本文介绍 二叉树最大的权值和 二叉树最大的权值和 本文由在当地较为英俊的男子金天大神原创,版权所有,欢迎转载,...

Nicholas_Jela ⋅ 2017/09/18 ⋅ 0

面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛 ⋅ 2017/12/22 ⋅ 0

Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛 ⋅ 2017/11/10 ⋅ 0

非递归遍历二叉树的四种策略-先序、中序、后序和层序

遍历二叉树的递归算法,是比较容易理解的,但是非递归的循环算法不是很容易一眼看穿。下面的五个算法是参考严蔚敏的《数据结构》和USTC的张昱老师的讲义后,写下来的,部分有改动。 先序遍历...

晨曦之光 ⋅ 2012/04/24 ⋅ 0

Leetcode——二叉树常考算法整理

二叉树常考算法整理 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法项目点star呀~~ 前言 二叉树即...

qq_32690999 ⋅ 05/28 ⋅ 0

算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛 ⋅ 2017/12/18 ⋅ 0

二叉树的遍历(20)

二叉树的遍历: 一棵二叉树由三部分组成:根结点、左子树和右子树 。 本篇内容先用递归来遍历二叉树,后面再介绍用非递归的方式遍历二叉树。还有一个重要的概念就是递归归根结底也是栈的运算...

lixiyuan ⋅ 2014/04/30 ⋅ 0

递归算法转换为非递归算法的技巧

递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率。 函数调...

fnqtyr45 ⋅ 2017/11/22 ⋅ 0

满二叉树的三种周游方法之算法

二叉树的三种周游,先序,中序,后序。 这里给出完全二叉树的三种方法,其他二叉树大致思想也差不多。 递归方法就不用说了,一共几行代码。有难度的是非递归算法。 先序线序遍历就是说最先输...

abcdxyz ⋅ 2012/04/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Cube、Cuboid 和 Cube Segment

1.Cube (或Data Cube),即数据立方体,是一种常用于数据分析与索引的技术;它可以对原始数据建立多维度索引。通过 Cube 对数据进行分析,可以大大加快数据的查询效率 2.Cuboid 在 Kylin 中特...

无精疯 ⋅ 36分钟前 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 38分钟前 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 48分钟前 ⋅ 0

云计算的选择悖论如何对待?

人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云计算为...

linux-tao ⋅ 51分钟前 ⋅ 0

我的第一篇个人博客

虽然这是个技术博客,但是,我总是想写一些自己的东西,所有就大胆的在这里写下了第一篇非技术博客。技术博客也很久没有更新,个人原因。 以后自己打算在这里写一些非技术博客,可能个人观点...

Mrs_CoCo ⋅ 52分钟前 ⋅ 0

Redis 注册为 Windows 服务

Redis 注册为 Windows 服务 redis 注册为 windows 服务相关命令 注册服务 redis-server.exe –service-install redis.windows.conf 删除服务 redis-server –service-uninstall 启动服务 re......

Os_yxguang ⋅ 52分钟前 ⋅ 0

世界那么大,语言那么多,为什么选择Micropython,它的优势在哪?

最近国内MicroPython风靡程序界,是什么原因导致它这么火呢?是因为他功能强大,遵循Mit协议开源么? 错!因为使用它真的是太舒服了!!! Micropython的由来,这得益于Damien George这位伟大...

bodasisiter ⋅ 55分钟前 ⋅ 0

docker 清理总结

杀死所有正在运行的容器 docker kill $(docker ps -a -q) 删除所有已经停止的容器(docker rm没有加-f参数,运行中的容器不会删掉) docker rm $(docker ps -a -q) 删除所有未打 dangling 标...

vvx1024 ⋅ 今天 ⋅ 0

关于学习

以前学车的时候,教练说了这样的一句话:如果一个人坐在车上一直学,一直学,反而不如大家轮流着学。因为一个人一直学,就没有给自己留空间来反思和改进。而轮流着学的时候大家下来之后思考上...

mskk ⋅ 今天 ⋅ 0

压缩工具之gzip-bzip2-xz

win下常见压缩工具:rar zip 7z linux下常见压缩工具:zip gz bz2 xz tar.gz tar.bz2 tar.xz gzip 不支持目录压缩 gzip 1.txt #压缩。执行后1.txt消失,生成1.txt.gz压缩文件 gzip -d 1.txt....

ZHENG-JY ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部