首页 > 编程语言 >PTA-树的遍历(python实现)

PTA-树的遍历(python实现)

时间:2024-03-29 21:29:05浏览次数:37  
标签:遍历 后序 python self PTA 二叉树 root def

自己做题过程中的一些想法,做一个记录,方便以后查看,如果能给读者一些启发也是极好的。欢迎大家的批评指正和交流讨论。

题目描述:

给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式:

输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

4 1 6 3 5 7 2

思路:

题目给出了后序遍历和中序遍历,需要输出层序遍历,首先要做的就是根据后序遍历和中序遍历的结果重构这棵二叉树,然后再做层序遍历,层序遍历借助队列来实现(先进先出)。

具体过程:

第一步:建构二叉树

后序遍历即是“左-右-根”的顺序遍历二叉树,由此我们可以知道后序遍历的最后一个值就是二叉树的根节点的值;中序遍历即是“左-根-右”的顺序遍历二叉树,因此根据后序遍历找到根节点后,就可以根据该根节点的值(这里假设二叉树的每个结点值都不相同)在中序遍历找到相应的位置,从该位置以左就是二叉树的左子树,以右就是二叉树的右子树。根据左子树和右子树结点的个数可以在后序遍历的序列中找到相应的左子树和右子树对应的序列。同理,后序遍历的左子树序列最后一个值就是左子树的根节点,右子树序列的最后一个值就是右子树的根节点。

图示:

这个不断寻找每个结点的左子树和右子树的过程可以通过递归来实现,我们可以每次找到一个子树的根节点后就将它的值从后序遍历的序列中删除,子树的结构通过中序遍历的顺序来判断。直到每个结点都没有左子树且没有右子树,递归返回的条件就可以据此设置为后序遍历的序列是否为空。

第二步:层序遍历输出

借助“队列”先进先出的结构来对二叉树进行层序遍历,首先把根节点放入空队中,然后弹出队列中第一个值,并把它的左节点和右节点放入队列的队尾。之后循环判断队列是否为空,不空则每次弹出队首的元素,并且把弹出元素的左节点和右节点放入队尾,直到最后队列为空退出循环。这个更详细的解释可以去看MOOC上浙江大学的课程《数据结构》,老师讲的很易懂。

代码:

有些注释是为了检查程序是否有问题

#7-10 树的遍历
n=int(input())
back=list(map(int,input().split()))
middle=list(map(int,input().split()))

'''定义队列'''
class Queue():
    def __init__(self):
        #创建一个空队列
        self.item=[]
    def isEmpty(self):
        #判断是否空队列
        return len(self.item)==0
    def enQueue(self,elemt):
        #向队尾加入元素。定义0为队尾,n为队首
        self.item.insert(0,elemt)
    def deQueue(self):
        #抛出队首元素
        if self.isEmpty():
            raise Exception('Queue is empty.')
        return self.item.pop()
    def len(self):
        #返回队列中元素个数
        return len(self.item)
    def first(self):
        #返回队列第一个元素但不移除
        #队列为空则触发一个错误
        if self.isEmpty():
            raise Exception('Queue is empty.')
        return self.item[-1]
    def queueList(self):
        #返回队列所有元素
        if self.isEmpty():
            raise Exception('Queue is empty.')
        else:
            return self.item[::-1]

'''定义二叉树结点'''
class TreeNode():
    def __init__(self,val,Left=None,Right=None):
        '''val--结点值,Left--左结点,Right--右结点'''
        self.val=val
        self.Left=Left
        self.Right=Right
    def printNode(self):
        #打印结点值
        print(self.val)

'''根据后序遍历和中序遍历建立树'''
def create_tree(backorder,midorder):
    if not backorder:
        return None
    else:
        root_val=backorder.pop()
        root=TreeNode(root_val)
        root_idx=midorder.index(root_val)
        ll=len(midorder[:root_idx])     #左子树长度
        rl=len(midorder[root_idx+1:])   #右子树长度
        # print("ll:",ll,"rl:",rl)

        root.Left=create_tree(backorder[:ll],midorder[:root_idx])
        root.Right=create_tree(backorder[ll:ll+rl],midorder[root_idx+1:])
        # print(type(root))
        return root

'''定义层序遍历'''
def level_order_travsal(root):
    if not root:
        return None
    else:
        result=[]
        Que=Queue()
        # print('level order:',type(root))
        Que.enQueue(root)
        while(not Que.isEmpty()):
            rt=Que.deQueue()
            # print('loop:',type(rt))
            result.append(rt.val)
            if rt.Left:
                Que.enQueue(rt.Left)
            if rt.Right:
                Que.enQueue(rt.Right)
        return result

