返回值&&作用域&&樹

返回值

舉例：

In [7]: def showplus(x):

…: print(x)

…: return x+1#返回值

…:

In [8]: showplus(5)

Out[8]: 6

#舉例2：

In [9]: def showplus(x):

…: print(x)

…: return x+1

…: print(x+1)

In [10]: showplus(6)#通過此處打印結果證明return后的代碼不執行

Out[10]: 7

多條return語句

#分支解構雙return測試：

In [11]: def guess(x):

…: if x>3:

…: return “>3”

…: else:

…: return “<=3”

In [12]: print(guess(4))#結果證明分支解構可以使用雙return

In [13]: print(guess(2))

<=3

##直接雙return測試：

In [14]: def showplus(x):

…: print(x)

…: return x+1

…: return x+2

In [15]: showplus(4)#此處結果證明第二個return無法執行

Out[15]: 5

##舉例3：

In [16]: def fn(x):

…: for i in range(x):

…: if i>3:

…: return i

…: else:

…: print(‘{}is not greater than 3’.format(x))

In [21]: fn(5)#i小于3時打印else_print

5is not greater than 3

Out[21]: 4##當值大于3時返回i值

In [22]: fn(1)

1is not greater than 3

函數返回值總結：

python函數使用return語句返回“返回值”

所有函數都有返回值，如果沒有return，隱式調用return None

return語句并不一定是函數語句塊的最后一條語句。例如條件分支

一個函數可以存在多個return語句，但是只有一條可以被執行。如果沒有一條return隱式返回None

如果有必要，可以顯示調用return，可以簡寫成return

如果函數執行了return語句，函數就會返回，當前被執行的return語句之后的其他語句不被執行

作用：結束函數調用，返回return值

返回多個值

In [23]: def showlist():

…: return [1,2,4]

In [24]: showlist()#此時調用函數時返回一個列表

Out[24]: [1, 2, 4]

In [28]: def showlist():

…: return 1,2,3

In [29]: showlist()#return多值返回默認用tuple來封裝

Out[29]: (1, 2, 3)

In [29]: showlist()

Out[29]: (1, 2, 3)

In [30]: a,b,c = showlist()#使用解構提取更方便。

In [31]: a

Out[31]: 1

In [32]: b

Out[32]: 2

In [33]: c

Out[33]: 3

返回多值總結：

函數不能同時返回多個值

return [1,2,3]時指明返回一個列表，是一個列表對象

return 1,3,4看似是返回多個值，隱式的被python封裝成一個元組

函數嵌套

解釋：在一個函數中定義了另一個函數

In [34]: def outer():

…: def inner():

…: print(“inner”)

…: print(“outer”)

…: inner()

…: outer()

…: inner()#在外部無法調用函數內部的函數，如下報錯提示inner沒有定義

…:

outer#調用outer函數時print打印

inner#調用outer函數時觸發inner函數打印

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-34-24eaf14ce604> in <module>()

5 inner()

6 outer()

—-> 7 inner()

NameError: name ‘inner’ is not defined

作用域***

概念：一個標識符的可見范圍，這就是標識符的作用域，一般常說的是變量的作用域

#舉例：

In [35]: x=5##定義全局變量

In [36]: def foo():

…: print(x)#此時函數內部可以調用外部的全局變量

…:

In [37]: foo()

In [38]: def foo():

…: x += 1#用此方法會報錯，原因：”x += 1″==”x = x + 1″,相當于在foo內部定義了一個局部變量x，那么foo內部所有x都是這個局部變量的x了，但是這個x還沒完成賦值就被右邊拿來+1操作了（賦值及定義程序會先設置一個新的x的標識符但是x還沒有設置值，故用x再去+1會提示本地變量引用前沒有賦值。UnboundLocalError）

…: print(x)

…:

In [39]: foo()

—————————————————————————

UnboundLocalError Traceback (most recent call last)

<ipython-input-39-624891b0d01a> in <module>()

—-> 1 foo()

<ipython-input-38-512b125c7e6b> in foo()

1 def foo():

—-> 2 x += 1

3 print(x)

