【原創教程】數據結構與算法(1)——二叉樹

2021-03-02 辰語學習筆記

一、二叉樹

二叉樹是一種更為典型的樹樹狀結構。如它名字所描述的那樣，二叉樹是每個節點最多有兩個子樹的樹結構，通常子樹被稱作「左子樹」和「右子樹」。下面是個二叉樹的例子：

用python定義二叉樹的節點：

# 二叉樹節點
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

二、二叉樹遍歷1、前序遍歷

前序遍歷訪問的順序為：根節點、左子樹、右子樹。對於上圖，遍歷過程如下：

一開始指向根節點，訪問它，為E

有左子樹，指向他並訪問，為A

A沒有左子樹，指向其右子樹並訪問，為C

C有左子樹和右子樹，按順序訪問，為BD

E的左半邊訪問完畢，指向E的右子樹並訪問，為G

G只有右子樹，訪問它，為F

F往下已經沒有葉子節點，遍歷結束

因此，前序遍歷的結果為：EACBDGF

2、中序遍歷

中序遍歷訪問的順序為：左子樹、根節點、右子樹。對於上圖，遍歷過程如下：

因此，中序遍歷的結果為：ABCDEGF。通常來說，對於二叉搜索樹，我們可以通過中序遍歷得到一個遞增的有序序列

3、後序遍歷

後序遍歷訪問的順序為：左子樹、右子樹、根節點。對於上圖，遍歷過程如下：

因此，後序遍歷的結果為：BDCAFGE。當你刪除樹中的節點時，用到後序遍歷。也就是說，當你刪除一個節點時，你將首先刪除它的左節點和它的右邊的節點，然後再刪除節點本身。

4、層序遍歷

層序遍歷就是逐層遍歷樹結構，下圖展示了它的層次結構：

二叉樹的層序遍歷即為廣度優先搜索，該算法從一個根節點開始，首先訪問節點本身。然後遍歷它的相鄰節點，其次遍歷它的二級鄰節點、三級鄰節點，以此類推。廣度優先搜索需要用到隊列。遍歷過程如下：

初始化隊列q=[]，並將根節點E入隊，為q=[E]

q出隊，為E

E有左子樹和右子樹，兩者入隊，為q=[A, G]

q出隊，為A，此時將A的右子樹入隊，為q=[G, C]

q出隊，為G，此時G的右子樹入隊，為q=[C, F]

q出隊，為C，此時C的左子樹、右子樹入隊，為q=[F, B, D]

q出隊，為F，此時q=[B, D]

F沒有子樹，q繼續出隊，為B，此時q=[D]

q出隊，為D

q為空，遍歷結束

因此，層序遍歷的結果為：EAGCFBD。

三、程序實現

二叉樹的前序、中序、後序和層序遍歷，分別為leetcode的第144、94、145、102題，都可以用遞歸和迭代兩種方法做。

1、遞歸實現

對於前序、中序和後序來說，遞歸的現實非常簡單，他們的實現區別是根節點訪問的順序不一樣。代碼如下：

# 前序遍歷遞歸
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
else:
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

# 中序遍歷遞歸
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
else:
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

# 後序遍歷遞歸
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
else:
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right)+ [root.val]

可以看出不同的地方就是[root.val]的位置不一樣，前序遍歷[root.val]就在最一開始，中序遍歷[root.val]則在中間，後序遍歷[root.val]就在最後。整個迭代結構下圖所示：

對於層序遍歷的遞歸實現，我們不僅要輸出層序遍歷的序列，還要有每個元素屬於哪個層次的信息，可以用列表嵌套的方式，比如之前的例子裡，層序遍歷表示為[[E], [AG], [CF], [BD]]。

# 層序遍歷遞歸
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
levels = []
if not root:
return levels

def helper(node, level):
# start the current level
if len(levels) == level:
levels.append([])

# append the current node value
levels[level].append(node.val)

# process child nodes for the next level
if node.left:
helper(node.left, level + 1)
if node.right:
helper(node.right, level + 1)

helper(root, 0)
return levels

我們設更節點的層級序號為0，依次往下為1、2、3……。leaves為保存結果的列表，每一層的結果又為一個列表，保存在leaves裡，層級序號即為在leaves裡的index，在第i層級，leaves裡應該有i+1個列表，第i+1個列表為當前層級的節點。每個列表只append層級序號相同的節點。

2、迭代實現

