Python|快速掌握單雙鏈表和樹
- 2020 年 3 月 30 日
- 筆記
前言：
單雙鏈表、樹、二叉樹等數據結構的程式碼實現都存在相似之處，本文將從單鏈表入手，輕鬆掌握單雙鏈表、樹、二叉樹的程式碼實現。友情提示：請提前了解什麼是鏈表和樹。
具體內容
1.單鏈表
單鏈表由一個個節點連接而成每個節點包含兩部分資訊：值(val)、下一個節點(next)。
圖一單鏈表示意圖
在接觸單鏈表時，書上說的是節點1指向節點2，也就是next指向下一個節點。在程式碼實現的時候「next指向下一個節點」就等同於「next」就是下一個節點。
一個節點由兩部分組成：值(val)、下一個節點(next)。下一個節點(next)也由兩部分組成：val和next。層層嵌套，就形成了一個單鏈表。
圖二單鏈表結構圖
理解這些後，實現單鏈表的程式碼就很簡單。
|
class Node(): def __init__(self,val): self.elem=val self.next=None #定義單鏈表link,第一個節點的值是10link=Node(10)#第一個節點的下一個節點是節點20link.next=Node(20)#第二個節點的下一個節點是30link.next.next=Node(30)#列印第一個節點的值print(link.elem)#返回10#列印第二個節點的值print(link.next.elem) #返回20#列印第三個節點的值print(link.next.next.elem) #返回30 |
|---|
根據上方的程式碼，用節點類Node實現了一個單鏈表，但是很明顯，這個單鏈表的操作看起來有點蠢，當需要添加新節點時，還需要知道鏈表中有多少個節點，節點一多就需要手敲很多個next。
所以需要另一個類，來實現在添加節點時直接添加，而不用去管之前有多少節點。這個類如果還能實現遍歷節點之類的操作就更好了。
節點添加：尾插法
|
#節點類class Node(): def __init__(self,val): self.elem=val #next初始化為空 self.next=None#定義一個空鏈表類class SigleLink():def __init__(self,node=None): #單鏈表必須從頭部訪問，空鏈表需要記錄頭部，初始化為空 self.__head=node |
|---|
尾插法，顧名思義，在單鏈表的尾部添加元素，如果鏈表為空，令頭部__head等於新加入節點即可。鏈表不為空，令最後一個節點的next等於新加入的節點，就完成了新節點的插入，由於單鏈表只能從頭部開始操作，所以需要先從頭部遍歷到最後一個節點。
|
#從尾部插入元素def add_tail(self,val): #用戶只需傳入節點值，由函數自帶處理成節點 node=Node(val) #分別處理鏈表為空和不為空的情況 if self.__head==None: #頭部為空，鏈表為空 self.__head=node else: #需要對最後一個節點進行操作，需要先遍歷到最後一個節點 cur=self.__head #從頭節點開始遍歷,cur記錄當前操作的節點 while cur.next!=None: #當前節點的next不為空，就將cur移向下一個節點 cur=cur.next cur.next=node |
|---|
在尾插法的實現中已經包含了節點的遍歷，還要再實現從頭部插入節點，以及從任意位置插入節點的程式碼也就很簡單了。
|
#鏈表節點遍歷 def travel(self): cur=self.__head while cur!=None: print(cur.elem,end=' ') cur=cur.next print('')#換行 |
|---|
節點添加：頭插法
在鏈表頭部插入新節點(node)，令node.next等於原來的頭節點，將node標識為新的頭節點即可。
|
#頭插法 def add_top(self,val): node=Node(val) node.next=self.__head self.__head=node |
|---|
節點添加：任意位置插入節點
在下標為pos處插入新節點node，通過遍歷找出第pos-1個節點，令node.next等於第pos-1的節點的next，再令第pos-1的節點的next等於node即可.
|
#獲取鏈表的長度 def length(self): #cur游標，表示當前操作的節點 cur=self.__head #統計有多少節點 count=0 while cur!=None: count+=1 #將cur替換為下一個節點 cur=cur.next return countdef insert(self,pos,val): #輸入的位置<0，調用頭插法 if pos<=0: self.add_top(val) #輸入的位置>節點個數，調用頭插法 elif pos>self.length()-1: self.add_tail(val) else: node=Node(val) cur=self.__head count=0 #表示當前節點的下標，從0開始 #遍歷到第pos-1個節點時停止 while count<pos-1: count+=1 cur=cur.next node.next=cur.next cur.next=node |
|---|
2.雙鏈表
單鏈表每個節點包含：值(val)、下一個節點(next)。雙鏈表多一個資訊：上一個節點(last)。只需要對節點類稍加更改即可。
|
#雙鏈表節點類class Node(): def __init__(self,val): self.elem=val self.last=None self.next=None |
|---|
（1）遍歷
從頭部開始遍歷，操作和單鏈表一樣。從鏈表中的某個節點開始遍歷，只需要分別向前(last)和向後(next)遍歷一次即可。
（2）插入
單鏈表從尾部插入只需更改上一個節點的next，雙鏈表多一步，還需要更改插入節點的last。其他插入方式，也只需要注意多出來的last即可。
3.二叉樹
二叉樹與雙鏈表相比，上一個和下一個節點變為左節點和右節點
根據邏輯結構的變化，對遍歷，插入等操作做相應變化即可。
|
#二叉樹節點類class Node(): def __init__(self,val): self.elem=val self.left=None self.right=None |
|---|
4.樹
樹稍微麻煩一點，因為樹中的某個節點有多少子節點是不確定的，所以需要將子節點(son)用列表儲存。在遍歷節點的時候，注意用個for循環去遍歷當前節點的son即可。
|
#樹節點類class Node(): def __init__(self,val): self.elem=val self.son=[] |
|---|
結語
單雙鏈表、二叉樹、樹的程式碼實現都有其共同之處，在弄清楚單鏈表的實現後，在編寫雙鏈表、二叉樹、樹的程式碼時，多思考，舉一反三，便能很快上手。
END
編 輯 | 王楠嵐
責 編 | 馬原濤
where2go 團隊
