数据结构与算法（Python版）第2版 源代码汇 周元哲 第2-14章 异常处理与调试-networkX

第2章异常处理与调试【例2-4】捕获单个异常num1=int(input("请输入被除数："))num2=int(input("请输入除数："))try:print("结果为",num1/num2)exceptZeroDivisionErroraserror: print("出错了,原因是：",error)【例2-5】捕获多个异常num1=int(input("请输入被除数："))num2=int(input("请输入除数："))try:print("结果为",num1/num2)except(ZeroDivisionError,ValueError)aserror:print("出错了,原因是：",error)【例2-6】try-except-else处理异常情况num1=int(input("请输入被除数："))num2=int(input("请输入除数："))try:result=num1/num2exceptExceptionaserror:print("出错了,原因是：",error)else:print(result)【例2-7】try-except-finally举例try:print(2/0)except(ZeroDivisionError,Exception):print('发生了一个异常')finally:print('不管是否发生异常都执行')【例2-11】举例：使用断言语句判断用户输入的除数是否为0。num1=int(input("请输入被除数："))num2=int(input("请输入除数："))assertnum2!=0,'除数不能为0'print(num1/num2)第3章线性表3.2顺序存储Python提供列表实现顺序表的各种操作，进行判空，查找，插入，删除，打印等功能。#创建一个空的顺序表：my_list=[]#初始化列表my_list=list(map(int,input().split()))#比如3135#在顺序表末尾插入元素：data=int(input())#9my_list.append(data)#[3,1,3,5,9]print(my_list)#在指定位置插入元素：my_list.insert(1,15)#[3,15,1,3,5,9]print(my_list)#获取指定位置的元素：element=my_list[0]#3#修改指定位置的元素：my_list[2]=25#[3,15,25,3,5,9]print(my_list)#删除指定位置的元素：delmy_list[1]#[3,25,3,5,9]print(my_list)#获取顺序表的长度：length=len(my_list)#5#判断元素是否在顺序表中：is_present=25inmy_list#True#查找元素在顺序表中的索引：index=my_list.index(25)#1#清空顺序表：my_list.clear()#[]程序输入：31359输出：[3,1,3,5,9]#初始化的列表[3,15,1,3,5,9]#末尾添加9[3,15,25,3,5,9]#位置2修改为25[3,25,3,5,9]#删除位置1后的列表3.3链式存储classNode(object):"""节点类"""def__init__(self,elem):self.elem=elemself.next=None#初始设置下一节点为空classSingleLinkList(object):"""创建单链表"""def__init__(self,node=None):#使用一个默认参数，传入头结点接收；没有传入时，默认头结点为空self.__head=nodedefis_empty(self):'''链表是否为空'''returnself.__head==Nonedeflength(self):'''链表长度'''cur=self.__head#cur游标，用来移动遍历节点count=0#count记录数量whilecur!=None:count+=1cur=cur.nextreturncountdeftravel(self):'''遍历整个列表'''cur=self.__headwhilecur!=None:print(cur.elem,end='')cur=cur.nextprint("\n")defadd(self,item):'''链表头部添加元素'''node=Node(item)node.next=self.__headself.__head=nodedefappend(self,item):'''链表尾部添加元素'''node=Node(item)#由于特殊情况当链表为空时没有next，所以在前面要做个判断ifself.is_empty():self.__head=nodeelse:cur=self.__headwhilecur.next!=None:cur=cur.nextcur.next=nodedefinsert(self,pos,item):'''指定位置添加元素'''ifpos<=0:#如果pos位置在0，当做头插法self.add(item)elifpos>self.length()-1:#如果pos位置比原链表长，那么都当做尾插法来做self.append(item)else:per=self.__headcount=0whilecount<pos-1:count+=1per=per.next#当循环退出后，pre指向pos-1位置node=Node(item)node.next=per.nextper.next=nodedefremove(self,item):'''删除节点'''cur=self.__headpre=Nonewhilecur!=None:ifcur.elem==item:#先判断该节点是否是头结点ifcur==self.__head:self.__head=cur.nextelse:pre.next=cur.nextbreakelse:pre=curcur=cur.nextdefsearch(self,item):'''查找节点是否存在'''cur=self.__headwhilenotcur:ifcur.elem==item:returnTrueelse:cur=cur.nextreturnFalseif__name__=="__main__":ll=SingleLinkList()print(ll.is_empty())print(ll.length())ll.append(3)ll.add(999)ll.insert(-3,110)ll.insert(99,111)print(ll.is_empty())print(ll.length())()ll.remove(111)()【程序运行结果】True0False4110999311111099933.4双链表3.5实例——一元多项式的加法classNode:#单链表结点存储一元多项式非零项的系数，指数和下一个结点def__init__(self,coefficient,exponent):self.coefficient=coefficientself.exponent=exponentself.next=NoneclassPolynomial:#一元多项式的类定义def__init__(self):#初始化空链表self.head=Nonedefis_empty(self):returnself.headisNonedefinsert_term(self,coefficient,exponent):new_node=Node(coefficient,exponent)ifself.is_empty()orexponent>self.head.exponent:new_node.next=self.headself.head=new_nodeelse:current=self.headprev=Nonewhilecurrentandexponent<current.exponent:prev=currentcurrent=current.nextifcurrentandexponent==current.exponent:current.coefficient+=coefficientifcurrent.coefficient==0:ifprev:prev.next=current.nextelse:self.head=current.nextelse:ifprevisNone:new_node.next=self.headself.head=new_nodeelse:new_node.next=currentprev.next=new_nodedefadd(self,p2):result=Polynomial()current1=self.headcurrent2=p2.headwhilecurrent1andcurrent2:ifcurrent1.exponent>current2.exponent:result.insert_term(current1.coefficient,current1.exponent)current1=current1.nextelifcurrent1.exponent<current2.exponent:result.insert_term(current2.coefficient,current2.exponent)current2=current2.nextelse:sum_coefficient=current1.coefficient+current2.coefficientifsum_coefficient!=0:result.insert_term(sum_coefficient,current1.exponent)current1=current1.nextcurrent2=current2.nextwhilecurrent1:#下面的2个循环最多有一个会被执行result.insert_term(current1.coefficient,current1.exponent)current1=current1.nextwhilecurrent2:result.insert_term(current2.coefficient,current2.exponent)current2=current2.nextreturnresultdefdisplay(self):current=self.headwhilecurrent:coefficient=current.coefficientexponent=current.exponentifexponent==0:term="+"+str(coefficient)elifexponent==1:term=f"{coefficient}x"else:term=f"{coefficient}x^{exponent}"print(term,end="")current=current.nextprint()#测试示例p1=Polynomial()p1.insert_term(3,3)p1.insert_term(-2,2)p1.insert_term(1,0)p2=Polynomial()p2.insert_term(3,3)p2.insert_term(-2,2)p2.insert_term(5,1)print("Polynomial1:")p1.display()print("Polynomial2:")p2.display()p3=p1.add(p2)print("Resultofaddition:")p3.display()【程序运行结果】Polynomial1:3x^3-2x^2+1Polynomial2:3x^3-2x^25xResultofaddition:6x^3-4x^25x+13.6实例——舞蹈链classNode:#舞蹈链的结点def__init__(self,value):self.value=value#结点的值self.up=None#上方相邻结点self.down=None#下方相邻结点self.left=None#左侧相邻结点self.right=None#右侧相邻结点self.column=None#列结点classCrossList:#舞蹈链def__init__(self):self.head=Node(None)#头结点，不存储具体值self.columns=[]#列结点列表#二维矩阵matrix初始化十字链表definit(self,matrix):#创建列结点col_count=len(matrix[0])foriinrange(col_count):col_node=Node(i)col_node.left=self.headifi==0elseself.columns[-1]col_node.left.right=col_nodeself.columns.append(col_node)#构建行结点forrowinmatrix:row_head=None#当前行的头结点prev_node=None#前一个结点forj,valueinenumerate(row):ifvalue==1:#创建新的结点node=Node(j)node.column=self.columns[j]node.column.up=node.columnifnotnode.column.upelsenode.column.upnode.column.up.down=nodeifnotrow_head:row_head=node#插入到行链表中ifprev_node:prev_node.right=nodenode.left=prev_nodeprev_node=node#连接行链表首尾ifrow_head:row_head.left=prev_nodeprev_node.right=row_head#删除指定行结点defremove_row(self,row_index):#找到指定行结点的起始结点start_node=self.head.rightwhilestart_node.value!=row_index:start_node=start_node.right#迭代删除对应列结点的链接关系node=start_nodewhilenode:#断开行链表的链接关系node.left.right=node.rightnode.right.left=node.left#断开列链表的链接关系col_node=node.upwhilecol_node!=node:col_node.down.up=col_node.upcol_node.up.down=col_node.downcol_node=col_node.upnode=node.right3.7实例——最大子序列和defget_max_data(data):#全部都是负数，则最大和是最大负数max_data=data[0]fordindata[1:]:ifmax_data<d:max_data=dreturnmax_datadefget_max_sum(data):max_sum=get_max_data(data)ifmax_sum<0:#最大值是负数，则全部都是负数returnmax_sumthis_sum=0max_sum=0fordindata:this_sum+=d;ifmax_sum<this_sum:max_sum=this_sumifthis_sum<0:this_sum=0returnmax_sumdata=list(map(int,input().split()))max_sum=get_max_sum(data)print(max_sum)【程序运行结果】6-23-83-1273.8实例——链表合并classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(list1,list2):#创建一个虚拟头结点，方便后续操作dummy=ListNode()current=dummy#遍历两个链表，直到其中一个链表为空whilelist1andlist2:iflist1.val<list2.val:current.next=list1list1=list1.nextelse:current.next=list2list2=list2.nextcurrent=current.next#如果list1不为空，直接连接到新链表末尾iflist1:current.next=list1#如果list2不为空，直接连接到新链表末尾eliflist2:current.next=list2#返回新链表的头结点（虚拟头结点的下一个结点）returndummy.next#创建链表1->3->5list1=ListNode(1)list1.next=ListNode(3)list1.next.next=ListNode(5)#创建链表2->4->6list2=ListNode(2)list2.next=ListNode(4)list2.next.next=ListNode(6)#合并链表merged_list=mergeTwoLists(list1,list2)#打印合并后的链表whilemerged_list:print(merged_list.val,end="->"ifmerged_list.nextelse"\n")merged_list=merged_list.next【程序运行结果】1->2->3->4->5->63.9实例——求单链表的倒数第k个结点classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefgetKthFromEnd(head,k):#初始化两个指针，都指向头结点fast=headslow=head#先让fast指针走k步for_inrange(k):ifnotfast:returnNone#如果k大于链表长度，返回Nonefast=fast.next#同时移动fast和slow指针，直到fast指针到达链表末尾whilefast:fast=fast.nextslow=slow.next#此时slow指针指向的就是倒数第k个结点returnslow#创建链表1->2->3->4->5head=ListNode(1)head.next=ListNode(2)head.next.next=ListNode(3)head.next.next.next=ListNode(4)head.next.next.next.next=ListNode(5)#求倒数第2个结点k=2node=getKthFromEnd(head,k)#打印结点值ifnode:print(node.val)else:print("k大于链表长度")【程序运行结果】4，对这些数据进行逆置，最后按照逆置后的结果输出。第4章队列和栈4.1栈classStack(object):def__init__(self):#初始化self.items=[]defis_empty(self):#判断栈是否为空returnself.items==[]defpush(self,item):#将元素压入栈顶self.items.append(item)defpop(self):#弹出栈顶元素returnself.items.pop()defpeek(self):#返回栈顶元素returnself.items[len(self.items)-1]defsize(self):#返回栈的大小returnlen(self.items)if__name__=="__main__":stack=Stack()print(stack.is_empty())print(stack.size())stack.push(1)print(stack.peek())stack.push(2)print(stack.peek())stack.push(3)print(stack.peek())stack.pop()print(stack.peek())stack.pop()print(stack.peek())stack.pop()print(stack.is_empty())print(stack.size())4.2队列classQueue(object):def__init__(self):self.items=[]defis_empty(self):#判断队列是否为空returnself.items==[]defenqueue(self,item):#入队列self.items.insert(0,item)#在列表的头部进行操作defdequeue(self):#出队列returnself.items.pop()#在列表的尾部进行弹出操作defsize(self):#队列元素个数returnlen(self.items)if__name__=="__main__":queue=Queue()print(queue.is_empty())print(queue.size())queue.enqueue(1)queue.enqueue(2)queue.enqueue(3)print(queue.dequeue())print(queue.dequeue())print(queue.dequeue())print(queue.is_empty())print(queue.size())4.4斐波那契数列1循环方法x=1y=1print(x,end="")print(y,end="")while(True):z=x+yx=yy=zif(z>100):#当z>100的时候，终止循环breakprint(z,end="")2递归defFib(n):#递归函数ifn<=1:returnnelse:return(Fib(n-1)+Fib(n-2))m=int(input("打印前多少项?"))ifm<=0:print("请输入正整数！")else:print("Fib级数前%d项:"%m)foriinrange(1,m):print(Fib(i),end="")3迭代deffibo(max):n,a,b=0,0,1whilen<max:yieldba,b=b,a+bn=n+1#退出标识m=int(input())print("输出前%d项"%m)forninfibo(m):print(n,end="")4.5回文数1转换为字符串defis_palindrome(num):num_str=str(num)returnnum_str==num_str[::-1]2循环构造defis_palindrome_math(num):original_num=numreversed_num=0whilenum>0:reversed_num=reversed_num*10+num%10num//=10returnoriginal_num==reversed_num#示例用法num=12321print(is_palindrome_math(num))3deque实现fromcollectionsimportdeque#引入dequedefcheck(aString):chardeque=deque()forchinaString:chardeque.append(ch)stillEqual=Truewhilelen(chardeque)>1andstillEqual:first=chardeque.pop()last=chardeque.popleft()iffirst!=last:stillEqual=Falsereturn(stillEqual)print("sdfsfsdfsdf","is",check("sdfsfsdfsdf"))print("radar","is",check("radar"))4.6逆波兰表达式defeval_rpn(tokens):stack=[]operators="+-*/"fortokenintokens:iftokennotinoperators:stack.append(int(token))else:num2=stack.pop()num1=stack.pop()iftoken=="+":result=num1+num2eliftoken=="-":result=num1-num2eliftoken=="*":result=num1*num2eliftoken=="/":result=num1/num2stack.append(result)returnstack.pop()tokens=["2","1","+","3","*"]print(eval_rpn(tokens))4.7年龄问题defage(intn):ifn==1:c=10else:c=age(n-1)+2returncn=int(input(“inputn:”))print(“%d”%age(n))4.8恺撒密码importos#将每个字母用字母表中它之后的第k个字母（称作位移值）替代defencryption():str_raw=input("请输入明文：")k=int(input("请输入位移值："))str_change=str_raw.lower()str_list=list(str_change)str_list_encry=str_listi=0whilei<len(str_list):iford(str_list[i])<123-k:str_list_encry[i]=chr(ord(str_list[i])+k)else:str_list_encry[i]=chr(ord(str_list[i])+k-24)i=i+1print("加密结果为："+"".join(str_list_encry))defdecryption():str_raw=input("请输入密文：")k=int(input("请输入位移值："))str_change=str_raw.lower()str_list=list(str_change)str_list_decry=str_listi=0whilei<len(str_list):iford(str_list[i])>=97+k:str_list_decry[i]=chr(ord(str_list[i])-k)else:str_list_decry[i]=chr(ord(str_list[i])+24-k)i=i+1print("解密结果为："+"".join(str_list_decry))whileTrue:print(u"1.加密")print(u"2.解密")choice=input("请选择：")ifchoice=="1":encryption()elifchoice=="2":decryption()else:print(u"您的输入有误！")4.9各类素数4.9.1素数方法1：使用循环判断素数i=2IsPrime=Truenum=int(input("anumber:"))foriinrange(2,num-1): ifnum%i==0: IsPrime=False break#作用是什么？ifIsPrime==True: print(num,"isprime")else: print(num,"isnotprime")方法2：埃拉托斯特尼筛法（SieveofEratosthenes）defsieve_of_eratosthenes(n):#创建一个布尔数组，初始值为True，表示所有数都是素数is_prime=[True]*(n+1)is_prime[0]=is_prime[1]=False#0和1不是素数#遍历从2到sqrt(n)的数foriinrange(2,int(n**0.5)+1):ifis_prime[i]:#如果i是素数#将i的倍数标记为非素数forjinrange(i*i,n+1,i):is_prime[j]=False#返回所有标记为True的索引，即素数primes=[iforiinrange(2,n+1)ifis_prime[i]]returnprimes4.9.2可逆素数defisprime(num):flag=1;i=2whilei<num:ifnum%i==0:flag=0breaki=i+1ifflag==1:returnTrue,defrev(n):r=0while(n>0):r=r*10+(n%10)n//=10returnrforiinrange(3,100):if(isprime(i)):ifisprime(rev(i)):print("%d"%i,"",end="")4.9.3孪生素数defisprime(num):foriinrange(2,num):ifnum%i==0:return0return1foriinrange(2,100):ifisprime(i)==1:ifisprime(i+2)==1:print(i,i+2)4.9.4回文素数defis_palindrome(n):"""判断一个数是否为回文数"""returnstr(n)==str(n)[::-1]deffind_palindromic_primes(limit):"""找出小于等于limit的所有回文素数"""palindromic_primes=[]foriinrange(2,limit+1):ifis_prime(i)andis_palindrome(i):palindromic_primes.append(i)returnpalindromic_primes#示例用法limit=1000palindromic_primes=find_palindromic_primes(limit)print(f"小于等于{limit}的回文素数有：")print(palindromic_primes)4.9.5素数环defis_prime(num):"""判断一个数是否是素数"""ifnum<=1:returnFalseifnum<=3:returnTrueifnum%2==0ornum%3==0:returnFalsei=5whilei*i<=num:ifnum%i==0ornum%(i+2)==0:returnFalsei+=6returnTruedeffind_prime_ring(n):"""使用回溯法找到一个素数环"""ifn<2:return[]#n至少为2才有意义#初始化path=[1]#素数环从1开始used=[False]*(n+1)#标记数字是否已经被使用used[1]=True#1已经被使用defbacktrack(path):"""回溯函数"""iflen(path)==n:#检查首尾是否也满足素数条件ifis_prime(path[-1]+path[0]):return[path[:]]#返回一个完整的环return[]results=[]foriinrange(2,n+1):ifnotused[i]andis_prime(path[-1]+i):used[i]=Truepath.append(i)results.extend(backtrack(path))#继续递归path.pop()used[i]=Falsereturnresultsreturnbacktrack(path)#测试n=int(input("请输入一个正整数n："))prime_rings=find_prime_ring(n)ifprime_rings:print(f"素数环：{prime_rings}")else:print("没有找到素数环")4.10汉诺塔i=1defmove(n,mfrom,mto):globaliprint("第%d步:将%d号盘子从%s->%s"%(i,n,mfrom,mto))i+=1defhanoi(n,A,B,C):ifn==1:move(1,A,C)#表示只有一个碟子时，直接从A塔移动到C塔else:hanoi(n-1,A,C,B)#将剩下的A塔上的n-1借助C塔移动到B塔move(n,A,C)#将A上最后一个直接移动到C塔上hanoi(n-1,B,A,C)#将B塔上的n-1个碟子借助A塔移动到C塔#调用hanoi函数try:n=int(input("pleaseinputainteger:"))print("移动步骤如下：")hanoi(n,'A','B','C')exceptValueError:print("pleaseinputaintegern(n>0)!")第5章串classString(object):def__init__(self):self.MaxStringSize=256self.chars=""self.length=0defIsEmpty(self):#判断是否为空ifself.length==0:IsEmpty=Trueelse:IsEmpty=FalsereturnIsEmptydefCreateString(self):#创建串stringSH=input("请输入字符串：")iflen(stringSH)>self.MaxStringSize:print("溢出，超过的部分无法保存")self.chars=stringSH[:self.MaxStringSize]else:self.chars=stringsprint("输入字符串长度是：%d"%len(stringSH))defStringConcat(self,strSrc):#串连接lengthSrc=len(strSrc)stringSrc=strSrciflengthSrc+len(self.chars)<=self.MaxStringSize:self.chars=self.chars+stringSrcelse:print("两个字符的长度之和溢出，超过的部分无法显示")size=self.MaxStringSize-len(self.chars)self.chars=self.chars+stringSrc[:size]print("连接后字符串为：",self.chars)defSubString(self,iPos,length):#从iPos位置开始，取长度为length的子串ifiPos>len(self.chars)-1oriPos<0orlength<1or(length+iPos)>len(self.chars):print("无法获取")else:substr=self.chars[iPos:iPos+length]print("获取的字串为：",substr)if__name__=="__main__":string=String()print(string.IsEmpty())string.CreateString()string.StringConcat("12345")string.SubString(1,4)5.3模式匹配1BF算法defBF(s1,s2,pos=0):#BF算法i=posj=0while(i<len(s1)andj<len(s2)):if(s1[i]==s2[j]):i+=1j+=1else:i=i-j+1#目标串S的i回滚j=0#模式串Tif(j>=len(s2)):returni-len(s2)else:return0if__name__=="__main__":s1="BBCABCDABABCDABCDABDE"s2="ABCDABD"print(BF(s1,s2))2KMP算法#coding=utf-8defkmp_match(s,p):#KMP算法m=len(s);n=len(p)cur=0#起始指针curtable=partial_table(p)whilecur<=m-n:#只去匹配前m-n个foriinrange(n):ifs[i+cur]!=p[i]:cur+=max(i-table[i-1],1)#有了部分匹配表,可以一次移动多位breakelse:#如果没有从任何一个break中退出，则会执行和for对应的else#只要从break中退出了，则else部分不执行。returnTruereturnFalse#部分匹配表defpartial_table(p):'''''partial_table("ABCDABD")->[0,0,0,0,1,2,0]'''prefix=set()postfix=set()ret=[0]foriinrange(1,len(p)):prefix.add(p[:i])postfix={p[j:i+1]forjinrange(1,i+1)}ret.append(len((prefix&postfixor{''}).pop()))returnretprint(partial_table("ABCDABD"))print(kmp_match("BBCABCDABABCDABCDABDE","ABCDABD"))5.4词法分析expression="3+4*2"tokens=[]i=0whilei<len(expression):ifexpression[i].isdigit():j=iwhilei<len(expression)andexpression[i].isdigit():i+=1tokens.append(expression[j:i])else:tokens.append(expression[i])i+=1print(tokens)5.5字串统计L=int(input())s=input()dict={}count=1i=0whilei<=len(s)-L:j=L+iwhilej<=len(s):s1=s[i:j]iftuple(s1)indict:dict[tuple(s1)]+=1else:dict[tuple(s1)]=1j+=1i+=1L=sorted(dict.items(),key=lambdaitem:item[1],reverse=True)foriinL[0][0]:print(str(i),end="")5.6文本处理与编辑#定义一个文本字符串text="Thisisasampletext.Wecanperformvariousstringoperationsonit."#插入操作new_text=text[:10]+"modified"+text[10:]print(new_text)#删除操作new_text_without_word=text.replace("sample","")print(new_text_without_word)#查找操作index_of_word=text.find("string")print("Theword'string'startsatindex:",index_of_word)#替换操作replaced_text=text.replace("stringoperations","functions")print(replaced_text)5.7Anagrams问题1collections模块fromcollectionsimportCounterdefis_anagram(str1,str2):returnCounter(str1)==Counter(str2)print(is_anagram(Unclear,Nuclear))2循环方法def

