python数据结构之二叉树的遍历实例

 更新时间:2014年04月29日 09:06:02   作者:   我要评论
这篇文章主要介绍了python数据结构之二叉树的递归遍历实例,需要的朋友可以参考下

遍历方案
    从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
    1).访问结点本身(N)
    2).遍历该结点的左子树(L)
    3).遍历该结点的右子树(R)

有次序:
    NLR、LNR、LRN

遍历的命名

    根据访问结点操作发生位置命名:
NLR:前序遍历(PreorderTraversal亦称(先序遍历))  ——访问结点的操作发生在遍历其左右子树之前。
LNR:中序遍历(InorderTraversal)  ——访问结点的操作发生在遍历其左右子树之中(间)。
LRN:后序遍历(PostorderTraversal)    ——访问结点的操作发生在遍历其左右子树之后。

注:由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

遍历算法

1).先序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
a.访问根结点
b.遍历左子树
c.遍历右子树

2).中序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
a.遍历左子树
b.访问根结点
c.遍历右子树

3).后序遍历得递归算法定义:
若二叉树非空,则依次执行如下操作:
a.遍历左子树
b.遍历右子树
c.访问根结点

一、二叉树的递归遍历:

复制代码 代码如下:

# -*- coding: utf - 8 - *-

class TreeNode(object):

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

     
class BTree(object):

    def __init__(self, root=0):
        self.root = root

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

    def preorder(self, treenode):
        '前序(pre-order,NLR)遍历'
        if treenode is 0:
            return
        print treenode.data
        self.preorder(treenode.left)
        self.preorder(treenode.right)

    def inorder(self, treenode):
        '中序(in-order,LNR'
        if treenode is 0:
            return
        self.inorder(treenode.left)
        print treenode.data
        self.inorder(treenode.right)

    def postorder(self, treenode):
        '后序(post-order,LRN)遍历'
        if treenode is 0:
            return
        self.postorder(treenode.left)
        self.postorder(treenode.right)
        print treenode.data

     
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

bt = BTree(root)

print u'''

#生成的二叉树

# ------------------------
#          root
#       7        8
#     6
#   2   5
# 1    3 4
#
# -------------------------

'''
print '前序(pre-order,NLR)遍历 :\n'
bt.preorder(bt.root)

print '中序(in-order,LNR) 遍历 :\n'
bt.inorder(bt.root)

print '后序(post-order,LRN)遍历 :\n'
bt.postorder(bt.root)


二、.二叉树的非递归遍历

下面就用非递归的方式实现一遍。主要用到了 stack 和 queue维护一些数据节点:

复制代码 代码如下:

# -*- coding: utf - 8 - *-

     
class TreeNode(object):

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

     
class BTree(object):

    def __init__(self, root=0):
        self.root = root

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

    def preorder(self, treenode):
        '前序(pre-order,NLR)遍历'
        stack = []
        while treenode or stack:
            if treenode is not 0:
                print treenode.data
                stack.append(treenode)
                treenode = treenode.left
            else:
                treenode = stack.pop()
                treenode = treenode.right

    def inorder(self, treenode):
        '中序(in-order,LNR) 遍历'
        stack = []
        while treenode or stack:
            if treenode:
                stack.append(treenode)
                treenode = treenode.left
            else:
                treenode = stack.pop()
                print treenode.data
                treenode = treenode.right

    # def postorder(self, treenode):
    #     stack = []
    #     pre = 0
    #     while treenode or stack:
    #         if treenode:
    #             stack.append(treenode)
    #             treenode = treenode.left
    #         elif stack[-1].right != pre:
    #             treenode = stack[-1].right
    #             pre = 0
    #         else:
    #             pre = stack.pop()
    #             print pre.data

    def postorder(self, treenode):
        '后序(post-order,LRN)遍历'
        stack = []
        queue = []
        queue.append(treenode)
        while queue:
            treenode = queue.pop()
            if treenode.left:
                queue.append(treenode.left)
            if treenode.right:
                queue.append(treenode.right)
            stack.append(treenode)
        while stack:
            print stack.pop().data

    def levelorder(self, treenode):
        from collections import deque
        if not treenode:
            return
        q = deque([treenode])
        while q:
            treenode = q.popleft()
            print treenode.data
            if treenode.left:
                q.append(treenode.left)
            if treenode.right:
                q.append(treenode.right)

     
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')

     
bt = BTree(root)

print u'''

#生成的二叉树

# ------------------------
#          root
#       7        8
#     6
#   2   5
# 1    3 4
#
# -------------------------

'''
print '前序(pre-order,NLR)遍历 :\n'
bt.preorder(bt.root)

print '中序(in-order,LNR) 遍历 :\n'
bt.inorder(bt.root)

print '后序(post-order,LRN)遍历 :\n'
bt.postorder(bt.root)

print '层序(level-order,LRN)遍历 :\n'
bt.levelorder(bt.root)

相关文章

  • python三大神器之fabric使用教程

    python三大神器之fabric使用教程

    fabric 是一个python包 是一个基于ssh的部署工具包,这篇文章主要介绍了python三大神器之fabric,需要的朋友可以参考下
    2019-06-06
  • Django 导出项目依赖库到 requirements.txt过程解析

    Django 导出项目依赖库到 requirements.txt过程解析

    这篇文章主要介绍了Django 导出项目依赖库到 requirements.txt过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
    2019-08-08
  • 10分钟教你用Python实现微信自动回复功能

    10分钟教你用Python实现微信自动回复功能

    今天,我们就来用Python实现微信的自动回复功能吧,并且把接收到的消息统一发送到文件助手里面,方便统一查看。感兴趣的朋友跟随小编一起看看吧
    2018-11-11
  • python 获取网页编码方式实现代码

    python 获取网页编码方式实现代码

    这篇文章主要介绍了python 获取网页编码方式实现代码的相关资料,需要的朋友可以参考下
    2017-03-03
  • 对Python通过pypyodbc访问Access金沙国际官网的方法详解

    对Python通过pypyodbc访问Access金沙国际官网的方法详解

    今天小编就为大家分享一篇对Python通过pypyodbc访问Access金沙国际官网的方法详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-10-10
  • 利用Python获取操作系统信息实例

    利用Python获取操作系统信息实例

    作为一个运维人员,经常需要获取系统的的各种信息,使用python会很方便帮助获得,这篇文章运用实例告诉大家如何利用Python来获取操作系统的信息,有需要的可以参考借鉴。
    2016-09-09
  • Python3.2中的字符串函数学习总结

    Python3.2中的字符串函数学习总结

    这篇文章主要介绍了Python3.2中的字符串函数学习总结,本文讲解了格式化类方法、查找 & 替换类方法、拆分 & 组合类方法等内容,需要的朋友可以参考下
    2015-04-04
  • django金沙国际官网migrate失败的解决方法解析

    django金沙国际官网migrate失败的解决方法解析

    这篇文章主要介绍了django金沙国际官网migrate失败的解决方法解析,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
    2018-02-02
  • Django重置migrations文件的方法步骤

    Django重置migrations文件的方法步骤

    这篇文章主要介绍了Django重置migrations文件的方法步骤,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2019-05-05
  • Python中字符串的处理技巧分享

    Python中字符串的处理技巧分享

    这篇文章给大家分享了Python中字符串的处理技巧,包括拆分含有多种分隔符的字符串、判断字符串a是否以字符串b开头或结尾、调整字符串中文本的格式已经将多个小字符串拼接成一个大的字符串等,感兴趣的朋友们可以通过阅读下文来学习。
    2016-09-09

最新评论