开发者社区> 罗兵> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

python 二叉树

简介: class Node(object): def __init__(self, data=None, left=None, right=None): self.data = data self.
+关注继续查看
class Node(object):
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BTree(object):
    def __init__(self, root=None):
        self.root = root

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

    # 先序遍历(递归,recursion)
    def pre_order(self, node):
        if node is None:
            return
        print(node.data)
        self.pre_order(node.left)
        self.pre_order(node.right)

    # 中序遍历(递归)
    def in_order(self, node):
        if node is None:
            return
        self.in_order(node.left)
        print(node.data)
        self.in_order(node.right)

    # 后序遍历(递归)
    def post_order(self, node):
        if node is None:
            return
        self.post_order(node.left)
        self.post_order(node.right)
        print(node.data)
        
        
    # 先序遍历(非递归)
    def preorder(self, node):
        stack = []
        while node or stack:
            if node is not None:
                print(node.data)
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                node = node.right
    
    # 中序遍历(非递归)
    def inorder(self, node):
        stack = []
        while node or stack:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                print(node.data)
                node = node.right


    # 后序遍历(非递归)
    def postorder(self, node):
        stack = []
        queue = []
        queue.append(node)
        while queue:
            node = queue.pop()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            stack.append(node)
        while stack:
            print(stack.pop().data)

    # 水平遍历
    def levelorder(self, node):
        if node is None:
            return
        queue = [node]
        while queue:
            node = queue.pop(0)
            print(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    
    # 根据前序遍历和中序遍历,求后序遍历
    def findTree(self, preList, midList, afterList): 
        '''
        preList = list('DBACEGF')  
        midList = list('ABCDEFG')

        afterList = ['A', 'C', 'B', 'F', 'G', 'E', 'D'] 
        '''
        if len(preList)==0:  
            return  
        if len(preList)==1:  
            afterList.append(preList[0])  
            return  
        root = preList[0]  
        n = midList.index(root)  
        self.findTree(preList[1:n+1], midList[:n], afterList)  
        self.findTree(preList[n+1:], midList[n+1:], afterList)  
        afterList.append(root)
        
        #return afterList
                
'''
n1 = Node(data=1)
n2 = Node(2,n1,None)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5,n3,n4)
n6 = Node(6,n2,n5)
n7 = Node(7,n6,None)
n8 = Node(8)
root = Node(0,n7,n8)
'''
root = Node(0, Node(7, Node(6, Node(2, Node(1)), Node(5, Node(3), Node(4)))), Node(8))

bt = BTree(root)
print('pre_order......')
print(bt.pre_order(bt.root))
print('in_order......')
print(bt.in_order(bt.root))
print('post_order.....')
print(bt.post_order(bt.root))


preList = list('DBACEGF')  
midList = list('ABCDEFG')  
afterList = []

bt.findTree(preList, midList, afterList)  
print(afterList)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
二叉排序树 python实现
二叉排序树 python实现
17 0
(五)Python中的排序和元组
1.简单的排序 Python中内置了一些用于排序的方法。
40 0
Python题目
简述函数式编程 在函数式编程中,函数是基本单位,变量只是一个名称,而不是一个存储单元。除了匿名函数外,Python还使用fliter(),map(),reduce(),apply()函数来支持函数式编程。
850 0
python 线程及线程池
一、多线程 import threading from time import ctime,sleep def music(func): for i in range(2): print("I was listening to %s.
712 0
Python的GUI编程
Python的GUI编程 使用Tkinter模块来创建简单的GUI程序。Tkinter的Widgets有:Button、Canvas、Checkbutton、Entry、Frame、Label、Listbox、Menu、Menubutton、Message、Radiobutton、Scales、Scrollbar、TEXT、Toplevel等。
763 0
Python专家编程
版权声明:本文为博主chszs的原创文章,未经博主允许不得转载。 https://blog.csdn.net/chszs/article/details/3767771 Python专家编程 一、CPythonCPython是一个默认的、广泛使用的Python编程语言的实现。
762 0
Python的GUI编程
版权声明:本文为博主chszs的原创文章,未经博主允许不得转载。 https://blog.csdn.net/chszs/article/details/3729155 Python的GUI编程 使用Tkinter模块来创建简单的GUI程序。
748 0
+关注
罗兵
数学专业。擅数据分析,涉stock、lotto。了解随机过程分析、神经网络。涉web前端、后端。了解vba、js,稍擅python
251
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载