二叉樹
線性結(jié)構(gòu)
樹形結(jié)構(gòu)
二叉樹
多叉樹
生活中的樹形結(jié)構(gòu)
? 使用樹形結(jié)構(gòu)可以大大提高效率
? 樹形結(jié)構(gòu)是算法面試的重點(diǎn)
樹(Tree)的基本概念
? 節(jié)點(diǎn)、根節(jié)點(diǎn)脐雪、父節(jié)點(diǎn)焦读、子節(jié)點(diǎn)甸各、兄弟節(jié)點(diǎn)
? 一棵樹可以沒有任何節(jié)點(diǎn)双妨，稱為空樹
?一棵樹可以只有 1 個(gè)節(jié)點(diǎn)现拒，也就是只有根節(jié)點(diǎn)
? 子樹寓盗、左子樹灌砖、右子樹
? 節(jié)點(diǎn)的度(degree):子樹的個(gè)數(shù)
? 樹的度:所有節(jié)點(diǎn)度中的最大值
?葉子節(jié)點(diǎn)(leaf):度為 0 的節(jié)點(diǎn)
?非葉子節(jié)點(diǎn):度不為 0 的節(jié)點(diǎn)
?層數(shù)(level):根節(jié)點(diǎn)在第 1 層，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第 2 層傀蚌，以此類推(有些教程也從第 0 層開始計(jì)算)
? 節(jié)點(diǎn)的深度(depth):從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的唯一路徑上的節(jié)點(diǎn)總數(shù)
? 節(jié)點(diǎn)的高度(height):從當(dāng)前節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)總數(shù)
? 樹的深度:所有節(jié)點(diǎn)深度中的最大值
? 樹的高度:所有節(jié)點(diǎn)高度中的最大值
?樹的深度 等于 樹的高度
有序樹基显、無序樹、森林
? 有序樹
樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系
? 無序樹
樹中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有順序關(guān)系 ?也稱為“自由樹”
?森林
由 m(m ≥ 0)棵互不相交的樹組成的集合
二叉樹(Binary Tree)
? 二叉樹的特點(diǎn)
每個(gè)節(jié)點(diǎn)的度最大為 2(最多擁有 2 棵子樹)
左子樹和右子樹是有順序的
即使某節(jié)點(diǎn)只有一棵子樹善炫，也要區(qū)分左右子樹
?二叉樹是有序樹 還是 無序樹?
有序樹
二叉樹的性質(zhì)
?非空二叉樹的第i層撩幽，最多有2i?1 個(gè)節(jié)點(diǎn)(i ≥ 1)
?在高度為h的二叉樹上最多有2h ? 1個(gè)結(jié)點(diǎn)(h ≥ 1)
?對于任何一棵非空二叉樹，如果葉子節(jié)點(diǎn)個(gè)數(shù)為 n0箩艺，度為 2 的節(jié)點(diǎn)個(gè)數(shù)為 n2窜醉，則有: n0 = n2 + 1
假設(shè)度為 1 的節(jié)點(diǎn)個(gè)數(shù)為 n1，那么二叉樹的節(jié)點(diǎn)總數(shù) n = n0 + n1 + n2
二叉樹的邊數(shù) T = n1 + 2 * n2 = n – 1 = n0 + n1 + n2 – 1
因此 n0 = n2 + 1
真二叉樹(Proper Binary Tree)
?真二叉樹:所有節(jié)點(diǎn)的度都要么為 0，要么為 2
?下圖不是真二叉樹
滿二叉樹(Full Binary Tree)
?滿二叉樹:最后一層節(jié)點(diǎn)的度都為 0，其他節(jié)點(diǎn)的度都為 2
?假設(shè)滿二叉樹的高度為 h( h ≥ 1 )惦积，那么
第 i 層的節(jié)點(diǎn)數(shù)量: 2i ? 1
葉子節(jié)點(diǎn)數(shù)量: 2h ? 1
總節(jié)點(diǎn)數(shù)量 n
?h 012 h?1
?n= 2 ?1= 2 +2 +2 +?+2
?h = log2(n+1)
? 在同樣高度的二叉樹中顾稀，滿二叉樹的葉子節(jié)點(diǎn)數(shù)量最多、總節(jié)點(diǎn)數(shù)量最多
? 滿二叉樹一定是真二叉樹，真二叉樹不一定是滿二叉樹
完全二叉樹(Complete Binary Tree)
? 完全二叉樹:對節(jié)點(diǎn)從上至下、左至右開始編號，其所有編號都能與相同高度的滿二叉樹中的編號對應(yīng)
完全二叉樹
滿二叉樹
?葉子節(jié)點(diǎn)只會出現(xiàn)最后 2 層藤抡，最后 1 層的葉子結(jié)點(diǎn)都靠左對齊
?完全二叉樹從根結(jié)點(diǎn)至倒數(shù)第 2 層是一棵滿二叉樹
? 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹
完全二叉樹的性質(zhì)
?度為 1 的節(jié)點(diǎn)只有左子樹
?度為 1 的節(jié)點(diǎn)要么是 1 個(gè)抹估，要么是 0 個(gè)
? 同樣節(jié)點(diǎn)數(shù)量的二叉樹缠黍，完全二叉樹的高度最小
?假設(shè)完全二叉樹的高度為 h( h ≥ 1 )，那么
至少有2h?1 個(gè)節(jié)點(diǎn)(20+21+22+?+2h?2+1)
最多有2h ? 1個(gè)節(jié)點(diǎn)(20+21+22+?+2h?1药蜻，滿二叉樹)
總節(jié)點(diǎn)數(shù)量為 n
?2h?1 ≤n<2h
?h ?1≤log2n<h
?h= floor(log2n) + 1
?floor 是向下取整瓷式，另外，ceiling 是向上取整
?一棵有 n 個(gè)節(jié)點(diǎn)的完全二叉樹(n > 0)谷暮，從上到下蒿往、從左到右對節(jié)點(diǎn)從 1 開始進(jìn)行編號，對任意第 i 個(gè)節(jié)點(diǎn)
如果 i = 1 湿弦，它是根節(jié)點(diǎn)
如果 i > 1 瓤漏，它的父節(jié)點(diǎn)編號為 floor( i / 2 )
如果 2i ≤ n ，它的左子節(jié)點(diǎn)編號為 2i
如果 2i > n ，它無左子節(jié)點(diǎn)
如果 2i + 1 ≤ n 蔬充，它的右子節(jié)點(diǎn)編號為 2i + 1
如果 2i + 1 > n 蝶俱，它無右子節(jié)點(diǎn)
?一棵有 n 個(gè)節(jié)點(diǎn)的完全二叉樹(n > 0)，從上到下饥漫、從左到右對節(jié)點(diǎn)從 0 開始進(jìn)行編號榨呆，對任意第 i 個(gè)節(jié)點(diǎn)
如果 i = 0 ，它是根節(jié)點(diǎn)
如果 i > 0 庸队，它的父節(jié)點(diǎn)編號為 floor( (i – 1) / 2 )
如果 2i + 1 ≤ n – 1 积蜻，它的左子節(jié)點(diǎn)編號為 2i + 1
如果 2i + 1 > n – 1 ，它無左子節(jié)點(diǎn)
如果 2i + 2 ≤ n – 1 彻消，它的右子節(jié)點(diǎn)編號為 2i + 2
如果 2i + 2 > n – 1 竿拆，它無右子節(jié)點(diǎn)
下圖不是完全二叉樹
面試題
?如果一棵完全二叉樹有 768 個(gè)節(jié)點(diǎn)，求葉子節(jié)點(diǎn)的個(gè)數(shù)
假設(shè)葉子節(jié)點(diǎn)個(gè)數(shù)為 n0宾尚，度為 1 的節(jié)點(diǎn)個(gè)數(shù)為 n1丙笋，度為 2 的節(jié)點(diǎn)個(gè)數(shù)為 n2
總結(jié)點(diǎn)個(gè)數(shù) n = n0 + n1 + n2，而且 n0 = n2 + 1
?n = 2n0 + n1 – 1
完全二叉樹的 n1 要么為 0煌贴，要么為 1
?n1為1時(shí)御板，n = 2n0，n 必然是偶數(shù)
?葉子節(jié)點(diǎn)個(gè)數(shù) n0 = n / 2牛郑，非葉子節(jié)點(diǎn)個(gè)數(shù) n1 + n2 = n / 2
?n1為0時(shí)怠肋，n = 2n0 – 1，n 必然是奇數(shù)
?葉子節(jié)點(diǎn)個(gè)數(shù) n0 = (n + 1) / 2井濒，非葉子節(jié)點(diǎn)個(gè)數(shù) n1 + n2 =(n – 1) / 2
葉子節(jié)點(diǎn)個(gè)數(shù) n0 = floor( (n + 1) / 2 ) = ceiling( n / 2 )
非葉子節(jié)點(diǎn)個(gè)數(shù) n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
因此葉子節(jié)點(diǎn)個(gè)數(shù)為 384
國外教材的說法
?Full Binary Tree:完滿二叉樹
所有非葉子節(jié)點(diǎn)的度都為 2
就的國內(nèi)說的“真二叉樹”
?Perfect Binary Tree:完美二叉樹
所有非葉子節(jié)點(diǎn)的度都為 2灶似，且所有的葉子節(jié)點(diǎn)都在最后一層
就是國內(nèi)說的“滿二叉樹”
?Complete Binary Tree:完全二叉樹
跟國內(nèi)的定義一樣
二叉樹的遍歷
? 遍歷是數(shù)據(jù)結(jié)構(gòu)中的常見操作
把所有元素都訪問一遍
? 線性數(shù)據(jù)結(jié)構(gòu)的遍歷比較簡單
正序遍歷
逆序遍歷
? 根據(jù)節(jié)點(diǎn)訪問順序的不同，二叉樹的常見遍歷方式有4種
前序遍歷(Preorder Traversal)
中序遍歷(Inorder Traversal)
后序遍歷(Postorder Traversal)
層序遍歷(Level Order Traversal)
前序遍歷(Preorder Traversal)
? 訪問順序
根節(jié)點(diǎn)瑞你、前序遍歷左子樹、前序遍歷右子樹
7希痴、4者甲、2、1砌创、3虏缸、5、9嫩实、8刽辙、11、10甲献、12
前序遍歷 – 非遞歸
? 利用棧實(shí)現(xiàn)
- 設(shè)置node=root
- 循環(huán)執(zhí)行以下操作
如果 node != null
?對node 進(jìn)行訪問
?將node.right 入棧
? 設(shè)置 node = node.left
如果 node == null
? 如果棧為空宰缤，結(jié)束遍歷
? 如果棧不為空，彈出棧頂元素并賦值給 node
? 利用棧實(shí)現(xiàn)
- 將root入棧
- 循環(huán)執(zhí)行以下操作，直到棧為空
彈出棧頂節(jié)點(diǎn) top慨灭，進(jìn)行訪問
將 top.right 入棧
將 top.left 入棧
中序遍歷(Inorder Traversal)
? 訪問順序
中序遍歷左子樹朦乏、根節(jié)點(diǎn)、中序遍歷右子樹
1氧骤、2呻疹、3、4筹陵、5刽锤、7、8朦佩、9姑蓝、10、11吕粗、12
? 如果訪問順序是下面這樣呢?
中序遍歷右子樹纺荧、根節(jié)點(diǎn)、中序遍歷左子樹
12颅筋、11宙暇、10、9议泵、8 占贫、7、5先口、4型奥、3、2碉京、1
? 二叉搜索樹的中序遍歷結(jié)果是升序或者降序的
中序遍歷 – 非遞歸
? 利用棧實(shí)現(xiàn)
- 設(shè)置node=root
- 循環(huán)執(zhí)行以下操作
如果 node != null
?將node 入棧
? 設(shè)置 node = node.left
如果 node == null
? 如果棧為空厢汹，結(jié)束遍歷
? 如果棧不為空，彈出棧頂元素并賦值給 node ?對node 進(jìn)行訪問
?設(shè)置 node = node.right
后序遍歷(Postorder Traversal)
? 訪問順序
后序遍歷左子樹谐宙、后序遍歷右子樹烫葬、根節(jié)點(diǎn)
1、3凡蜻、2搭综、5、4划栓、8兑巾、10、12忠荞、11蒋歌、9帅掘、7
后序遍歷 – 非遞歸
? 利用棧實(shí)現(xiàn)
- 將 root 入棧
- 循環(huán)執(zhí)行以下操作，直到棧為空
如果棧頂節(jié)點(diǎn)是葉子節(jié)點(diǎn) 或者 上一次訪問的節(jié)點(diǎn)是棧頂節(jié)點(diǎn)的子節(jié)點(diǎn) ? 彈出棧頂節(jié)點(diǎn)奋姿，進(jìn)行訪問
否則
? 將棧頂節(jié)點(diǎn)的right锄开、left按順序入棧
層序遍歷(Level Order Traversal)
? 訪問順序
從上到下、從左到右依次訪問每一個(gè)節(jié)點(diǎn)
7称诗、4萍悴、9、2寓免、5癣诱、8、11袜香、1撕予、3、10蜈首、12
? 實(shí)現(xiàn)思路:使用隊(duì)列
- 將根節(jié)點(diǎn)入隊(duì)
- 循環(huán)執(zhí)行以下操作实抡，直到隊(duì)列為空
將隊(duì)頭節(jié)點(diǎn) A 出隊(duì)，進(jìn)行訪問
將 A 的左子節(jié)點(diǎn)入隊(duì)
將 A 的右子節(jié)點(diǎn)入隊(duì)
四則運(yùn)算
? 四則運(yùn)算的表達(dá)式可以分為3種
前綴表達(dá)式(prefix expression)欢策，又稱為波蘭表達(dá)式
中綴表達(dá)式(infix expression)
后綴表達(dá)式(postfix expression)吆寨，又稱為逆波蘭表達(dá)式
表達(dá)式樹
? 如果將表達(dá)式的操作數(shù)作為葉子節(jié)點(diǎn)，運(yùn)算符作為父節(jié)點(diǎn)(假設(shè)只是四則運(yùn)算)
這些節(jié)點(diǎn)剛好可以組成一棵二叉樹
比如表達(dá)式:A / B + C * D – E
? 如果對這棵二叉樹進(jìn)行遍歷
前序遍歷
– + / A B * C D E
剛好就是前綴表達(dá)式(波蘭表達(dá)式)中序遍歷
A / B + C * D – E
剛好就是中綴表達(dá)式后序遍歷
A B / C D * + E –
剛好就是后綴表達(dá)式(逆波蘭表達(dá)式)
思考
? 如果允許外界遍歷二叉樹的元素?你會如何設(shè)計(jì)接口踩寇？
增強(qiáng)遍歷接口
遍歷的應(yīng)用
? 前序遍歷
樹狀結(jié)構(gòu)展示(注意左右子樹的順序)
? 中序遍歷
二叉搜索樹的中序遍歷按升序或者降序處理節(jié)點(diǎn)
? 后序遍歷
適用于一些先子后父的操作
? 層序遍歷
計(jì)算二叉樹的高度
判斷一棵樹是否為完全二叉樹
根據(jù)遍歷結(jié)果重構(gòu)二叉樹
? 以下結(jié)果可以保證重構(gòu)出唯一的一棵二叉樹
前序遍歷 + 中序遍歷
后序遍歷 + 中序遍歷
?前序遍歷 + 后序遍歷
? 如果它是一棵真二叉樹(Proper Binary Tree)啄清，結(jié)果是唯一的
? 不然結(jié)果不唯一
前序遍歷+中序遍歷重構(gòu)二叉樹
?前序遍歷:4 2 1 3 6 5
?中序遍歷:1 2 3 4 5 6
練習(xí) – 利用前序遍歷樹狀打印二叉樹
練習(xí) - 翻轉(zhuǎn)二叉樹
? https://leetcode-cn.com/problems/invert-binary-tree/
? 請分別用遞歸、迭代(非遞歸)方式實(shí)現(xiàn)
練習(xí) – 計(jì)算二叉樹的高度
?遞歸
?迭代
練習(xí) – 判斷一棵樹是否為完全二叉樹
? 如果樹為空俺孙，返回 false
? 如果樹不為空辣卒，開始層序遍歷二叉樹(用隊(duì)列)
如果 node.left!=null，將 node.left 入隊(duì)
如果 node.left==null && node.right!=null睛榄，返回 false
如果 node.right!=null荣茫，將 node.right 入隊(duì)
如果 node.right==null
? 那么后面遍歷的節(jié)點(diǎn)應(yīng)該都為葉子節(jié)點(diǎn)，才是完全二叉樹
? 否則返回 false
遍歷結(jié)束懈费，返回 true
前驅(qū)節(jié)點(diǎn)(predecessor)
? 前驅(qū)節(jié)點(diǎn):中序遍歷時(shí)的前一個(gè)節(jié)點(diǎn)
如果是二叉搜索樹计露，前驅(qū)節(jié)點(diǎn)就是前一個(gè)比它小的節(jié)點(diǎn)
? node.left != null
舉例:6、13憎乙、8
predecessor = node.left.right.right.right... ? 終止條件:right 為 null
? node.left == null && node.parent != null
舉例:7、11叉趣、9泞边、1
predecessor = node.parent.parent.parent...
? 終止條件:node 在 parent 的右子樹中
? node.left == null && node.parent == null
那就沒有前驅(qū)節(jié)點(diǎn)
舉例:沒有左子樹的根節(jié)點(diǎn)
后繼節(jié)點(diǎn)(successor)
? 后繼節(jié)點(diǎn):中序遍歷時(shí)的后一個(gè)節(jié)點(diǎn)
如果是二叉搜索樹，后繼節(jié)點(diǎn)就是后一個(gè)比它大的節(jié)點(diǎn)
? node.right != null
舉例:1疗杉、8阵谚、4
successor = node.right.left.left.left...
? 終止條件:left 為 null
? node.right == null && node.parent != null
舉例:7蚕礼、6、3梢什、11
successor = node.parent.parent.parent...
? 終止條件:node 在 parent 的左子樹中
? node.right == null && node.parent == null
那就沒有前驅(qū)節(jié)點(diǎn)
舉例:沒有右子樹的根節(jié)點(diǎn)
作業(yè)
?二叉樹的前序遍歷: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ (遞歸+迭代)
?二叉樹的中序遍歷: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/ (遞歸+迭代)
?二叉樹的后序遍歷: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/ (遞歸+迭代)
?二叉樹的層次遍歷: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ (迭代)
?二叉樹的最大深度: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ (遞歸+迭代)
?二叉樹的層次遍歷II: https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
? 二叉樹最大寬度:https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
?N叉樹的前序遍歷: https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
?N叉樹的后序遍歷: https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
?N叉樹的最大深度: https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
? 二叉樹展開為鏈表
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
? 從中序與后序遍歷序列構(gòu)造二叉樹
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
? 從前序與中序遍歷序列構(gòu)造二叉樹
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
? 根據(jù)前序和后序遍歷構(gòu)造二叉樹
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
? 對稱二叉樹
https://leetcode-cn.com/problems/symmetric-tree/
? 樹狀形式打印二叉樹
比如給定一個(gè)二叉搜索樹:[7, 4, 9, 2, 5, 8, 11, 1, 3, 6, 10, 12]
嘗試輸出以下格式
? 開源項(xiàng)目:https://github.com/CoderMJLee/BinaryTrees
? 已知前序奠蹬、中序遍歷結(jié)果，求出后序遍歷結(jié)果
? 已經(jīng)中序嗡午、后序遍歷結(jié)果囤躁，求出前序遍歷結(jié)果
