函數，作用域，樹，簡介

函數嵌套

在一個函數中定義了另一個函數
函數有可見範圍，這就是 作用域 概念
内部函數不能在外部直接使用，會抛NameError異常，因為它不可見           

作用域

一個辨別符的可見範圍，這就是辨別符的作用域。一般常說的是變量的作用域
全局作用域
在整個程式運作環境中都可見
局部作用域
在函數、類等内部可見
局部變量使用範圍不能超過其所在局部作用域           

全局變量global

x = 5
def foo():
    global x
    x += 1
使用global關鍵字變量，将foo内的x聲明為使用外部的全局作用域中定義的x
全局作用域中必須有x的定義
内部作用域使用x = 5 之類的指派語句會重新定義局部作用域使用的變量x，但是一旦這個作用域中使用global聲明x為全局的,那麼x= 5相當于在全局作用域的變量x 指派           

nonlocal

使用了nonlocal關鍵字，将變量标記為不在本地作用域定義，而在上級的某一級局部作用域中定義，但不能是全局作用域中定義
内部函數使用nonlocal 關鍵字聲明變量在上級作用域而非本地作用域中定義           

閉包

自由變量：未在本地作用域中定義的變量
閉包： 就是一個概念，出現在嵌套函數中，指的是内層函數引用到了外層函數的自由變量，就形成了閉包。           

變量名解析原則LEGB

local  本地作用域、局部作用域的local命名空間。函數調用時建立，調用結束時消亡
Enclosing，Python2.2時引入了嵌套函數，實作了閉包，這個就是嵌套函數的外部函數命名空間
Global，全局作用域，即一個子產品的命名空間，函數被import時建立，解釋器退出時消亡
Build-in  内模組化塊的命名空間，生命周期從python解釋器啟動時建立到解釋器退出時消亡。           

遞歸

自己調用自己           

格式：
    lambda 參數清單 ：表達式
    參數清單不需要小括号
    冒号是用來分割參數清單和表達式的
    不需要用return，表達式的值，就是匿名函數傳回值
    lambda表達式（匿名函數）隻能寫在一行上，被稱為單行函數           

生成器generator
    生成器是指生成器對象，可以由生成器表達式得到，也可以使用yield關鍵字得到一個生成器函數，調用這個函數得到一個生成器對象
生成器函數
    函數體中包含yield語句的函數，傳回生成器對象
    生成器對象，是一個可疊代對象，是一個疊代器
    生成器對象，是延遲計算、惰性求值的
    包含yield語句的生成器函數生成 生成器對象的時候，生成器函數體不會立即執行
    next(generator)會從函數的目前位置向後執行到之後碰到的第一個yield 語句，會彈出值，并暫停函數執行
    再次執行next函數，和上一條一樣的處理過程
    沒有多餘的yield語句能被執行，繼續調用next函數，會抛出StopIteration異常           

普通定義
    非線性結構，每個元素可以有多個前驅和後繼
    樹是n(n>=0) 個元素的集合
    n= 0 時，為空樹
    樹隻有一個特殊的沒有前驅的元素，稱為樹的根Root
    樹中除了根節點外，其餘隻能有一個前驅，可以有零個或多個後繼
遞歸定義
    樹T是n(n>=0)個元素的集合。n=0時，稱為空樹
    有且隻有一個特殊元素根，剩餘元素都可以被劃分為m個互補相交的集合T1、T2、...T  m，每一個集合都是樹，稱為T的樹Subtree
    子樹也有自己的根

概念
    結點 ：樹中的資料元素
    結點的度degree：結點擁有子樹的數目稱為度，記作d(v)
    葉子結點：結點的度為0，稱為葉子結點leaf、終端結點、末端節點
    分支結點：結點的度不為0，稱為非終端結點或分支結點
    分支：結點之間的關系
    内部結點：除去根和葉子結點外的分支結點
    樹的度是樹内各結點的度的最大值
    結點的層次（Level)：根結點為第一次層，根的孩子為第二層，以此類推，記作L(v）
    樹的深度（高度）：樹的層次的最大值
    有序樹：結點是子樹是有順序的，不能交換
    無序樹：結點的子樹是無順序的，可以交換
    路徑：樹中的k個結點n1,n2...nk，滿足ni是n(i+1)的雙親，成為n1到nk的一條路徑。就是一條線串下來的，前一個都是後一個的前驅結點
    路徑長度 = 路徑上的節點數-1，也就是分支數
    森林：m(m>=0)棵不相交的樹 集合
        對于結點而言，其子樹的集合就是森林。

樹的特點
    唯一的根
    子樹不相交
    除了根以外，每個元素都隻能有一個前驅，可以有零個或多個後繼
    根結點沒有雙親結點（前驅），葉子結點沒有孩子結點（後繼）
    雙親結點比孩子結點的層次小1

二叉樹
    每個結點最多有兩個子樹
    二叉樹不存在度數大于2 的結點
    它是有序樹，左子樹，右子樹是有順序的，不能交換順序
    即使某個結點隻有一顆子樹，也要确定它是左子樹還是右子樹
    二叉樹的五種基本形态
    空二叉樹
    隻有一個根結點
    根節點隻有左子樹
    根節點隻有右子樹
    根結點有左子樹和右子樹
斜樹
    左斜樹，所有的結點都隻有左子樹
    右斜樹，所有的結點都隻有右子樹
滿二叉樹
    一個二叉樹的所有分支結點都存在左子樹和右子樹，并且所有的葉子結點都隻存在在最下面一層
    同樣深度二叉樹中，滿二叉樹結點最多
    k 為深度（1<=n),則結點總數為2^k-1
    完全二叉樹Complete Binary Tree
    若二叉樹的深度為k，二叉樹的層數從1到k-1層的結點數都達到了最大個數，在第k層的結點都集中在最左邊，這就是完全二叉樹
    完全二叉樹由滿二叉樹引出
    滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹
    k為深度（1<=k<=n),則結點總數最大值為2^k-1，當達到最大值的時候就是滿二叉樹
二叉樹性質
    高度為k的二叉樹，至少有K個結點
    含有n(n>=1)的結點的二叉樹高度至多為n。最小為math.ceil(log2(n+1)),不小于對數值的最小整數，向上取整
    具有n個結點的完全二叉樹的深度為int(log2n)+1或者math.ceil(log2(n+1))