文档章节

二叉树遍历的非递归算法

seandor
 seandor
发布于 2013/11/02 19:21
字数 638
阅读 41
收藏 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
博文 25
码字总数 22346
作品 0
巢湖
二叉树的遍历,深度优先遍历和广度优先遍历

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

not_in_mountain
2017/09/29
0
0
二叉树创建与遍历,递归和非递归实现

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

Nicholas_Jela
2017/09/18
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

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

泽毛
2017/12/22
0
0
Android 面试文档分享

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

泽毛
2017/11/10
0
0
非递归遍历二叉树的四种策略-先序、中序、后序和层序

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

晨曦之光
2012/04/24
260
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

python3.6 取整除法

python3.6 中取整除法运算逻辑如下: d 非零,那么商 q 满足这样的关系: a = qd + r ,且0 ≤ r n1=7//3#7 = 3*2 +1n2=-6.1//3#-7 = 3*(-3)+2'{},{}'.format(n1,n2) 从运行结果可以...

colinux
19分钟前
0
0
阶段总结——用虚拟机搭建一个高可用负载均衡集群架构

[toc] linux基本知识已经介绍完,现有一个业务需要操作,通过对这个项目的操作,可以复习、总结、巩固之前的知识点; ** 用13台虚拟机搭建一个高可用负载均衡集群架构出来,并运行三个站点,...

feng-01
22分钟前
0
0
mysql 设置utf8字符集 (CentOS)

1.查看数据库及mysql应用目前使用的编码方式 (1)链接mysql 客户端 (2)执行:status 结果: 2.修改mysql 应用的字符编码(server characterset ) (1)打开配置文件:vim /etc/mysql/my...

qimh
22分钟前
0
0
windows无法格式化u盘解决方法

1。点开始-运行-输入cmd-format f: /fs: fat32 (这里f:是指U盘所在盘符) 这个格式化会很慢 请耐心等待

大灰狼wow
34分钟前
0
0
MySql 8.0连接失败

原来,MySql 8.0.11 换了新的身份验证插件(caching_sha2_password), 原来的身份验证插件为(mysql_native_password)。而客户端工具Navicat Premium12 中找不到新的身份验证插件(caching_s...

放飞E梦想O
51分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部