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程序设计有所帮助。