Python編程實現(xiàn)雙鏈表，棧，隊列及二叉樹的方法示例
更新時間：2017年11月01日 12:00:45 作者：王輝_Python
這篇文章主要介紹了Python編程實現(xiàn)雙鏈表，棧，隊列及二叉樹的方法,結(jié)合具體實例形式分析了Python簡單實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中雙鏈表，棧，隊列及二叉樹相關操作技巧,需要的朋友可以參考下
本文實例講述了Python編程實現(xiàn)雙鏈表，棧，隊列及二叉樹的方法。分享給大家供大家參考，具體如下：
1.雙鏈表
class Node(object):
def __init__(self, value=None):
self._prev = None
self.data = value
self._next = None
def __str__(self):
return "Node(%s)"%self.data
class DoubleLinkedList(object):
def __init__(self):
self._head = Node()
def insert(self, value):
element = Node(value)
element._next = self._head
self._head._prev = element
self._head = element
def search(self, value):
if not self._head._next:
raise ValueError("the linked list is empty")
temp = self._head
while temp.data != value:
temp = temp._next
return temp
def delete(self, value):
element = self.search(value)
if not element:
raise ValueError('delete error: the value not found')
element._prev._next = element._next
element._next._prev = element._prev
return element.data
def __str__(self):
values = []
temp = self._head
while temp and temp.data:
values.append(temp.data)
temp = temp._next
return "DoubleLinkedList(%s)"%values
2. 棧
class Stack(object):
def __init__(self):
self._top = 0
self._stack = []
def put(self, data):
self._stack.insert(self._top, data)
self._top += 1
def pop(self):
if self.isEmpty():
raise ValueError('stack 為空')
self._top -= 1
data = self._stack[self._top]
return data
def isEmpty(self):
if self._top == 0:
return True
else:
return False
def __str__(self):
return "Stack(%s)"%self._stack
3.隊列
class Queue(object):
def __init__(self, max_size=float('inf')):
self._max_size = max_size
self._top = 0
self._tail = 0
self._queue = []
def put(self, value):
if self.isFull():
raise ValueError("the queue is full")
self._queue.insert(self._tail, value)
self._tail += 1
def pop(self):
if self.isEmpty():
raise ValueError("the queue is empty")
data = self._queue.pop(self._top)
self._top += 1
return data
def isEmpty(self):
if self._top == self._tail:
return True
else:
return False
def isFull(self):
if self._tail == self._max_size:
return True
else:
return False
def __str__(self):
return "Queue(%s)"%self._queue
4. 二叉樹（定義與遍歷）
class Node:
def __init__(self,item):
self.item = item
self.child1 = None
self.child2 = None
class Tree:
def __init__(self):
self.root = None
def add(self, item):
node = Node(item)
if self.root is None:
self.root = node
else:
q = [self.root]
while True:
pop_node = q.pop(0)
if pop_node.child1 is None:
pop_node.child1 = node
return
elif pop_node.child2 is None:
pop_node.child2 = node
return
else:
q.append(pop_node.child1)
q.append(pop_node.child2)
def traverse(self): # 層次遍歷
if self.root is None:
return None
q = [self.root]
res = [self.root.item]
while q != []:
pop_node = q.pop(0)
if pop_node.child1 is not None:
q.append(pop_node.child1)
res.append(pop_node.child1.item)
if pop_node.child2 is not None:
q.append(pop_node.child2)
res.append(pop_node.child2.item)
return res
def preorder(self,root): # 先序遍歷
if root is None:
return []
result = [root.item]
left_item = self.preorder(root.child1)
right_item = self.preorder(root.child2)
return result + left_item + right_item
def inorder(self,root): # 中序序遍歷
if root is None:
return []
result = [root.item]
left_item = self.inorder(root.child1)
right_item = self.inorder(root.child2)
return left_item + result + right_item
def postorder(self,root): # 后序遍歷
if root is None:
return []
result = [root.item]
left_item = self.postorder(root.child1)
right_item = self.postorder(root.child2)
return left_item + right_item + result
t = Tree()
for i in range(10):
t.add(i)
print('層序遍歷:',t.traverse())
print('先序遍歷:',t.preorder(t.root))
print('中序遍歷:',t.inorder(t.root))
print('后序遍歷:',t.postorder(t.root))
輸出結(jié)果：
層次遍歷: [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相關內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設計有所幫助。
相關文章
這篇文章給大家介紹了Python十大列表操作技巧分享,列表展開,降維,分塊,轉(zhuǎn)置,查找眾數(shù),判斷重復元素等十個操作技巧,并通過代碼示例給大家介紹的非常詳細,需要的朋友可以參考下2024-01-01
在python2.7版本中，MySQLdb模塊還不是python的內(nèi)置模塊，但是MySQLdb模塊又是Python與MySQL連接的橋梁，對于作為MySQL DBA又很喜歡Python語言的我來說，MySQLdb真的是必需品呢。所以就需要自己進行安裝了，這篇文章就給大家詳細介紹了關于用yum安裝MySQLdb模塊的步驟。2016-12-12
Python如何將兩個三維模型(obj)合成一個三維模型(obj)
這篇文章主要介紹了Python如何將兩個三維模型(obj)合成一個三維模型(obj)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
使用默認的源地址下載速度很慢，所以一般都是使用國內(nèi)源，今天花了點時間配置安裝，所以記錄一下，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
這篇文章主要介紹了python定時器（Timer）用法,以一個簡單實例形式分析了定時器（Timer）實現(xiàn)延遲調(diào)用的技巧,需要的朋友可以參考下2015-06-06
一種Python工具的License授權(quán)機制詳解
這篇文章主要介紹了一種Python工具的License授權(quán)機制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
這篇文章主要介紹了Python json模塊dumps、loads操作,結(jié)合實例形式分析了Python使用json模塊針對json數(shù)據(jù)的載入、讀取、打印、編碼轉(zhuǎn)換等相關操作技巧,需要的朋友可以參考下2018-09-09
pytorch加載語音類自定義數(shù)據(jù)集的方法教程
這篇文章主要給大家介紹了關于pytorch加載語音類自定義數(shù)據(jù)集的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
Django uwsgi Nginx 的生產(chǎn)環(huán)境部署詳解
這篇文章主要介紹了Django uwsgi Nginx 的生產(chǎn)環(huán)境部署詳解,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-02-02
Python數(shù)據(jù)分析庫PyGWalker的強大交互式功能界面探索
這篇文章主要介紹了Python數(shù)據(jù)分析庫PyGWalker的強大交互式功能界面探索有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2024-01-01