UnboundLocalError: local variable ‘x’ referenced before assignment

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

#舉例：

In [40]: def fn1():##在函數內部設置標識符x

…: x = 1

…:

In [41]: def fn2():##在次函數中調用上個函數中的x變量

…: print(x)

In [45]: fn1()

In [46]: fn2()#此時報錯因為函數fn1中的x是本地變量無法再函數外部調用

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-46-af5ceffc3832> in <module>()

—-> 1 fn2()

<ipython-input-41-d686ebdc00e5> in fn2()

1 def fn2():

—-> 2 print(x)

NameError: name ‘x’ is not defined

In [47]: print(x)

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-47-81745ac23551> in <module>()

—-> 1 print(x)##當然在在外部也是無法調用的

NameError: name ‘x’ is not defined

嵌套解構

通過下面例子可以看出
- 外層變量作用域在內層作用域中可見
- 內層作用域inner中如果定義了o=97，相當于在當前作用域重新定義了一個新的o變量，但是這個o沒有覆蓋外層作用域中的o

In [48]: def outer1():

…: o = 65

…: def inner():

…: print(“inner{}”.format(o))

…: print(chr(o))

…: print(“outer{}”.format(o))

…: inner()

…:

In [50]: outer1()#從結果可以看出大函數內部的子函數可以使用父函數的標識符

outer65

inner65

In [51]: def outer1():

…: o = 65

…: def inner():

…: o = 97

…: print(“inner{}”.format(o))

…: print(chr(o))

…: print(“outer{}”.format(o))

…: inner()

…:

In [52]: outer1()#此結果顯示子函數的同名標識符要優先于復函數的標識符

outer65

inner97

全局變量

全局變量global
使用golbal關鍵字變量，將foo內的x聲明為使用外部的全局作用域中定義的x
全局作用域中必須有x的定義
global作用范圍，只在聲明global的局部作用域和外部全局作用域中生效

In [56]: x=5

In [58]: def foo():

…: global x#將x聲明為全局變量

…: x +=1

…:

In [59]: foo()

In [60]: x

Out[60]: 6

#如果全局中沒有定義y值會報錯：

In [62]: def foo():

…: global y

…: y +=1

…:

In [63]: foo()

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-63-624891b0d01a> in <module>()

—-> 1 foo()

<ipython-input-62-d7ef84539f12> in foo()

1 def foo():

2 global y##此處y值并沒有在外部聲明，故報錯，當然也可以在函數內部聲明報錯消失。

—-> 3 y +=1

NameError: name ‘y’ is not defined

y在內部作用域為一個外部作用域的變量賦值，所以在golbal下面加上y = 1時，y+=1不會報錯，注意這里的y的作用域還是全局的

global總結：

x += 1這種特殊形式產生的錯誤原因，是因為先引用后賦值造成的。而python動態語言是賦值才算定義，才能被引用。解決辦法：在這條語句之前加上x=0之類的賦值語句，或者使用global告訴內部作用域，去全局作用域查找變量定義。

內部作用域使用x=5之類的賦值語句會重新定義局部作用域的變量x，但是一旦這個作用域中使用global聲明x為全局的，那么x=5相當于為全局作用域的變量x賦值

使用規則：不用global如果函數需要使用外部全局變量，請使用函數的形參傳參解決

閉包

自由變量：未在本地作用域中定義的變量，例如定義在內部函數外的外層函數的作用域中的變量應用在函數嵌套中。隨著外部函數的消亡，自由變量不會消亡以為在內層函數中還會調用
閉包：出現在嵌套函數中，指的是內層函數引用到了外層函數的自由變量就形成了閉包。很多語言都有這個概念例如javascript

#閉包舉例一：Python2中如果要修改外部函數自由變量，只有這一種方法：

In [72]: def counter():

…: c = [0]

…: def inc():

…: c[0] += 1

…: return c[0]

…: return inc

…:

In [73]: foo = counter()

In [74]: foo

Out[74]: <function __main__.counter.<locals>.inc>

In [75]: print(foo(),foo())

1 2

In [76]: c = 100

In [77]: print(foo())

