關于Python實現樹結構和鏈表結構的一點想法

Python由于內置的數據結構具有很高的靈活性，所以可以用很多種方式來構建樹、圖、鏈表等結構

1. 樹的Python實現

python自然可以使用class來創建Node結點類和Trie類，然后通過left和right屬性保存Node結點來實現樹

Python也可以使用字典來嵌套生成樹，字典的Key作為當前結點，字典的Value為子樹。

但需要注意的是，字典的value是一個字典，那么這個value字典中可以有多個Key，那么每個Key之間是互相為兄弟關系的。

同理，如列表等數據結構，也可以通過嵌套來生成樹

在使用字典創建樹時，可以重復利用dict的方法setdefault(key,default)，如果key存在，則返回value，若不存在，則插入key:default并返回default

--------------------------

比較有意思的是對于樹而言，在哪里存他的數據會有很多的不同，對于不同場景酌情實現

假設是使用class實現的字母前綴樹，那么可以把字母值保存在當前Node結點的value中，那么這樣匹配一個單詞的時候，需要遍歷所有的子節點找到對應值是否存在，這樣在某一層上就多花了k的時間(由于字典自帶哈希，所以字典實現的前綴樹查找會很快，是O(1)的時間)

也可以把字母值保存在連向子結點的連線上

由于字母前綴樹每個結點最多只有26種取值，所以可以提前存一個初始化為26個None的列表，如果在b的位置有值，那么在第二個位置存子結點的Node，這樣就實現了把字母值存在連向子結點的連線上。

同時，匹配一個單詞的時候，直接來判斷這個位置是None還是存在Node結點就可以直接找到下一個結點了，也是O(1)的時間，但是如果樹很深，但是很窄的話，這樣會浪費許多空間

所以針對不同的場景需求，可以自行選擇存儲數據的位置，有不同的效果。

利用字典實現樹代碼如下

#利用字典實現前綴樹

trie = {}

# 建立字典實現的字母前綴樹

for word in words:

cur = trie

for alpha in word:

cur=cur.setdefault(alpha,{})

2. 鏈表的Python實現

python本身的列表已經很好用了，在python的標準庫中沒有鏈接列表的實現，如果需要大量插入和刪除還是需要手動實現一下的，可以實現O(k)的增刪查找復雜度

鏈表實現自然也可以用class來創建Node結點類和Trie類，在Trie類中創建head與tail的Node對象，就可以進行追蹤了

如果需要O(1)的查找以及增刪復雜度的鏈表，那么需要配合哈希與雙向鏈表實現、那么在Trie類中還需要添加一個dict哈希來進行節點位置的追蹤，key為Node節點的Key(Node節點屬性有Key、value、next、pre)，Value為該Node節點

#配合哈希與雙向鏈表實現O(1)的查找以及增刪復雜度

class Node:

def __init__(self,key,value):

self.key=key

self.value=value

self.next=None

self.pre=None

class LRUCache:

def __init__(self, capacity: int):

self.dic=dict()

self.capacity=capacity

self.size=0

self.head=Node(-1,-1)

self.tail=Node(-1,-1)

self.head.next=self.tail

self.tail.pre=self.head

def get(self, key: int) -> int:

if(key in self.dic):

new_node = Node(key, self.dic[key].value)

# 刪除舊節點

del_node = self.dic[key]

del_node.pre.next = del_node.next

del_node.next.pre = del_node.pre

# 添加新節點到頭部

new_node.pre = self.head

new_node.next = self.head.next

self.head.next.pre = new_node

self.head.next = new_node

self.dic[key]=new_node

return self.dic[key].value

else:

return -1

def put(self, key: int, value: int) -> None:

new_node = Node(key, value)

# 添加新節點到頭部

new_node.pre = self.head

new_node.next = self.head.next

self.head.next.pre = new_node

self.head.next = new_node

if(key in self.dic):

del_node=self.dic[key]

del_node.pre.next=del_node.next

del_node.next.pre=del_node.pre

else:

# 如果key不在鏈表中，才考慮刪去尾元素或者更改size

if(self.size==self.capacity):

# 如果滿了，要刪去尾部節點

self.dic.pop(self.tail.pre.key)

self.tail.pre.pre.next=self.tail

self.tail.pre=self.tail.pre.pre

else:

self.size+=1

self.dic[key] = new_node

原文：https://www.cnblogs.com/heyjjjjj/p/13837283.html

總結

以上是生活随笔為你收集整理的python链表和树实验报告_关于Python实现树结构和链表结构的一点想法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。