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