#閉包舉例二常用方式跟一類似：

In [92]: def counter():

…: c = [5]#自由變量

…: a = 10#非自由變量，因為inner內部函數中沒有調用

…: def inner():

…: c.append(6)

…: return c

…: return inner

…:

In [93]: foo = counter()

In [94]: print(foo())#此時內部函數已經改變了外部函數的變量函數。

[5, 6]

#閉包舉例三：

In [89]: def foo():

…: global count

…: count=0

…: def inc():

#count=1#這樣用不會報錯，但是不是閉包了，因為count已經重新定義

…: return count#只要內部函數用到了外部函數的自由變量即為閉包

…: return inc

…:

In [90]: abc = foo()

In [91]: print(abc())

代碼解析：c[0] += 1,c在counter函數中定義過了，而且inc中的使用方式是為c的元素修改值，而不是重新定義變量。c=100不會生效因為inc中的c使用的是函數counter中的c而非外部全局變量。這種方法是python2中實現閉包的方式，python3中使用nonlocal關鍵字
[閉包應用于裝飾器中]

nonlocal關鍵字

概念：將變量標記為上級的局部作用域中定義，但不能是全局作用域中定義

#舉例：

In [1]: def counter():

…: count = 0

…: def inx():

…: nonlocal count#標記為上級的局部作用域中定義的變量，此處為自由變量

…: count += 1

…: return count

…: return inx

…:

In [2]: foo = counter()

In [3]: foo()

Out[3]: 1

In [4]: foo()

Out[4]: 2

#舉例二：錯誤

In [5]: a = 50

In [6]: def counter():

…: nonlocal a#提示錯誤因為a是在外部作用域中定義的無法使用nonlocal

…: a += 1

…: print(a)

…: count = 0

…: def inx():

…: nonlocal count

…: count += 1

…: return count

…: return inx

…:

File “<ipython-input-6-91bd7a67f269>”, line 2

nonlocal a

SyntaxError: no binding for nonlocal ‘a’ found

上述代碼解釋：
count 是外層函數的局部變量，被內部函數引用
內部函數使用nonlocal關鍵字聲明count變量在上一級作用域中
舉例一，代碼可以正常使用，且形成閉包
舉例二，不能正常運行，變量a不能在全局作用域中

默認值作用域

#舉例一：

In [7]: def foo(xyz=1):

…: print(xyz)

…:

In [8]:

In [8]: foo()

In [9]: foo()

In [10]: print(xyz)#當前作用域沒有xyz變量

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-10-2cf093bba2e6> in <module>()

—-> 1 print(xyz)

NameError: name ‘xyz’ is not defined

#舉例二：

In [11]: def foo(xyz=[]):

…: xyz.append(1)

…: print(xyz)

…:

In [12]: foo()

[1]

In [13]: foo()#因為函數也是對象，python把函數的默認值放在了這個屬性中，這個屬性就伴隨著這個函數對象的整個生命周期

[1, 1]

In [14]: print(xyz)#當前作用域沒有xyz變量

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-14-2cf093bba2e6> in <module>()

—-> 1 print(xyz)

NameError: name ‘xyz’ is not defined

In [15]: foo.__defaults__

Out[15]: ([1, 1],)

#舉例三：

In [19]: def foo(xyz=[],u=’abc’,z=123):

…: xyz.append(1)

…: return xyz

…:

In [20]: print(foo(),id(foo))#獲取函數返回值及函數地址

[1, 1] 431432824904

In [21]: print(foo.__defaults__)

([1, 1], ‘abc’, 123)

In [22]: print(foo(),id(foo))#通過跟上面比較，函數地址并沒有改變

[1, 1, 1, 1] 431432824904

In [23]: print(foo.__defaults__)

([1, 1, 1, 1], ‘abc’, 123)

例子三說明,函數地址并沒有變，就是說函數這個對象沒有變，調用它，他的屬性__defaults__中使用元組保存所有默認值
xyz默認值時引用類型，引用類型的元素變動，并不是元組的變化。
非引用類型舉例：

In [28]: def foo(w,u=’abc’,z=123):

…: u = ‘zyx’

…: z = 789

…: print(w,u,z)

…:

In [29]: print(foo.__defaults__)

(‘abc’, 123)

In [30]: foo(‘magedu’)

magedu zyx 789

In [31]: print(foo.__defaults__)

(‘abc’, 123)

屬性__defaults__中使用元組保存所有默認值，它不會因為函數體內使用了它而發生變化
可變類型默認值，如果使用了默認值，就可以修改這個默認值
使用場景舉例：

#舉例一：

#函數體內，不改變默認值。

#xyz都是傳入參數或者默認參數的”副本”，如果就想修改原參數，無能為力

In [32]: def foo(xyz=[],u=’abc’,z=123):

…: xyz = xyz[:]#影子拷貝

…: xyz.append(1)

…: print(xyz)

…:

In [33]: foo()

[1]

In [34]: print(foo.__defaults__)

([], ‘abc’, 123)

In [35]: foo()

[1]

In [36]: print(foo.__defaults__)

([], ‘abc’, 123)

In [37]: foo([10])

[10, 1]

In [38]: print(foo.__defaults__)

([], ‘abc’, 123)

In [39]: foo([10,5])

[10, 5, 1]

In [40]: print(foo.__defaults__)

([], ‘abc’, 123)

#舉例二：

#使用不可變類型默認值，如果使用缺省值None就創建一個列表

#如果傳入一個列表，就修改這個列表

In [52]: def foo(xyz=None,u=’abc’,z=123):

…: if xyz is None:

…: xyz = []

…: xyz.append(1)

…: print(xyz)

…:

In [53]: foo()

[1]

In [54]: print(foo.__defaults__)

(None, ‘abc’, 123)

In [55]: foo()

[1]

In [56]: print(foo.__defaults__)

(None, ‘abc’, 123)

In [57]: foo([10])

[10, 1]

In [58]: print(foo.__defaults__)

(None, ‘abc’, 123)

In [59]: foo([10,5])

[10, 5, 1]

In [60]: print(foo.__defaults__)

(None, ‘abc’, 123)

舉例一：使用影子拷貝創建了一個新的對象，永遠不能改變傳入的參數
舉例二：
通過值得判斷就可以靈活的選擇創建或者修改傳入對象
很多函數的定義，都可以看到使用None這個不可變的值作為默認參數，廣泛用法

函數銷毀

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

In [68]: def foo(xyz=[],u=’abc’,z=123):

…: xyz.append(1)

…: def inner(a=10):

…: pass

…: print(inner)

…: def inner(a=100):

…: print(xyz)

…: print(inner)

…: return inner

…:

In [69]: bar = foo()

<function foo.<locals>.inner at 0x0000006477A0E510>

<function foo.<locals>.inner at 0x0000006477A0E488>

In [70]: print(id(foo),id(bar),foo.__defaults__,bar.__defaults__)

431503722424 431503762568 ([1], ‘abc’, 123) (100,)

In [71]: del bar##銷毀局部函數

In [72]: print(id(foo),id(bar),foo.__defaults__,bar.__defaults__)

—————————————————————————

NameError Traceback (most recent call last)

<ipython-input-72-273dde837969> in <module>()

—-> 1 print(id(foo),id(bar),foo.__defaults__,bar.__defaults__)

NameError: name ‘bar’ is not defined

樹