# back=[2,3,1,5,7,6,4]
# middle=[1,2,3,4,5,6,7]
root=create_tree(back,middle)
result=level_order_travsal(root)
for i in range(n-1):
    print(result[i],end=' ')
print(result[n-1])

标签:遍历,后序,python,self,PTA,二叉树,root,def
From: https://blog.csdn.net/life_can_be_cool/article/details/137155543

相关文章

  • Python 基于 xlsxwriter 实现百万数据导出 excel
    追加导出+自动切换sheet⚠️excel中的每个sheet最多只能保存1048576行数据#获取项目的根路径rootPathcurPath=os.path.abspath(os.path.dirname(__file__))rootPath=curPath[:curPath.find(你的项目名称+"/")+len(你的项目名称+"/")]#临时文件l......
  • python 脚本对数据库的简单操作
    importsqlite3fromdatetimeimportdatetime'''数据库内容[ID]intnull,[loginName]text(50),[loginTime]text(50),[logOutTime]text(50),[operation]intnull'''#连接到数据库conn=sqlite3.connect('test.......
  • Python 基于 xlsxwriter 实现百万数据导出 excel
    增量导出+自动切换sheet⚠️excel中的每个sheet最多只能保存1048576行数据#获取项目的根路径rootPathcurPath=os.path.abspath(os.path.dirname(__file__))rootPath=curPath[:curPath.find(你的项目名称+"/")+len(你的项目名称+"/")]#临时......
  • Python Numpy第三方库的基本使用
    1.下载Numpy第三方库pipinstallnumpy2.导入第三方库importnumpyasnp3.一些基本操作importnumpyasnpnum1=np.array([1,2,3,4,5])#创建数组print(num1)num2=np.zeros((3,2))#创建全零数组print(num2)print(num2.shape)#打印数组尺寸num3=np.ones((2,4))#创建......
  • 文件-Python
    师从黑马程序员文件编码 不同编码,将内容翻译成二进制也是不同的查看文件编码文件的读取文件的概念文件操作内容主要包括打开,关闭,读,写文件的操作步骤open()打开函数mode常用的三种基础访问模式读操作相关方法读操作相关方法close()关闭文件对象wi......
  • 转载:记录一下python setDaemon相关
    前言使用Python都不会错过线程这个知识,但是每次谈到线程,大家都下意识说GIL全局锁,但其实除了这个老生常谈的话题,还有很多有价值的东西可以探索的,譬如:setDaemon()。线程的使用与存在的问题我们会写这样的代码来启动多线程:importtimeimportthreadingdeftest():......
  • Python数据库编程全指南SQLite和MySQL实践
    1.安装必要的库首先,我们需要安装Python的数据库驱动程序,以便与SQLite和MySQL进行交互。对于SQLite,Python自带了支持;而对于MySQL,我们需要安装额外的库,如mysql-connector-python。#安装MySQL连接器pipinstallmysql-connector-python2.连接SQLite数据库SQLite是一......
  • python处理字典之表格-城市排行榜
    #中国城市排行榜importxlrdbook=xlrd.open_workbook('city_data.xls')sheet=book.sheet_by_index(0)main_data_list=[]forrowinrange(3,sheet.nrows):temp_dict={}#print(sheet.row_values(row))temp_dict["城市"]=sheet.row_values(row......
  • python根据达芬奇场景分析保存的edl文件,智能裁切输出4K视频画面(不带声音)-自动找到MP
    使用前先将mp4对应的EDL文件命名为相同的名字,如:春天.mp4,春天.edl只处理持续时间大于5帧的画面批量处理指定文件夹下所有文件,处理失败的直接跳过,接着继续处理其他的 importcv2importosimporttimeimportdatetimeimportshutilfrommoviepy.editorimportVideoFile......
  • 8 在IPython Notebook 运行Python Spark 程序
    8.1安装Anaconda下载:wget https://mirrors.pku.edu.cn/anaconda/archive/Anaconda3-5.3.1-Linux-x86_64.sh安装:bashAnaconda3-5.3.1-Linux-x86_64.sh-b编辑~/.bashrc:sudogedit~/.bashrc source~/.bashrc查看python版本 在data1,data2按同样的方法安装Anaconda8.2......