二叉樹的迭代實現都需要用到棧。對於前序、中序、後序遍歷，他們的迭代實現大同小異：

# 前序遍歷迭代
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []

stack, output = [root, ], []
while stack:
root = stack.pop()
if root is not None:
output.append(root.val)
if root.right is not None:
stack.append(root.right)
if root.left is not None:
stack.append(root.left)

return output

# 中序遍歷迭代
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []

stack, output= [], []
curr = root
while curr or len(stack) > 0:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
output.append(curr.val)
curr = curr.right
return output

# 後序遍歷迭代
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []

stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
if root.left is not None:
stack.append(root.left)
if root.right is not None:
stack.append(root.right)

return output[::-1]

對於前序遍歷，先初始化一個有根節點的棧，然後進入循環，出棧根節點，訪問它。然後依次入棧右子樹、左子樹（注意棧是先進後出）。則下次循環，會先出棧左子樹，訪問它，然後入棧它的右子樹、左子樹。這樣根節點E的右子樹會在其左子樹遍歷完後才會出棧。循環停止條件是棧為空。

對於中序遍歷，因為要優先遍歷左子樹，循環之前初始化一個空棧，進入循環後，用一個內循環依次入棧左子樹，直到葉子節點（也為一個左子樹），然後退出內循環，出棧並訪問。

對於後序遍歷，和前序遍歷的整體結構是一樣的，唯一不同的是在循環裡先入棧左子樹，後入棧右子樹，循環結束後將結果逆序。

對於層序遍歷的迭代實現，循環之前初始化一個有根節點的隊列，此時隊列只有一個元素，進入循環後，出隊並訪問，然後將根節點的左右子樹依次入隊。下次循環，依次將上次隊列裡的元素出隊，同隊入隊他們的左右子樹。這樣每次循環只出隊當前層次的節點，併入隊他們的左右子樹，完成了層次之間的交換。這實際上是一種廣度優先搜索。層序遍歷迭代寫法：

# 層序遍歷迭代，使用棧
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
q = [root]
result = []
while q:
res = []
for i in range(len(q)):
node = q.pop(0)
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(res)
return result

# 層序遍歷迭代，使用隊列
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []

res = []
q = deque()
q.append(root)
while q:
size = len(q)
curr_level = []
for _ in range(size):
node = q.popleft()
curr_level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(curr_level)
return res

四、例題

二叉樹的最近公共祖先

此題為leetcode第236題

（https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/）

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 樹為空返回None
if root is None:
return None

# 找到了p或q
if root == p or root == q:
return root

# 在root的左子樹找p或q
left = self.lowestCommonAncestor(root.left, p, q)
# 在root的右子樹找p或q
right = self.lowestCommonAncestor(root.right, p, q)

if left is None: # 如果左子樹沒有p或q，返回右孩子
return right
elif right is None: # 如果右子樹沒有p或q，返回左孩子
return left
else: # 如果分別在左右子樹找到了p或q，那麼root就是最近公共祖先
return root

五、總結

（全文完）

作者簡介：

李旭東，中科院在讀研究生，研究方向為深度學習、工業故障診斷，喜歡讀書，希望同各位小夥伴一起交流學習！

作者微信號：wuan3076

個人網站：lixudong.ink

博客：https://blog.csdn.net/u014157632

郵箱：lixudong16@mails.ucas.edu.cn

粉絲福利：

關注公眾號「辰語學習筆記」，在公眾號對話框回復關鍵詞「知識手冊」，免費獲取《機器學習基礎知識手冊》！

註：這篇文章是公眾號粉絲投稿的原創文章，想要投稿請聯繫小編微信：makersky1688

往期回顧

【原創首發】《機器學習基礎知識手冊》：一個總結性的機器學習基礎知識小冊子

【原創首發】創意科普魔方，不止是一個玩具！

生成「星辰大海」：變分自編碼器（VAE）實踐

零基礎學爬蟲（一）：不用編程抓取B站彈幕信息

零基礎學爬蟲（二）：幾分鐘完成你的第一個爬蟲程序！

零基礎學爬蟲（三）：抓取網頁的多個元素

零基礎學爬蟲（四）：不規則分頁的抓取和反爬蟲應對方法

手把手教你搭建谷歌TensorFlow深度學習開發環境！

