找二叉樹中給定元素的的左孩子結點_[校招-算法題] 二叉樹基礎算法1

二叉樹是面試中常考的資料結構，因為涉及大量指針操作，是以可以考察思維的嚴謹性和靈活性。但是校招中的二叉樹題規律性很強，是以需要總結一下。

各種常見的二叉樹概念

二叉樹：每個結點最多有兩個子樹（左子樹和右子樹）的樹結構。

節點的層次：一個結點的層次直覺上來說就是其所在的行，其中根結點層次為1。

二叉樹的深度：二叉樹的深度指二叉樹的最大葉子結點所在的層。二叉樹的深度求解可用遞歸方式實作，等于max(左子樹深度，右子樹深度)+1。

結點的度：二叉樹結點的度指該結點分支的個數，取值為0、1或2。

結點種類：

• 根結點：第一層的結點
• 葉子結點：度為0的結點
• 分支結點：度不為0的結點
• 孩子結點：結點的子樹的根稱為該結點的孩子結點
• 兄弟結點：同一雙親的孩子結點
• 祖先結點：從根到該結點上所經分支的所有結點
• 子孫節點：以某結點為根的子樹中任一結點都稱為該結點的子孫節點

建立一棵二叉樹

class 
           

代碼構造的二叉樹

二叉樹的分類

滿二叉樹：

除葉結點外每一個結點都有左右子結點并且葉子結點都處在最底層的二叉樹。

完全二叉樹：

除最後一層外，其他各層的結點數都達到最大，最後一層的葉子結點都是從左往右依次排布。

二叉排序樹（BST）：

或者是一棵空樹，或者具有如下性質：（1）若左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值；（2）若右子樹不為空，則右子樹上所有結點的值均大于它的根結點的值；（3）左右子樹也分别為二叉排序樹；（4）沒有值相等的結點。

平衡二叉樹（AVL）：

一種二叉排序樹，其中每個結點的左子樹和右子樹的高度差至多等于1。要麼它是一棵空樹，要麼它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。

二叉樹的周遊

二叉樹最重要的是四種周遊算法：前序周遊（遞歸和非遞歸）、中序周遊（遞歸和非遞歸）、後序周遊（遞歸和非遞歸）和層次周遊。

前序周遊（根左右）

先通路根結點，然後通路左子樹，再通路右子樹。

遞歸算法：

def 
           

非遞歸算法：

使用棧來臨時存儲節點：（1）列印根結點資料；（2）把根結點的right入棧，周遊左子樹；（3）周遊完左子樹傳回時，棧頂元素應為right，出棧，周遊以該結點為根的子樹

def 
           

中序周遊（左根右）

遞歸算法：

def 
           

非遞歸算法：

使用棧來存儲臨時節點，（1）先将根節點入棧，周遊左子樹；（2）周遊完左子樹傳回時，棧頂元素應為根節點，此時出棧，并列印節點資料；（3）再中序周遊右子樹。

def 
           

後序周遊（左右根）

遞歸算法：

def 
           

非遞歸算法：

使用棧來存儲臨時節點，使用哈希表來記錄狀态。

假設root時周遊樹的根指針，後序周遊要求在周遊完左、右子樹後再通路根，需要判斷根結點的左、右子樹是否均周遊過。使用标記法，節點入棧時，将該結點存入哈希表，值為0表示周遊左子樹前的現場保護，值為1表示周遊右子樹前的現場保護。

首先将root，周遊左子樹；傳回後，修改哈希表中該結點的值為1，周遊右子樹，最後通路根節點。

def 
           

層次周遊

層次周遊需要使用一個輔助隊列，初始元素是根結點。當隊列不為空時，每次列印隊列最前端結點的值，然後判斷該結點左子結點是否存在，存在就壓入隊列；再判斷該結點右子節點是否存在，存在就壓入隊列。

def 
           

二叉樹周遊的應用

分層列印二叉樹

在層次周遊的基礎上，使用兩個額外的變量分别儲存目前層需要列印的結點數和下一層的結點數。

def 
           

之字形列印二叉樹

def 
           

判斷二叉樹是否為完全二叉樹

算法：

1. 如果為空樹，直接傳回True；
2. 采用層次周遊，使用一個變量leaf（預設為0）；
3. 如果目前結點有右孩子，且沒有左孩子，直接傳回False；
4. 如果目前結點沒有兩個孩子，那麼leaf=1，之後的節點必須都為葉節點，即不能有孩子，否則傳回False；
5. 周遊結束後沒有傳回，那麼傳回True。

def