Python编程实现双链表,栈,队列及二叉树的方法示例
本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法。分享给大家供大家参考,具体如下:
1.双链表
classNode(object): def__init__(self,value=None): self._prev=None self.data=value self._next=None def__str__(self): return"Node(%s)"%self.data classDoubleLinkedList(object): def__init__(self): self._head=Node() definsert(self,value): element=Node(value) element._next=self._head self._head._prev=element self._head=element defsearch(self,value): ifnotself._head._next: raiseValueError("thelinkedlistisempty") temp=self._head whiletemp.data!=value: temp=temp._next returntemp defdelete(self,value): element=self.search(value) ifnotelement: raiseValueError('deleteerror:thevaluenotfound') element._prev._next=element._next element._next._prev=element._prev returnelement.data def__str__(self): values=[] temp=self._head whiletempandtemp.data: values.append(temp.data) temp=temp._next return"DoubleLinkedList(%s)"%values
2.栈
classStack(object): def__init__(self): self._top=0 self._stack=[] defput(self,data): self._stack.insert(self._top,data) self._top+=1 defpop(self): ifself.isEmpty(): raiseValueError('stack为空') self._top-=1 data=self._stack[self._top] returndata defisEmpty(self): ifself._top==0: returnTrue else: returnFalse def__str__(self): return"Stack(%s)"%self._stack
3.队列
classQueue(object): def__init__(self,max_size=float('inf')): self._max_size=max_size self._top=0 self._tail=0 self._queue=[] defput(self,value): ifself.isFull(): raiseValueError("thequeueisfull") self._queue.insert(self._tail,value) self._tail+=1 defpop(self): ifself.isEmpty(): raiseValueError("thequeueisempty") data=self._queue.pop(self._top) self._top+=1 returndata defisEmpty(self): ifself._top==self._tail: returnTrue else: returnFalse defisFull(self): ifself._tail==self._max_size: returnTrue else: returnFalse def__str__(self): return"Queue(%s)"%self._queue
4.二叉树(定义与遍历)
classNode: def__init__(self,item): self.item=item self.child1=None self.child2=None classTree: def__init__(self): self.root=None defadd(self,item): node=Node(item) ifself.rootisNone: self.root=node else: q=[self.root] whileTrue: pop_node=q.pop(0) ifpop_node.child1isNone: pop_node.child1=node return elifpop_node.child2isNone: pop_node.child2=node return else: q.append(pop_node.child1) q.append(pop_node.child2) deftraverse(self):#层次遍历 ifself.rootisNone: returnNone q=[self.root] res=[self.root.item] whileq!=[]: pop_node=q.pop(0) ifpop_node.child1isnotNone: q.append(pop_node.child1) res.append(pop_node.child1.item) ifpop_node.child2isnotNone: q.append(pop_node.child2) res.append(pop_node.child2.item) returnres defpreorder(self,root):#先序遍历 ifrootisNone: return[] result=[root.item] left_item=self.preorder(root.child1) right_item=self.preorder(root.child2) returnresult+left_item+right_item definorder(self,root):#中序序遍历 ifrootisNone: return[] result=[root.item] left_item=self.inorder(root.child1) right_item=self.inorder(root.child2) returnleft_item+result+right_item defpostorder(self,root):#后序遍历 ifrootisNone: return[] result=[root.item] left_item=self.postorder(root.child1) right_item=self.postorder(root.child2) returnleft_item+right_item+result t=Tree() foriinrange(10): t.add(i) print('层序遍历:',t.traverse()) print('先序遍历:',t.preorder(t.root)) print('中序遍历:',t.inorder(t.root)) print('后序遍历:',t.postorder(t.root))
输出结果:
层次遍历:[0,1,2,3,4,5,6,7,8,9] 先次遍历:[0,1,3,7,8,4,9,2,5,6] 中次遍历:[7,3,8,1,9,4,0,5,2,6] 后次遍历:[7,8,3,9,4,1,5,6,2,0]
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。