看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)

語言: CN / TW / HK

歡迎關注微信公眾號:簡說Python關注後回覆:1024,可以領取學習資源。

這兩天和幾個朋友組了個互相督促學習群,想著督促一下自己學習,也督促自己的原創輸出,其實很多時候都是懶,真不是沒有東西可以寫了,這不,我在我的免費知識星球簡說程式設計裡開了個新的標籤日常程式設計問題,後面我會把自己學習工作中遇到的一些問題和解決方法記錄到裡面,有些可以擴充套件的點,我會寫到微信公眾號裡。我定的目標是:

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)
我簡單寫了個規則,大家說可以,然後,我們就開始吧,我習慣把該做的事情提前一天做(如果有時間的話)。

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)
今天給大家分享的書籍《Python程式設計師面試演算法寶典》第三章第一小節:什麼是二叉樹,還介紹了常用的二叉樹遍歷方法,以及如何做演算法題的實戰方法。

如果你是第一次看,也許,你可以看看本系列下面的文章:

Python資料結構:連結串列合集(12+7),復現幾遍,包你學會

Python資料結構:棧佇列雜湊合集(10+1),復現幾遍,包你學會

不敲程式碼,5分鐘帶你認識二叉樹

今日問題

"""
目標:寫一個程式,將一個有序陣列存放到二叉樹中

輸入:[1, 2, 3, 4, 5, 6, 7]
輸出:4
         /     \
        2       6
      /   \    /   \
     1     3  5     7

Goal: write a program to store an ordered array in a binary tree
Input: [1, 2, 3, 4, 5, 6, 7]
Output:     4
         /     \
        2       6
      /   \    /   \
     1     3  5     7
"""

1> 什麼是二叉樹?

不敲程式碼,5分鐘帶你認識二叉樹

2> 解題優先

2.1> 思路概述

核心思想:將陣列折中分成左右兩部分,將中間結點當作二叉樹的根結點,左邊當作左子樹,右邊當作右子樹,對左右兩邊陣列同樣按上面的方法分,要讀取時採用中序遍歷對二叉 樹進行遍歷列印。

Core idea: divide the array into left and right parts, regard the
middle node as the root node of the binary tree, the left as the
left subtree, and the right as the right subtree. Divide the left
and right arrays according to the above method, and use the middle
order traversal to print the binary tree when reading.



2.2> 思路圖解

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)

2.3> 實現程式碼

def array_to_binary_tree_one(arr, start, end):
    """"
    arr : 待轉化為二叉樹的陣列
    start : arr陣列起始下標,初始時為0
    end : arr陣列末尾下標,初始時為len(arr)-1
    """
    if end >= start:  # 非空
        # 初始化一個二叉樹結點
        root = BinaryTree()
        # 獲取中間結點位置
        mid = (end + start + 1) // 2
        # 二叉樹根結點為列表中間元素
        root.root = arr[mid]
        # 二叉樹左結點為左列表(以中間結點為界線)中間元素
        root.lchild = array_to_binary_tree_one(arr, start, mid-1)
        # 二叉樹右結點為右列表(以中間結點為界線)中間元素
        root.rchild = array_to_binary_tree_one(arr, mid + 1, end)
    else:
        root = None
    return root  # 返回根結點

2.4> 測試程式碼

# 測試轉化結果,將轉化後的二叉樹打印出來
def in_order_traversal(root):
    # 以中序遍歷(左根右)的方式遍歷讀取二叉樹
    if not root:
        return
    if root.lchild:  # 遞迴遍歷先讀左子樹
        in_order_traversal(root.lchild)
    print(root.root, end="  ")  # 列印根結點
    if root.rchild:  # 遞迴遍歷右子樹
        in_order_traversal(root.rchild)

# 當然,也許還有別的方法,比如建一個輔助的連結串列
# 歡迎你說出你的想法

