二叉树遍历的非递归算法
博客专区 > seandor 的博客 > 博客详情
二叉树遍历的非递归算法
seandor 发表于4年前
二叉树遍历的非递归算法
  • 发表于 4年前
  • 阅读 39
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

摘要: python实现

以下代码实现了一个二叉树类,包含了它的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()


共有 人打赏支持
粉丝 0
博文 15
码字总数 22346
×
seandor
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: