Python函數返回值、作用域以及樹的概念

函數的返回值
總結:
Python函數使用return語句返回“返回值”
所有的函數都有返回值，如果沒有return語句，隱式調用return None
return 語句并不是函數語句塊的最后一條語句
一個函數可以存在多個return語句，但是只有一條可以被執行。如果沒有一條return語句被執行到，隱式調用return None
如果有必要，可以顯示調用return None，可以簡寫return
如果函數執行了return語句，函數就會返回，當前被執行return語句之后的其他語句就不會被執行了
作用：結束函數調用、返回值
返回多個值
函數不能同時返回多個值
return [1,3,5]是指明返回一個列表，返回的一個列表對象
return 1,3,5 看似返回多個值，其實會把這幾個值，封裝成為一個元組，進行返回
函數的嵌套
在一個函數中定義了另外一個函數
函數有可見范圍，作用域
內部函數不能被外部直接使用，會拋NameError異常

作用域
一個標識符的可見范圍，就是標識符的作用域
全局作用域
在整個程序的運行環境中都可見
局部作用域
在函數、類等內部可見
局部變量使用范圍不能超過其所在的局部作用域

外層變量的作用域在內層作用域可見

代碼：
x = 1
def doo():
x += 2
return x
上面的代碼，執行時會報錯，
UnboundLocalError Traceback (most recent call last)
in ()—-> 1 doo()

in doo() 1 x = 1 2 def doo():—-> 3 x += 1 4 return x

UnboundLocalError: local variable ‘x’ referenced before assignment

x += 1其實是 x = x +1
Python中的變量是賦值即定義，在賦值之前x已經被聲明是是一個本地變量，但是在函數內部的局部作用域中沒有發現，對x進行賦值就被調用，所以會報錯，函數體外面x = 1 是全局變量

解決方法：可以講doo內部的聲明為global x 這樣 doo內部變量x就會聲明為外部的作用域

global使用原則
外部作用域變量會內部作用域可見，但也不要在內部作用域中直接只用，因為函數的目的是封裝，盡量與外界隔離
如果函數使用了外部全局變量，使用函數的形參傳參解決
不用global

閉包：
自由變量：未在本地作用域中定義的變量，例如定義在內層函數外的外層函數的作用域變量
閉包：指的是內層函數引用到了外層函數的自由變量，就形成了閉包

nonlocal關鍵字
使用nonlocal關鍵字，將變量標記為不在本地作用于域定義，而在上級的某一級局部作用域中定義，但不能在全局作用域中定義
def counter():
count = 0
def inc():
nonlocal count#定義count為nonlocal
count += 1
return count
return inc

默認值作用域
Python把函數的默認值以元組的形式，放在屬性中，這個屬性會伴隨整個函數的生命周期
查看 函數名.__defaluts__屬性

屬性__defaults__中使用元組保存所有參數的默認值
屬性__kwdefaults__中使用字典保存所有keyword-only參數默認值

如果函數參數的默認值是一個類似列表的可變類型，那么它的元素的默認值有可能會發生改變
如果想使函數默認值的可變類型里的元素不發生改變
第一種方式：
使用影子拷貝的創建一個新的對象，永遠不能改變傳入的參數
第二種方式
通過值的判斷就可以領會的選擇創建或者修改傳入的對象
變量名的解析原則LEGB

函數的銷毀
全局函數銷毀
重新定義一個同名函數
del語句刪除函數對象
程序結束時
局部函數銷毀
重新在上級作用域定義同名函數
del語句刪除函數對象
上級作用域銷毀時

樹
非線性結構，每個元素都可以多個前驅和后繼
樹是n（n>=0）個元素的集合
樹只有一個特殊的沒有前驅的元素，稱為樹的根root
樹中除了根節點外，其余元素只能有一個前驅，可以有零個或者多個后繼
遞歸定義
樹T是n個元素的集合，n=0時，稱為空樹
有且只有一個特殊的元素根，剩余元素都可以被劃分為m個互不相交的集合，一個集合都是樹，稱為T的字樹
字數也有自己的根

樹的概念
結點：樹中的數據元素
結點的度degree：結點擁有的字樹的數目稱為度，記作d(v)
葉子結點：結點的度為0，稱為葉子結點leaf、終端結點、末端結點
分支結點：結點的度不為0，稱為非終端結點或者分支結點
分支:結點之間的關系
內部結點：除根結點外的分支結點，當然也不包括葉子結點
樹的度是樹內各節點度的最大值

孩子結點：結點的字數的根結點稱為該節點的孩子
雙親結點：一個結點是它各字數的根結點的雙親
兄弟結點：具有相同雙親節點的結點
祖先結點：從根結點到該結點所經分支上所有的結點。
子孫結點：結點的所有字樹上的結點都稱為該結點的子孫節點
結點的層次：根結點為第一層，根的孩子是第二層。。。。
堂兄弟：雙親在同一層的結點

路徑長度=路徑上的結點樹-1 即分支數

樹的特點：
唯一的根
字樹不相交
除根以外，每個元素都只能有一個前驅，可以有零個或多個后繼
根結點沒有雙親節點，葉子結點沒有孩子結點

二叉樹
每個結點最多2棵子樹
二叉樹不存在度數大于2的結點

二叉樹的五種基本形態
空二叉樹
只有一個根結點
根結點只有左子樹
根結點只有右字樹
根結點有左子樹和右字樹

斜樹
左斜樹，所有結點都只有左子樹
右斜樹，所有結點都只有右子樹
滿二叉樹
一顆二叉樹的所有分支結點都存在左子樹和右子樹，并且所有葉子結點只存在最下面一層
k為深度，則結點總數為2**k – 1

完全二叉樹
若二叉樹的深度為k，二叉樹的層數從1到k-1層的結點樹都都達到了最大數，在第K層的所有結點（左邊必須全部填滿不能有空余）都集中在最左邊，這就是完全二叉樹
滿二叉樹一定是完全二叉樹，但完全二叉樹不是滿二叉樹
k是深度，完全二叉樹的結點樹最大值是2**k -1 ，達到最大值的時候是滿二叉樹

二叉樹的性質
在二叉樹的第i層上至多有2**（i-1）個結點
深度為k的二叉樹，至多有2**k-1個結點

葉子結點樹-1=度數為2的結點樹

含有n的結點的二叉樹的高度至多為n，最小為math.ceil(log2(n+1))

如果一棵n個結點的完全二叉樹，按照層序編號
如果i = 1，則結點i是二叉樹的根，無雙親；如果i>1，則雙親是int(i/2),向下取整，結點編號整除向下取整得到的是父節點的編號
父節點是i，那么左孩子的結點就是2i，右孩子的結點是2*i+1
n是結點樹
如果2*i > n,則結點i無左孩子，即結點為葉子結點，否則其左孩子的結點存在編號為2*i
如果2*i +1 > n，則結點i無右孩子，注意這里并不能說明結點i沒有左孩子，否則右孩子的結點存在編號2i+1