# 程式入口,測試函式功能
if __name__ == "__main__":
    # 待儲存到二叉樹的陣列
    data_list = [1, 2, 3, 4, 5, 6, 7]
    # 呼叫函式,將陣列存入二叉樹
    root = array_to_binary_tree_one(data_list, 0, len(data_list)-1)
    # 呼叫函式,列印二叉樹,檢驗結果
    in_order_traversal(root)

2.5> 執行結果

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)
與手寫該二叉樹的中序遍歷結果是一致的,無誤。

3> 搞就搞通:二叉樹的遍歷

3.1> 二叉樹的遍歷概述

通常二叉樹的遍歷分為深度優先遍歷和廣度優先遍歷,深度優先遍歷又包括:前序遍歷、中序遍歷、後序遍歷。

前序遍歷 (Pre-Order Traversal)(根結點-左孩子-右孩子)
中序遍歷 (In-Order Traversal)(左孩子-根結點-右孩子)
後序遍歷 (Post-Order Traversal)(左孩子-右孩子-根結點)

廣度優先遍歷又稱為層次遍歷 (Hierarchical traversal)(按二叉樹層來遍歷)。上面我們已經寫了中序遍歷,現在我們來仔細看看,看看讀取結果。

3.2> 前序遍歷 (Pre-Order Traversal)

所謂前序遍歷,就是按根結點-左孩子-右孩子的順序遍歷二叉樹,每遍歷到一個結點,先訪問該結點本身(root 根),然後訪問該結點左孩子(lchild),對於左孩子也按上面方法訪問,然後再訪問右孩子(rchild)。

3.2.0> 思路圖解

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)

3.2.1> 遞迴實現

def pre_order_traversal(root):
    # 前序遍歷 (Pre-Order Traversal)(根結點-左孩子-右孩子)
    if not root:
        return
    print(root.root, end="  ")  # 列印根結點
    if root.lchild:  # 遞迴遍歷先讀左子樹
        pre_order_traversal(root.lchild)
    if root.rchild:  # 遞迴遍歷右子樹
        pre_order_traversal(root.rchild)

3.2.2> 非遞迴實現

需要匯入我們之前寫過的棧,作為臨時儲存空間。如果你還不知道,不妨看看下面這篇文章:
Smaller Python資料結構:自己動手實現棧

from StackQueueHash.b_1_implementation_stack import ListStack

# 非遞迴實現前序遍歷
def pre_order_traversal(root):
    # 前序遍歷 (Pre-Order Traversal)(根結點-左孩子-右孩子)
    if not root:
        return
    # 初始化一個棧,臨時存放遍歷到的結點
    stack = ListStack()
    # 遍歷二叉樹
    while root or not stack.stack_is_empty():
        while root:  # 結點不為空時
            # 遍歷到該結點就訪問
            print(root.root, end="  ")
            # 將該結點臨時存入棧
            stack.stack_push(root)
            # 結點後移,向左遍歷
            root = root.lchild
        if not stack.stack_is_empty():  # 如果棧不為空
            # 取出棧中結點
            root = stack.get_stack_top()
            # 取出後,出棧
            stack.stack_pop()
            # 結點後移,向右遍歷
            root = root.rchild

3.3> 中序遍歷 (In-Order Traversal)

3.3.0> 思路圖解

圖片

3.3.1> 遞迴實現

def in_order_traversal(root):
    # 以中序遍歷(左根右)的方式遍歷讀取二叉樹
    if not root:
        return
    if root.lchild:  # 遞迴遍歷先讀左子樹
        in_order_traversal(root.lchild)
    print(root.root, end="  ")  # 列印根結點
    if root.rchild:  # 遞迴遍歷右子樹
        in_order_traversal(root.rchild)

3.3.2> 非遞迴實現

需要匯入我們之前寫過的棧,作為臨時儲存空間。如果你還不知道,不妨看看
下面這篇文章:
Smaller Python資料結構:自己動手實現棧