anagrams(s1,s2):

if(len(s1)!=len(s2)):

return

False

for

i

in

s1.lower():

if

i

not

in

s2.lower():

return

False

return

True

s1=input()

s2=input()

print(anagrams(s1,s2))按照指定的分隔符进行分割，返回分割后的字符串列表。第6章树和二叉树6.4先序遍历classTreeNode:def__init__(self,value):self.value=valueself.left=Noneself.right=Noneroot=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)6.4.1递归实现先序遍历defpreorder(root):result=[]defpreorder(root):ifroot:result.append(root.value)preorder(root.left)#先序遍历左子树preorder(root.right)#先序遍历右子树preorder(root)returnresultprint("递归先序遍历结果:",preorder(root))6.4.2非递归实现先序遍历defpreorderTraversal_nonrecursive(root):result=[]stack=[]ifroot:stack.append(root)whilestack:node=stack.pop()result.append(node.value)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresultprint("非递归先序遍历结果:",preorderTraversal_nonrecursive(root))6.5中序遍历6.5.1递归实现中序遍历definorder_traversal(root):ifrootisnotNone:inorder_traversal(root.left)#遍历左子树print(root.value,end='')#访问根节点inorder_traversal(root.right)#遍历右子树print("二叉树中序遍历结果:")inorder_traversal(root)6.5.2非递归实现中序遍历definorderTraversal_nonrecursive(root):result=[]stack=[]current=rootwhilecurrentorstack:#不断将当前节点的左子树节点压入栈，直到左子树为空whilecurrent:stack.append(current)current=current.left#弹出栈顶元素（即当前最左子树的根节点），并将其值加入结果列表current=stack.pop()result.append(current.value)#处理右子树，将当前节点更新为右子树节点，继续循环current=current.rightreturnresultprint("二叉树中序遍历结果:",inorderTraversal_nonrecursive(root))6.6后序遍历6.6.1递归实现后序遍历defPostOrder(root):ifroot==None:returnPostOrder(root.left)#后序遍历左子树PostOrder(root.right)#后序遍历右子树print(root.value,end='')#访问根节点print("二叉树后序遍历结果:")PostOrder(root)6.6.2非递归实现后序遍历defpostorderTraversal_nonrecursive(root):result=[]stack=[]last_visited=None#用于记录上一次访问的节点whilerootorstack:whileroot:stack.append(root)root=root.leftroot=stack.pop()#如果右子树为空或者右子树已经被访问过（即上一次访问的节点是右子树节点）ifnotroot.rightorroot.right==last_visited:result.append(root.value)last_visited=rootroot=None#继续从栈中取节点else:stack.append(root)root=root.rightreturnresultprint("二叉树后序遍历结果:",postorderTraversal_nonrecursive(root))6.7层序遍历fromcollectionsimportdequedeflevel_order_traversal(root):ifrootisNone:return#使用队列来存储待访问的节点queue=deque([root])whilequeue:node=queue.popleft()#从队列中取出一个节点print(node.value,end='')#访问该节点#将该节点的左子节点和右子节点依次加