返回值&&作用域&&树

返回值

举例：

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，结点按照层序编号如下图