from StackQueueHash.b_1_implementation_stack import ListStack

# 非遞迴實現中序遍歷
def in_order_traversal(root):
    # 以中序遍歷(左根右)的方式遍歷讀取二叉樹
    if not root:
        return
    # 初始化一個棧,臨時存放遍歷到的結點
    stack = ListStack()
    # 遍歷二叉樹
    while root or not stack.stack_is_empty():
        while root:  # 結點不為空時
            # 將該結點臨時存入棧
            stack.stack_push(root)
            # 結點後移,向左遍歷
            root = root.lchild
        # 注意,上面的過程訪問結點,只是遍歷
        # 遍歷到最左端是才開始返回訪問結點
        if not stack.stack_is_empty():  # 如果棧不為空
            # 取出棧中結點
            root = stack.get_stack_top()
            # 遍歷到該結點就訪問 (根)
            print(root.root, end="  ")
            # 取出後,出棧
            stack.stack_pop()
            # 結點後移,向右遍歷
            root = root.rchild

3.4> 後序遍歷 (Post-Order Traversal)

3.4.0> 思路圖解

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)

3.4.1> 遞迴實現

def post_order_traversal(root):
    # 後序遍歷 (Post-Order Traversal)(左孩子-右孩子-根結點)
    if not root:
        return
    if root.lchild:  # 遞迴遍歷先讀左子樹
        post_order_traversal(root.lchild)
    if root.rchild:  # 遞迴遍歷右子樹
        post_order_traversal(root.rchild)
    print(root.root, end="  ")  # 列印根結點

3.4.2> 非遞迴實現

需要匯入我們之前寫過的棧,作為臨時儲存空間。如果你還不知道,不妨看看
下面這篇文章:
Smaller Python資料結構:自己動手實現棧

from StackQueueHash.b_1_implementation_stack import ListStack

# 非遞迴實現後序遍歷
def post_order_traversal(root):
    # 後序遍歷 (Post-Order Traversal)(左孩子-右孩子-根結點)
    if not root:
        return
    # 初始化一個棧,臨時存放遍歷到的結點
    stack = ListStack()
    dict_node = {}
    # 遍歷二叉樹
    while root:
        # 結點不為空,而且該結點沒被訪問
        while root and root not in dict_node:
            # 將該結點臨時存入棧
            stack.stack_push(root)
            # 結點後移,向左遍歷
            root = root.lchild
        # 出while迴圈,說明該結點的左結點為空或者該結點已經被訪問了
        root = stack.get_stack_top()  # 獲取上一個結點(根結點)
        stack.stack_pop()  # 出棧
        # 根結點沒有左子樹或者左子樹被遍歷過
        if not root.lchild or root.lchild in dict_node:
            # 在看右子樹
            if not root.rchild or root.rchild in dict_node:
                # 該結點也沒有右子樹或者右子樹也被遍歷了,則訪問
                print(root.root, end="  ")
                # 將被訪問的結點存入字典
                dict_node[root] = "ok"  
                # 根據下一個根結點繼續遍歷二叉樹
                root = stack.get_stack_top()
                stack.stack_pop()  # 出棧
            else:  # 如果有右子樹,而且還沒被訪問,則遍歷右子樹
                stack.stack_push(root)  # 將根結點重新入棧
                root = root.rchild  # 獲取右子樹根結點

3.5> 層次遍歷 (Hierarchical traversal)

3.5.0> 思路圖解

看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)

3.5.1> 遞迴實現

def hierarchical_traversal(root, arr, levels):
    # 層次遍歷 (Hierarchical traversal)(按二叉樹層來遍歷)
    if not root:
        return

    if levels == len(arr):
        arr.append([])  # 分層
    # 新增根結點
    arr[levels].append(root.root)
    # 從左到右,先看左結點
    if root.lchild:
        hierarchical_traversal(root.lchild, arr, levels+1)  # 遞迴遍歷
    # 從左到右,再看右結點
    if root.rchild:
        hierarchical_traversal(root.rchild, arr, levels+1)  # 遞迴遍歷