相關焦點

  • 尚矽谷Java數據結構與算法、設計模式教程雙雙發布
    算法是程序的靈魂，優秀的程序在對海量數據處理時，依然保持高速計算,就需要高效的數據結構和算法支撐。網上數據結構和算法的教程不少，但存在兩個問題:(1) 授課方式單一，大多是照著代碼念一遍，數據結構和算法本身就比較難理解，對基礎好的學員來說，還好一點，對基礎不好的學生來說，基本上就是聽天書了。
  • 結構與算法:二叉樹與多叉樹
    一、樹狀結構1、數組與鍊表數組結構數組存儲是通過下標方式訪問元素，查詢速度快，如果數組元素是有序的，還可使用二分查找提高檢索速度；如果添加新元素可能會導致多個下標移動，效率較低；鍊表結構鍊表存儲元素，對於元素添加和刪除效率高
  • 數據結構和算法學習指南
    首先，這裡講的都是普通的數據結構和算法，咱不是搞競賽的，野路子出生，只解決常規的問題，以面試為最終目標。另外，以下是我個人的經驗的總結，沒有哪本算法書會寫這些東西，所以請讀者試著理解我的角度，別糾結於細節問題，因為這篇文章就是對數據結構和算法建立一個框架性的認識。
  • 快速入門數據結構和算法
    本文簡要分享算法基礎、常見的數據結構以及排序算法，給同學們帶來一堂數據結構和算法的基礎課。文末福利：阿里雲開發者訓練營來了。一  前言1  為什麼要學習算法和數據結構？2  業務開發要掌握到程度？ 二  數據結構基礎1  什麼是數據結構？數據結構是數據的組織、管理和存儲格式，其使用目的是為了高效的訪問和修改數據。數據結構是算法的基石。如果把算法比喻成美麗靈動的舞者，那麼數據結構就是舞者腳下廣闊而堅實的舞臺。2  物理結構和邏輯結構的區別？
  • 【算法總結】五道常見的算法-二叉樹
    慢慢得，我發現算法也是一個可以通過練習慢慢成長的。首先我們要掌握基本的數據結構，數組，鍊表，哈希表， Set，二叉樹，堆，棧等。你要知道他們有什麼優缺點，適應場景是什麼，時間複雜度和空間複雜度是多少。而不能知道簡單的 API。接著，掌握了這些基本的數據結構之後，一些基本的算法你也要掌握以下，比如快速排序，歸併排序，對排序，二分查找。
  • 「算法與數據結構」二叉樹之美
    腦圖👇樹的基本概念樹是用來模擬具有樹狀結構性質的數據集合。或者你可以把它認為是一種「抽象數據結構」或是實現這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。示例:❝輸入: [1,null,2,3]12/3輸出: [1,3,2]❞進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？
  • 數據結構與算法大總結
    數據結構知識綜述一、前言經過一個學期對數據結構與算法的學習，對這門課程有了更深入的了解，了解到了數據結構的相關知識，明白了，數據結構的重要性及應用，回顧一個學期，通過這個小論文，來總結一學期的學習成果，數據結構這門課程，具有一定的深度和廣度，有其複雜性，我們一起來分析一下
  • 數據結構學習筆記:樹與樹的表示、二叉樹及其遍歷、二叉搜索樹、平衡二叉樹、堆、哈夫曼樹、集合及其運算
    一個二叉樹第i 層的最大結點數為：2i-1，i ≥ 1深度為k 的二叉樹有最大結點總數為：2k-1，k ≥ 1對任何非空二叉樹T，若n0 表示葉結點的個數，n2 是度為2 的非葉結點個數，那麼兩者滿足關係n0 = n2 + 1（證明見這裡）二叉樹的抽象數據類型重要操作：
  • 數據結構與算法分析筆記——B樹
    數據結構與算法分析筆記——B樹B樹AVL樹的特徵是，通過在插入或刪除時的微調，使得整個樹中任意節點的左子樹和右子樹之間的高度差不超過1。這樣的結果是，整棵樹的高度不至於太高。那麼，如果我們想要得到一棵更低的樹？該如何呢？
  • 二叉樹算法,你懂嗎?
    點擊藍色「碼出高效面試的程序媛」關注我，了解更多技術流行面試題
  • 阿里技術官丟出的「數據結構與算法」筆記,名不虛傳
    現在隨著科技時代的迅速發展，數據結構與算法已經被更多企業使用以及被更多的人熟知，這也是目前很有前景的一個領域，但是市面上對於數據結構與算法的學習資料還是相對較少，很多人無從下手，那麼該如何學好數據結構與算法呢？現在數據結構與算法也是面試中經常被問及的，難以被忽視的一部分。
  • 資源 | 從算法到數據結構,百道面試問題實現答案集合
    、數據結構以及面試問題解決方案的集合，裡面的 repository 包含了我對常見算法問題的解答以及數據結構的實現（用 Java）。項目地址：https://github.com/sherxon/AlgoDS目前為止，該資源集合提供了算法、數據結構以及 200 道面試題的答案。
  • 歷年比例41%的算法與數據結構知識點總結
    1、算法◆問題處理方案的正確而完整的描述稱為【算法】。算法分析的目的是，分析算法的效率以求改進。算法的基本特徵是【可行性】、【確定性】、【有窮性】和擁有足夠情報。 ◆算法的有窮性是指：算法程序的運行時間是有限的。 ◆算法的複雜度是衡量算法好壞的度量，分為【時間複雜度】和【空間複雜度】。
  • 二叉樹的前序非遞歸遍歷
    二叉樹的遍歷是二叉樹數據結構的重要操作之一，對於遍歷我們首先想到的就是遞歸，遞歸操作思想簡潔，操作簡單，但是在複雜的高度較大的二叉樹應用中使用遞歸算法，可能會造成性能的浪費，本文來介紹二叉樹的前序非遞歸遍歷。
  • 面試經驗分享之數據結構、算法題
    前言面試 IT 企業的研發崗位，數據結構和算法顯然是必考的項目。俺只學過普通的數據結構課程，沒讀過 STL，也沒有過 ACM 的訓練和比賽經歷，在一開始面對這樣類型題目的時候，心裡還是十分忐忑的。大大小小几十場面試下來，自己在這方面總算有了一定的心得積累，在此拋磚引玉， 以饗讀者。
  • 《大話數據結構》pdf下載
    以一個計算機教師教學為場景，講解數據結構和相關算法的知識。通篇以一種趣味方式來敘述，大量引用了各種各樣的生活知識來類比，並充分運用圖形語言來體現抽象內容，對數據結構所涉及到的一些經典算法做到逐行分析、多算法比較。與市場上的同類數據結構圖書相比，本書內容趣味易讀，算法講解細緻深刻，是一本非常適合自學的讀物。本書以一個計算機教師教學為場景，講解數據結構和相關算法的知識。通篇?
  • 騰訊T4竟然把《數據結構與算法》講明白了,附源碼筆記
    如果一個算法有缺陷，或不適合於某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間複雜度與時間複雜度來衡量。經歷過校招或者面過網際網路大廠的朋友應該知道，算法和數據結構是不可避免的。
  • 二叉樹算法大盤點
    樹結構對於程式設計師來說應該不陌生，特別是二叉樹，基本只要接觸算法這一類的都一定會碰到的，所以我打算通過一篇文章，對二叉樹結構的相關算法進行總結匯總，思路和代碼實現相結合，讓你不在懼怕二叉樹。（ps：後面我還想寫一篇樹結構的高級篇，就是多叉數，就是對我平時看算法論文碰到的一些新奇的算法，比如B樹、B+樹，還有我一種叫做Bed樹的新奇算法等等）下面的思路講解中，我會給出一個類偽代碼的思路，然後進行相關說明，也就是一種思路框架，有了思路框架，以後碰到問題就直接交給框架完成。
  • 手寫二叉樹?程式設計師面試最常見問題TOP 48
    近來正值秋招季節，很多編程面試都要求手寫數據結構手推機器學習算法。各位同學為了面試也會刷各種編程題，其中數據結構與排序搜索算法又是最為基礎的內容。在本文中，我們為各位讀者準備了 48 道基礎面試題，它可以幫助我們更深地理解數據結構。本文所有面試題都提供了 Java 解決方案，並介紹了比較流行的 GitHub 面試題項目。
  • 考研計算機重難點解析:數據結構
    針對這樣的情況，為我們的考生們精心準備了一些數據結構重難點解析和複習建議。統考大綱對數據結構的考查目標定位為掌握數據結構的基本概念、基本原理和基本方法，掌握數據的邏輯結構、存儲結構以及基本操作的實現；能夠對算法進行基本的時間複雜度和空間複雜度的分析；能夠運用數據結構的基本原理和方法進行問題的分析求解，具備採用C、C 或JAVA語言設計程序與實現算法的能力。