文档章节

二叉树遍历的非递归算法

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

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 入门 - 进阶篇(4)- REST访问(RestTemplate)

经常需要发送一个GET/POST请求到其他系统(REST API),通过JDK自带的HttpURLConnection、Apache HttpClient、Netty 4、OkHTTP 2/3都可以实现。 HttpClient的使用:http://rensanning.iteye.c...

onedotdot
16分钟前
1
0
Wi-Fi也有版本号了!

据Solidot消息,行业组织 Wi-Fi 联盟宣布当前的版本 Wi-Fi 802.11ac 重命名为 Wi-Fi 5,而下一个版本 802.11ax 重命名为 Wi-Fi 6,之前的版本 802.11n 改名为 Wi-Fi 4。 Wi-Fi 标准之前使用单...

linux-tao
18分钟前
3
0
项目经验不丰富、技术不突出的程序员怎么打动面试官?

前言 相信不少的程序员都有过类似的困惑:如果我没有大型的项目经历,也不能靠技术征服面试官,那我要怎么才能给面试官留下一个好印象呢? 按照本人的面试经验来说,面试主要看几点:项目经验...

Mamba1
28分钟前
2
0
MyBatis 源码分析----MyBatis 整体架构概要说明

MyBatis整体架构 MyBatis的整体架构分为三层1:基础支持层,2:核心处理层,3:接口层 1:基础支持层: 1-1反射模块: 该模块对Java 原生的反射进行了良好的封装,提供了更加简洁易用的API ,...

西瓜1994
34分钟前
6
0
如何让 J2Cache 在多种编程语言环境中使用

现在的系统是越来越复杂了,不仅仅是功能复杂,系统结构也非常复杂,而且经常在一个系统里包含几种不同语言编写的子系统。例如用 JavaScript 做前端开发、用 Java/PHP 等等做后端,C/C++/Go ...

红薯
35分钟前
44
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部