使用函式裝飾器改進程式碼:

# 思路來源:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-ci-bian-li-by-leetcode/

def hierarchical_traversal1(root):
    # 層次遍歷 (Hierarchical traversal)(按二叉樹層來遍歷)
    if not root:
        return
    arr = []

    def traversal(root, levels):
        # 寫一個內部函式裝飾層次遍歷函式
        if levels == len(arr):
            arr.append([])  # 分層
        # 新增根結點
        arr[levels].append(root.root)
        # 從左到右,先看左結點
        if root.lchild:
            traversal(root.lchild, levels+1)  # 遞迴遍歷
        # 從左到右,再看右結點
        if root.rchild:
            traversal(root.rchild, levels+1)  # 遞迴遍歷

    traversal(root, 0)  # 開始遞迴遍歷
    return arr  # 返回執行結果

3.5.2> 非遞迴實現

為什麼下面程式碼中臨時儲存結點要用deque雙向佇列呢?主要是層次遍歷中要求要從左往右遍歷,所以使用deque可以從頭出(popleft),這樣操作比單純操作列表(list)效率要高,所以這裡選用了deque。

# 思路來自:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-ci-bian-li-by-leetcode/
from collections import deque

# 層次遍歷非遞迴實現
def hierarchical_traversal(root):
    # 層次遍歷 (Hierarchical traversal)(按二叉樹層來遍歷)
    arr = []  # 存放遍歷結果
    levels = 0  # 記錄層數,從0開始,即第一層
    if not root:
        return arr  # 空樹
    # 樹非空,開始遍歷
    queue = deque([root])  # 結點臨時存放處
    while queue:
        # 新增層
        arr.append([])
        # 計算該層待遍歷結點數
        level_nums = len(queue)
        # for 迴圈遍歷每個結點,訪問結點的子結點(子樹)
        for i in range(level_nums):
            # 結點從左往右出佇列,從左往右遍歷
            node = queue.popleft()
            # 新增(訪問)根結點 【注意吼,只有這裡在訪問】
            arr[levels].append(node.root)
            # 如果根結點左子樹存在,則加入遍歷佇列
            if node.lchild:
                queue.append(node.lchild)
            # 如果根結點右子樹存在,則加入遍歷佇列
            if node.rchild:
                queue.append(node.rchild)
        levels = levels + 1  # 向下遍歷,層數加1
    return arr  # 返回遍歷結果

今天還是很乾的貨了,也很花了一些時間整理,一來加深自己印象,再者希望對大家學習二叉樹有幫助。難點在二叉樹的非遞迴遍歷上,我把程式碼寫的很通俗易懂,想到就寫,並且加了大量註釋,在變數名、函式名、類名、包名都是嚴格按照標準寫的(程式碼規範+自己的習慣),可能像白話文一樣,裡面也有很多可以優化的地方,之所以現在沒直接優化,是為了方便大家閱讀學習,堅持。

附:不要怕刷演算法題,老表教你