非線性結構，每個元素可以有多個前驅和后繼
樹是n(n≥0)個元素的集合
- n = 0時，稱為空樹
- 樹只有一個特殊的沒有前驅的元素，稱為樹的跟Root
- 樹中除了根節點外，其余元素只能有一個前驅，可以有0個或多個后繼
遞歸定義：
- 樹T是n(n≥0)個元素的集合，n=0時，稱為空樹
- 有且只有一個特殊元素根，剩余元素都可以被劃分成m個互不相交的集合T1、T2、…Tm而每一個集合都是樹，稱為T的子樹subtree
- 子樹也有自己的根
結點：樹中的數據元素
結點的度degree：結點擁有的子樹的數目稱為度，記作d(v)
葉子結點：結點的度為0，稱為葉子結點leaf、終端結點、末端結點
分支結點：結點的度不為0，稱為非終端結點或分支結點
分支：結點之間的關系
內部結點：除根結點外的分支結點，當然不包括葉子結點
樹的度是樹內各結點的度的最大值。D結點度最大為3，樹的度數就是3
孩子結點：結點的子樹的根結點稱為該節點的孩子
雙親結點：一個結點是它各子樹的根結點的雙親
兄弟結點：具有相同雙親的結點
祖先結點：從根結點到該節點所經分支上所有的結點ABD都是G的祖先結點
子孫結點：結點的所有子樹上的結點都稱為該結點的子孫，B的子孫是DGHI
結點的層次：根結點為第一層，依次往下推記做L(v)
樹的深度（高度Depth）：樹的層次的最大值，如下圖的樹深度為4
堂兄弟：雙親在同一層的結點

有序樹：結點的子樹是有順序的（兄弟有大小，有先后順序），不能交換
無序數：結點的子樹是無序的，可以交換
路徑：樹中的k個結點n1、n2、….nk，滿足ni是n(i+1)的雙親，成為n1到nk的一條路徑，就是一條線串下來的，前一個都是后一個的父結點
路徑長度：路徑上結點數-1，也是分支數
森林：m(m≥0)棵不相交的樹的集合
- 對于結點而言，其子樹的集合就是森林，A結點的2棵子樹的集合就是森林
樹的特點：
- 唯一的根
- 子樹不想交
- 除了根以外，每個元素只能有一個前驅，可以有零個或多個后繼
- 根結點沒有雙親結點，葉子結點沒有后繼
- vi是vj的雙親，則(vi)=L(vj)-1,也就是說雙親比孩子結點的層級小1

二叉樹

每個結點最多2棵子樹
- 二叉樹不存在度數大于2的結點
他是有序的樹，左子樹、右子樹是有序的，不能交換次序
即使某個結點只有一顆子樹，也要確定他是左子樹還是右子樹
二叉樹的五種基本形態：
- 空二叉樹
- 只有一個根結點
- 根結點只有左子樹
- 根結點只有右子樹
- 根結點有左右子樹
斜樹
- 左斜樹，所有結點都只有左子樹
- 右斜樹，所有結點都只有右子樹

滿二叉樹

一棵二叉樹的所有分支結點都存在左右子樹，并且所有葉子結點只存在在最下面一層
同樣深度二叉樹中，滿二叉樹結點最多
k為深度（1≤k≤n），則結點總數為2^k-1

完全二叉樹complete binary tree

若二叉樹的深度為k，二叉樹的層數從1到k-1層的結點數都達到了最大個數，在第k層的所有結點都集中在最左邊。這就是完全二叉樹。
完全二叉樹由滿二叉樹引出
滿二叉樹一定是完全二叉樹，但是完全二叉樹不一定是滿二叉樹
k為深度（1≤k≤n），則結點總數最大值為2^k-1,當達到最大值時就是滿二叉樹
完全二叉樹，最下一層的葉子結點都是從左邊連續的擴展
right:

error:因為沒有從左側開始并且連續

二叉樹性質

在二叉樹的第i層上至多有2^(i – 1)個結點（i≥1）
深度為k的二叉樹，至多有2^k-1個結點（k≥1）
對任何一棵二叉樹T，如果其葉子結點數為n0，度數為2的結點為n2,則有n0=n2+1
- 換句話說，就是葉子結點數-1就是度數為2的結點數
- 證明：
高度為k的二叉樹，至少有k個個結點
- 含有n（n≥1）的結點的二叉樹高度至多為n同上
- 含有n（n≥1）的結點的二叉樹高度至多為n，最小為math.ceil(log2(n+1)),不小于對數值得最小整數，向上取整
- 假設高度為h,2^h-1=n => h = log2(n+1),層次數是取整。如果是8個結點，3.1699就要向上取整為4，為4層
具有n個結點的完全二叉樹的深度為int(log2n)+1或者math.ceil(log2(n+1))
如果有一棵n個結點的完全二叉樹深度為性質4，結點按照層序編號如下圖