如果你看了本文的程式碼+註釋+思路都晦澀難懂的話,我建議你不要只看,可以把電腦拿出來,手機開啟簡說Python公眾號,開啟這篇文章,然後用電腦對著文章裡的程式碼一個字一個字的先敲一遍,先不管裡面到底說了啥。
第一遍過後,你可能還是覺得索然無味,甚至可能出錯,沒關係,咱們再來一遍;
第二遍過後,你應該有了些感覺了,不管有沒有感覺,你都得開始下一步了,開始跟著註釋讀程式碼,在沒個你覺得難的程式碼後面加個print,看看他到底是了啥;
第三遍,這個時候你真的該有點感覺了,趁熱打鐵,草稿紙拿出來,字再醜,也得畫一畫,不管你是畫符還是畫花,都給我在紙上把程式碼邏輯寫一遍(什麼邏輯,就是程式碼每一句做了寫啥,幹了些啥,那些變數有了變化,變成啥樣了) ;
第四遍,也許第三遍你得走好多遍,那都是你的本事,然後也會成為你的成功堡壘的一塊磚,再讀程式碼,然後自己在草稿紙上根據自己的思考,對問題的認識,寫出你想到的解決方法,記住了,先寫思路,然後把思路變成程式碼,思路也就是虛擬碼,他告訴你每步該怎麼走;
第五遍,把你草稿紙上的程式碼輸入到電腦,執行,驗證,改錯,有問題重複上面的1-5步;
當然,你還需要會除錯程式碼,這裡,我分享了我最長用的三種除錯程式碼的方法,也許對你也有用。一般我感覺程式碼邏輯比較繞或者難理解的時候,我一般使用三種方法:





1.手寫邏輯過程,跟著程式碼一步一步來

優點:自己主觀思考比較多,整個過程下來,基本能搞清楚,還能舉一反三 缺點:易出錯,耗時長
比較適合簡單的邏輯程式碼
看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)

2.print實時輸出每行程式碼執行後,所有變數的變化

優點:程式碼執行過程不需動腦,不會出錯
缺點:耗時還是比較長,後面推導過程還得自己一步步來,本質上與方法一無異
同樣適合簡單量小的邏輯程式碼
看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)


3.單步除錯,設定斷點,跨越式除錯

優點:基本上解決前面兩種方法的問題
缺點:耗時(感覺無法避免 除非自己是大神)
幾乎適合所有程式碼
看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)
最後,你應該能完成學習,如果完不成,你可以加微信jjxksa888,我的個人微信,一起聊聊你的問題,我們還有學習交流群,供大家交流學習。
有永遠的方法論,但堅持才是有效的。




本文程式碼思路部分來自書籍《Python程式設計師面試寶典》,書中部分程式碼有問題,文中已經修改過了,並新增上了豐厚的註釋,方便大家學習,後面我會把所有內容開源放到Github上,包括程式碼,思路,演算法圖解(手繪或者電腦畫),時間充裕的話,會錄製視訊。希望大家多多支援。

大家好,我是老表 覺得本文不錯的話,轉發、留言、點贊,是對我最大的支援。

歡迎關注微信公眾號:簡說Python 關注後回覆:1024,可以領取精選學習資源。

每日留言
說說你讀完本文感受?
或者一句激勵自己的話?
(字數不少於15字)
留言贈書
《Python程式設計師面試演算法寶典》是一本講解程式設計師面試筆試演算法的書,程式碼採用Python語言編寫,書中除了講解如何解答演算法問題以外,還引入了例子輔以說明,讓讀者更容易理解。本書幾乎將程式設計師面試筆試過程中演算法類真題一網打盡,在題目的廣度上,通過各種渠道,蒐集了近3年來幾乎所有IT企業面試筆試演算法的高頻題目,所選擇題目均為企業招聘使用題目。
看完這篇文章,別再說二叉樹了,樹根都給你拔起來了(圖解+程式碼+詳細思路)
掃碼檢視書籍詳情






留言贈書:《Python程式設計師面試演算法寶典》

怎麼加入刻意學習隊伍
點我,看文末彩蛋
留言有啥福利
點我就知道了
想進學習交流群
加微信:jjxksa888
備註:簡說Python





2小時快速掌握Python基礎知識要點。
完整Python基礎知識要點
Python小知識 | 這些技能你不會?(一)
Python小知識 | 這些技能你不會?(二)
Python小知識 | 這些技能你不會?(三)
Python小知識 | 這些技能你不會?(四)
點在看,是你自己的選擇
轉發,也是你自己的選擇
也許,可以證明你看過
也許,可以證明你學了