1.1 数据容器

元组：元组中只有一个元素，必须加逗号。元组内的list的某个元组可以修改，因为元组内存储的是list的指针（内存地址）
序列：内容连续、有序，支持下标索引的一类容器，eg：列表、元组、字符串
切片：序列[起始:结束:步长]

• 起始可省：从头开始
• 结束可省：到尾结束
• 步长可省：步长为1（负数表示倒序执行）

1.1.2 文件

1、文件编码
编码就是一种规则集合，记录了内容和二进制间相互转换的逻辑，最常用的编码规则是UTF-8
 2、文件操作
步骤：
- 打开文件：open(name,mode,encoding)
        - name:是要打开的目标文件名的字符串（可以包含文件所在的具体路径）
        - mode:设置打开文件的模式（访问模式）：只读、写入、追加等
        - encoding:编码格式（推荐UTF-8)。encoding的顺序不是第三位，所以不能用位置参数，用关键字参数直接指定
f = open('python.txt','r',encoding='utf-8')
注意：f是open函数的文件对象，对象是Python中的一种特殊的数据类型，拥有属性和方法，可以使用对象.属性或对象.方法对其进行访问
- 读写文件：
- 关闭文件：

1.1.3 异常

try:
    可能有异常的代码
except 异常类型 as 别名:
    异常的处理代码
except 异常类型 as 别名:
    异常的处理代码
except 异常类型 as 别名:
    异常的处理代码
...
else:
    没有异常的代码
finally:
    有没有异常都会执行的代码

- try:只有try内部的代码，才会被捕获异常
- except:是匹配机制，用来匹配特定异常
  - 特殊异常类型：Exception所有异常的父类（顶级异常），任何异常都可以用Exception抓住 
- else（可选）：没有异常的时候执行
- finally：无论如何都会执行

1.1.4 包

1.1.5 面向对象

编程思想：人们利用计算机来解决问题的思维。面向对象、面向过程、面向函数式、面向接口。

• 面向过程：一种编程思想，强调以步骤（过程）为基础完成各种操作。
• 面向对象：一种编程思想，强调的是以对象为基础完成各种操作，它是面向过程的，说到面向对象，不得不提的就是它的三大思想特点：
  • 更符合人们的思考习惯
  • 复杂事情简单化
  • 把人们（程序员）转换为执行者。
    一切皆对象。

面向对象三大特性： 封装：把属性和方法封装在一起，仅提供对外的方法让别人去访问，好处：简化编程
继承：子类继承父类的属性和方法，使得子类对象（实例）具有父类的特征和行为。好处：代码复用 多态：不同类的对象对同一消息做出响应。
同样一个函数（消息）在不同的场景下表现出不同的形态。好处：解耦合，可拓展

继承：子类继承父类的属性和方法（子类角度）

• 继承指的是类的继承，而不是对象的继承
• 在Python中，所有类默认继承object类，object类是顶级类或基类，其他子类叫做派生类
• 优点：提高代码的复用性
• 缺点：耦合性增强
• 扩展：开发原则：高内聚，低耦合。
  • 内聚:类自己处理问题的能力
  • 耦合：类与类之间的关系
• 派生：从一个已有的类产生一个新的类（父类角度）
• 父类：基类
• 子类：派生类 扩展类
• 单继承与多继承：
  • 单继承
  • 多继承：一个类同时继承了多个父类，并且同时具有所有父类的属性和方法。
    当一个类有多个父类，默认使用第一个父类的同名属性和方法，可以使用类名.mro属性或类名.mro()方法查看调用的先后顺序
    MRO(Method Resolution Order):方法解析顺序
• 重写：也叫覆盖，当子类属性或方法与父类的属性或方法名字相同时，从父类继承下来的成员可以重新定义。子类重写父类的属性和方法，优先会调用子类的属性和方法（就近原则）
• 子类中调用父类的方法：
  • 父类名.方法名(self)
  • super().方法名() # super是父类的引用，self是子类的引用

封装：将类的属性和方法封装在一起。封装可以为属性和方法添加为私有权限。

1. 私有属性和私有方法：设置某个属性或方法不继承给子类。设置的格式是：在属性或方法名前加“__”（两个下划线）
2. 私有属性和方法使用规则：
3. 只能在类的内部使用，不能在类的外部使用
4. 如果想在类的外部使用，通过公共接口
5. 私有属性不能直接访问，可以定义get_xxx()方法，返回属性值,set_xxx()方法，修改属性值
6. 私有方法不能直接访问，可以在父类内设置一个公共方法进行访问

多态：多种状态，同样一个函数在不同场景下有不同的状态

• 同样的行为（函数）传入不同的对象，得到不同的状态
• 多态的成立条件：
  • 有继承（定义父类、子类，子类继承父类）
  • 函数重写（子类重写父类的函数）
  • 父类引用指向子类对象（子类对象传给父类对象调用者）

类：抽象的模板

• 抽象类：含有抽象方法的类（在Python中也叫做接口），充当父类，制定标准
• 抽象方法：方法体是空实现的pass 对象：具体的实体

类方法：类所拥有的方法，并需要使用装饰器**@classmethod**来标识的其为雷锋，同时注意：是对于类方法的第一个参数必须是类对象，通常以 **cls **作为第一个参数名。

• 使用方式：类名.类方法名 、对象名.类方法名

静态方法：需要通过装饰器**@staticmethod**来标识其为静态方法，且静态方法不需要定义参数（不需要写self）

• 使用方式：类名.静态方法名， 对象名.静态方法名

两者区别：

• 类方法的第1个参数必须是类对象，静态方法无参数的特殊要求

• 你可以理解为：如果函数中要用类对象，就定义成类方法，否则定义成静态方法，除此外，并无任何区别.

魔法方法：在Python中，有些可以给Python增加魔力的特殊方法，总是被双下划线包围，在特殊情况下会被自动调用，不需要开发者手动调用。

_魔法方法名_()

• _init_()：当创建一个对象时，则会自动触发该魔法方法。

  • 无参数情况：不需要外面传递参数，初始化属性值

  • 有参数情况：当需要外面传递参数，初始化属性值

• __dict__：把对象转为字典形式

1.1.6 闭包

闭包：可以保存函数内的变量，而不会随着调用完函数而被销毁。

用来延长函数内变量的声明周期。

• 语法：在函数嵌套的前提下，内部函数使用了外部函数的变量，并且外部函数返回了内部函数，这样使用外部函数变量的内部函数称为闭包

• def 外部函数(外部参数):

  • def 内部函数（内部函数）:

    • ...[使用外部函数的变量]

  • return 内部函数名 # 闭包

• 构成条件：

  • 有嵌套：在函数嵌套（函数里面再定义函数）的前提下

  • 有引用：内部函数使用了外部函数的变量（还包括外部函数的参数）

  • 有返回： 外部函数返回了内部函数名（对象）。

• global:声明全局变量

• nonlocal:声明能够让内部函数去修改外部函数的变量

1.1.7 装饰器和深浅拷贝

装饰器：在不改变原有函数的基础上，给原有函数增加额外功能。本质是一个闭包函数。

• 构成条件：

  • 有嵌套：在函数嵌套（函数里面再定义函数）的前提下

  • 有引用：内部函数使用了外部函数的变量（还包括外部函数的参数）

  • 有返回： 外部函数返回了内部函数名（对象）。

  • 有额外功能：给需要装饰的原有函数增加额外功能。

• 语法：

  • 传统方式：变量名 = 装饰器名（原有函数名）

  • 变量名（）

  • 语法糖：直接在要被装饰的原函数上，直接写 @装饰器名，然后直接调用即可

装饰器的使用：
"""
无参无返回值的函数：
定义：def 函数名():...
调用：函数名()
 
有参无返回值的函数：
定义：def 函数名(形参):...
调用：函数名(实参) 

无参有返回值的函数：
定义：def 函数名():... return 返回值
调用：变量 = 函数名()

有参有返回值的函数：
定义：def 函数名(形参):... return 返回值
调用：变量 = 函数名(实参)
"""
***Tips :装饰器的内部函数格式要和被装饰的原函数保持一致***
***即：***
***原函数是无参无返回的，则装饰器的内部函数也必须是无参无返回的***
***原函数有参又返回的，则装饰器的内部函数也必须时有参又返回的***
多个装饰器装饰一个函数：离函数近最近的装饰器先装饰，然后外面的装饰器
再进行装饰，由内到外的装饰过程。
*多个装饰器装饰1个原函数，按照由内到外的顺序执行，*
*但要用装饰器读写法来做，看到的效果是从上往下执行：*
*# 注意：*
*# - 一个装饰器的参数有且只有一个*
*# - 如果装饰器又多个参数，可以再该装饰器外边再包裹一层，把该装饰器当坐骑内部函数，返回即可。*

执行结果自己分析版本：

深浅拷贝：

• 所谓的深浅拷贝分别指的是：

  • 浅拷贝：copy模块的copy()

  • 深拷贝：copy模块的deepcopy（）函数

• 深拷贝拷贝得多，浅拷贝拷贝得少

• 深浅拷贝主要针对于可变类型，深拷贝拷贝所有层（可变），浅拷贝拷贝第一层（可变）。如果是针对不可变类型，则用法和普通赋值一样，并无区别

• 类型：

  • 可变类型：

  可变对象：可以修改的对象，包括列表、字典、集合该对象所指向的内存中的值可以被改变。变量（准确地说是引用）改变后，实际上是其所指的值直接发生改变，并没有发生复制行为，也没有开辟新的地址，通俗点说就是原地改变。

  • 不可变类型：不可变对象：一旦创建就不可修改的对象，包括字符串、元组、数值类型（整型、浮点型）该对象所指向的内存中的值不能被改变。当改变某个变量时候，由于其所指的值不能被改变，相当于把原来的值复制一份后再改变，这会开辟一个新的地址，变量再指向这个新的地址。

• 浅拷贝：创建新对象，其内容是原对象的引用。浅拷贝之所以称为浅拷贝，是它仅仅拷贝了一层，拷贝了最外围的对象本身，内部的元素只是拷贝了一个引用而已

1.1.8 网络编程

网络：实现资源共享和信息传递的虚拟平台。

• 网络编程：用来实现网络互联的不同计算机上运行的程序间，可以进行数据交互。

  • 三要素：

    • IP地址：设备在网络中的唯一标识。IPV4:4字节，十进制，IPV6：8字节，16进制

    • 端口号：程序在设备上的唯一标识

      端口：知名端口号：众所周知的端口号，范围：0-1023。系统已经使用

      动态端口号：一般程序员开发应用程序使用端口号称为动态端口号， 范围：1024-65535

    • 协议：传输规则，规范。

      • TCP协议：Transmission Control Protocol 传输控制协议，面向连接、可靠的、基于字节流的传输层通信协议。

      • TCP特点：

        • 面向有连接：通信双方必须先建立好连接才能进行数据传输，数据传输完成后，，需要断开连接，，以释放系统资源。

        • 采用字节流传输数据，理论无大小限制

        • 安全（可靠）协议：

          • 都建立了连接，传输数据可靠

          • 必须要先建立连接，相对效率较低

          • 大多数服务器程序都是使用TCP协议开发的，比如文件下载，网页浏览等

        • 效率相对较低

        • 区分客户端和服务器端

• TCP三次握手：建立一个TCP连接，需要客户端和服务器端总共发送3个包以确认连接

  • 第一次握手：客户端向服务器端发送请求，等到服务端确认

  • 第二次握手：服务端收到请求后指导客户端请求建立连接，回复给客户端以确认连接请求。

  • 第三次握手：客户端收到确认后，再次发送请求确认服务端，服务端收到正确请求后，如果正确则连接建立成功，完成三次握手，随后客户端与服务端之间可以开始传输数据

• TCP四次挥手：TCP断开连接的时候需要4次确认，TCP连接是双向的，A连接B、B连接A都要断开

  • 第一次挥手：当主机A（可以是客户端也可以是服务端）完成数据传输后，提出停止TCP连接的请求

  • 第二次挥手：主机B收到请求后对其作出响应，确认这一方向上的TCP连接将关闭

  • 第三次挥手：主机B端再提出反方向的连接关闭请求

  • 第四次挥手：主机A对主机B的请求进行确认，双方向的关闭结束

1.1.8.1 socket套接字

socket(简称 套接字)是进程之间通信一个工具，好比现实生活中的插座，所有的家用电器要想工作都是基于插座进行，而进程之间想要进行网络通信需要基于这个socket。

socket(AddressFamily,Type)

用于创建一个socket对象，其中AddressFamily可以选择A_INET用于Internet进程间通信，type表示套接字类型，可以是SOCK_STREAM流式套接字，主要用于TCP协议

1.1.8.2 TCP开发流程

TCP网络应用程序开发分为：

• TCP客户端程序开发（ps:浏览器）

• TCP服务端程序开发

说明：

客户端程序是指运行在用户设备上的程序

服务端程序是指运行在服务器设备上的程序，专门为客户端提供数据服务。

TCP服务器端操作步骤流程说明：

1.创建服务端套接字对象

2.绑定端口号

3.设置监听

4.等待接受客户端的连接请求

5.发送数据

6.接收数据

7.关闭套接字

connect(address)

主动初始化TCP服务器连接，一般参数address格式为元组（host,port），若连接出错，

TCP客户端操作步骤：

1. 创建客户端套接字

2. 客户端连接服务器端

3. 接收数据

4. 发送数据

5. 关闭套接字

当有了socket对象后，常用于客户端函数如下：

connet(address):主动初始化TCP服务器连接，一般地，参数address的格式为元组（host，port），若连接出错，则返回socket.error错误。

字符串转二进制数据bytes:

• 字符串转二进制：encode(encoding) ,encode表示编码格式，常为UTF-8

• 二进制转字符串：decode(encoding)

• 二进制的特殊写法：b’字母 数字 特殊符号’，不可以有中文

当客户端和服务器端建立连接后，服务器程序退出后端口号不会立即释放，需要等待大概1-2分钟。

解决方法：

• 更换服务器端端口号

• 设置端口号复用：服务端退出程序后立即释放端口号

  • tcp_server_socket.setsockopt(socket.SOL_SOCKET,socket.SO_REUSEADDR,True)

    • 参数1：当前套接字

    • 参数2：设置端口号复用

    • 参数3：设置端口号复用选项对应的值

总结：TCP网络程序的注意点

1. **TCP服务端必须绑定端口号，**否则客户端找不到这个TCP服务器程序，为了稳定，建议把IP也绑定

2. accetp()前的套接字是被动套接字，只负责接收新的客户端连接请求，不能收发消息。

3. 当TCP客户端程序和TCP服务端程序连接成功后，TCP服务器程序会产生一个新的套接字，用于收发客户端消息。

4. 若关闭accept()返回的被动连接套接字，则表示和这个客户端已经通信完毕。

5. 对于服务端socket,关闭时需慎重

6. 当客户端的套接字调用close后，服务器端的recv会解阻塞，返回的数据长度为0，用于判断客户端是否已经下线

1.1.8.3 进程

多任务:同一时间内执行多个任务。

• 表现形式：

  • 并发：在一段时间内，交替执行任务。（单核CPU是并发执行多任务）

  • 并行：在一段时间内，真正的同时一起执行多个任务（多核CPU是并行的执行多任务，始终有多个任务一起执行）

多个任务同时执行能够充分利用CPU资源，大大提高程序执行效率。

进程：Process，是CPU资源分配的最小单位，它是操作系统进行资源分配和调度运行的基本单位。一个正在运行的程序就是一个进程。

一个程序运行，至少有一个进程。

• 进程的创建步骤：

  • 导入进程工具包：import multiprocessing

  • 通过进程类实例化对象：子进程对象 = multiprocessing.Process(group=None,target=None,name=None,args=(),kwargs={})

    • group:参数未使用，值始终为None

    • target:表示调用对象，即子进程要执行的任务（回调函数入口地址）

    • args:表示元组的形式向子任务函数传参，元组方式传参一定要和参数的顺序保持一致

    • kwargs:表示以字典的方式给子任务函数传参，字典方式传参字典中的key要和参数名保持一致

    • name:为子进程的名称

  • 启动进程执行任务：进程对象.start()

• 进程编号：

  • 进程编号唯一标识一个进程，方便管理进程。在一个操作系统中，一个进程拥有的进程号是唯一的，进程号可以复用。

  • 目的：验证主进程和子进程的关系，可以得知子进程是由哪个主进程创建出来的

  • 获取进程编号的两种操作

    • 获取当前进程编号：os.getpid()

    • 获取当前父进程编号：os.getppid()

    • main中创建的进程，如果没有特殊指定，它的父进程都是main进程，而main进程的父进程是PyCharm程序的pid

• 注意事项：

  • 进程直接拿不共享全局变量

  • 主进程会等待所有的子进程执行结束再结束

    • 不让主进程等待子进程：

      • 子进程设置守候进程：目的是主进程退出子进程销毁，不让主进程再等待子进程去执行

      • 子进程自己主动终止子进程

写法	作用	主进程结束时
join()	主进程 等 子进程	子进程跑完才结束
daemon=True	守护进程	主进程一结束，子进程直接被杀
terminate()	手动强制杀死	立刻杀死，不等

origin_url=%E5%9B%BE%E7%89%87%E5%92%8C%E9%99%84%E4%BB%B6%2Fimage%252024.png&pos_id=img-l4uVFGkm-1785467454456)

1.1.8.4 线程

线程和进程的关系：

• 进程是分配资源的基本单位，一旦创建一个进程就会分配一定的资源。

• 线程是**CPU调度的基本单位，**每个进程至少都有一个线程，而这个线程就是主线程。

• 进程间的数据相互隔离，（同一个进程）线程间数据可以共享

目的：实现多任务编程。

创建线程步骤：

• 导入线程模块：import threading

• 通过线程类创建线程对象：线程对象 = threading.Thread(target = 任务名)

  • 线程对象 = threading.Thread([group[,target[,name[,args[,kwargs]]]]])

    • group:线程组，目前只能使用None

    • target：执行的目标任务名

    • args:以元组的方式给执行任务传参，元组方式传参一定要和目标任务函数的顺序保持一致

    • kwargs:以字典方式给执行任务传参，字典方式传参字典中的key一定要和参数的顺序保持一致

    • name：线程名，一般不用设置

• 启动线程执行任务：线程对象.start()

• 注意点：

  • 线程之间执行是无序的

  • 主线程会等待所有的子线程执行结束再结束

  • 线程之间共享全局变量

  • 线程之间共享全局变量数据出现错误问题（互斥锁）

    • 互斥锁：对共享数据进行锁定，保证同一时刻只有一个线程去操作。

    • 互斥锁是多个线程一起抢，抢到锁的线程先执行，没有抢到锁的线程进行等待，等锁使用完释放后，其他等待的线程再去抢这个锁。

    • 互斥锁的使用：

      • 创建：mutex = threading.Lock()

      • 上锁：mutex.acquire()

      • 释放锁：mutex.release()

进程和线程：

• 线程依赖进程，进程是CPU分配资源的基本单位，线程是CPU调度资源的基本单位

• 进行更消耗资源，不能共享全局变量，相对更稳定

• 线程更轻量级，可以共享全局变量，相对更灵活

1. 关系对比：

   1. 线程是依附进程里的，没有进程就没有线程

   2. 一个进程默认提供一条线程，进程可以创建多个线程

2. 区别对比：

   1. 进程之间不共享全局变量

   2. 线程之间共享全局变量，但是要注意资源竞争的问题，解决方式：互斥锁

   3. 创建进程的资源开销要比创建线程的资源开销要大

   4. 进程是操作系统资源分配的 基本单位，线程是CPU调度的基本单位

   5. 线程不能独立执行，必须依附在进程中

   6. Python中多进程开发要比单进程多线程开发稳定性要强

3. 优缺点对比：

   1. 进程：

      1. 优点；可以用多核

      2. 缺点：资源开销大

   2. 线程：

      1. 优点：资源开销小

      2. 缺点：不能使用多核

1.2 正则表达式

1.2.1 迭代器、生成器

迭代器：Iterator,用于在数据集合中逐个访问元素，而不需要暴露数据集合的底层实现。

• 特点：

  • 手动管理：需要显式实现`__iter__()、__next__()`方法

  • 状态管理：迭代器需要自己管理迭代的状态，包括当前位置和结束条件

  • 内存使用：内存使用取决于迭代器的实现，通常是惰性计算（按需生成数据）

生成器：程序员制定的规则，循环生成数据。需要一个，就生成一个。节约内存

• 创建生成器的方式：

  • 生成器推导式

  • yield关键字

property属性：把一个方法当做属性进行使用，简化代码

定义property属性的两种方法：

• 装饰器方式：

  • @property 修饰获取值的方法

  • @方法名.setter 修饰设置值的方法

• 类属性方式：

  • property属性 = property（获取值方法名，设置值方法名）

代码	功能
.	匹配任意1个字符，除 \n
[]	匹配[]中列举的字符
[^指定字符]	匹配处理指定字符以外的所有字符
\d	匹配数字，即0-9
\D	匹配非数字，即不是数字
\s	匹配空白，即空格，tab健	[\t\n\r]
\S	匹配非空白
\w	匹配非特殊字符，即a-z,A-Z,_,汉字	[a-ZA-Z0-9-汉字]
\W	匹配特殊字符，即非字母，非数字，非汉字
r’\d’ == ‘\\d’	取消\的特殊含义，或者
*	匹配前一个字符出现0次或无数字，即可有可无
+	匹配前一个字符出现1次或无数次，即至少有一次
？	匹配前一个字符出现1次或0次，即要么有1次，要么没有
{m}	匹配前一个字符出现m次
{m,}	匹配前一个字符至少出现n次，至多无数次
{m,n}	匹配前一个字符出现从m到n次，[m,n]
^	匹配开头
$	匹配字符串结尾
|	匹配左右任意一个表达式
(ab)	将括号中字符作为一个分组
\num	引用分组num匹配到的字符串

正则表达式大全.docx

图像识别学习计划.xlsx

1.3 数据结构与算法

1、数据结构与算法简介

1.1简介

数据结构：存储和组织数据的方式

算法：为了实现业务目的的各种方法和思路

数据结构与算法的作用：大大提升程序的性能、面试高频考点

1.2 算法特性

1. 独立性：算法是独立存在的一种解决问题的方法和思想，不依附编程语言存在。

2. 算法五大特性：

   1. 有输入：算法具有0个或多个输入

   2. 有输出：至少有1个或多个输出

   3. 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每个步骤可以在可接受的时间内完成

   4. 确定性：算法中每一步都有确定的含义，不会出现二义性

   5. 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限次数完成

1.3 算法的时间效率衡量

**实现效率:**代码执行总时间（T）= 操作步骤数量 * 操作步骤执行时间

T = （大整体*子整体*基本操作）*操作步骤执行时间

假设计算机执行算法每一个基本操作的时间是固定的一个时间单位，T= 操作步骤总数（基本操作*子整体*大整体）

1.4 时间复杂度

主要条件：随着问题规模变化而变化的

次要条件：随着问题规模变化而不变的

for a in range(0,1001):
    for b in range(0,1001):
        c = 1000 - a - b
        *# for c in range(0,1001):*
*        *if a + b + c == 1000 and a**2 + b**2 == c**2:
            print(f'a={a},b={b},c={c}')

时间复杂度：：表示一个算法**随着问题规模不断变化的最主要趋势，**通常是用来衡量一个算法的优劣。通俗点来说时间复杂度可以衡量一个“算法的量级”

将次要关系都省略掉，最终形成一个表达式，这种方式称为：大O记法

1.5 时间复杂度的计算

• 计算规则：

  • 基本操作：O（1）

  • 顺序结构：加法计算

  • 循环结构：乘法计算

  • 分支结构：取最大值

  • 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它要项和常数项可以忽略

  • 在没有特殊说明时，我们所分析的算法的时间复杂度都是最坏时间复杂度

时间复杂度与问题规模无关，执行次数恒定的算法，我们称之为具有O（1）的时间复杂度

1.6 最优最坏时间复杂度

考虑：

• 最优时间复杂度：算法完成工作最少需要多少基本基本操作

• 最坏时间复杂度：算法完成工作最多需要多少基本操作

• 平均时间复杂度：算法完成工作平均需要多少基本操作

通常我们都是用最坏时间复杂度。

1.7常见时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)

时间复杂度越低，效率越高

备注：

O(nlogn):大O记法：时间T与问题的规模变化曲线：二分法

O（nlogn）:一个for循环是n另外一个for循环的二分法，组合在一起

1.8空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量

类似于时间复杂度，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，也使用大O记法。

和时间复杂度类似，空间复杂度一般常见的有：

O(1) < O(logn) < O(n) < O(n²) < O(n³)

常数阶0(1):普通常量、变量、对象、元素数量与输入数据大小Ｎ无关的集合，皆使用常数大小的空间。

线性阶0(n):元素数量与Ｎ呈线性关系的任意类型集合（常见于一维数组、链表等），均使用线性大小的空间。

平方阶O(n²):元素数量与N呈平方关系的任意类型集合（常见于矩阵），均使用平方大小的空间。

2、数据结构

2.1 概念

数据结构只是静态的描述了数据元素之间的关系，是存储和组织数据的方式。高效的程序需要在数据结构的基础上设计和选择算法

算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体

最常用的数据运算有：插入、删除、修改、查找、排序

程序=数据结构+算法

2.2 内存的存储结构

**内存以字节为基本存储单位，**每个基本存储空间都有自己的地址（一个内存地址代表一个字节8bit的存储空间），其中整型4个字节，字符char:1个字符，

1.2 数据结构的分类

分类：

• 线性结构：数据结构中各个结点具有线性关系

  • 特点：非空集，所有节点最多只有一个直接前去结点和一个直接后继结点

  • 顺序表：

    • 一站式存储：数据区、信息区，eg:栈、队列

    • 分离式存储

  • 链表：自定义代码模拟 链表

• 非线性结构：数据结构中各个结点之间具有多个对应关系

  • 特点：非空集、一个结点可能有多个直接前驱结点和多个直接后继结点

  • 树结构、图结构

2.4 顺序表存储方式

①顺序表：将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示

②链表：将元素存放在通过链接构造起来的一系列存储块中，存储区是非连续的

无论一体式结构还是分离式结构，顺序表在获取数据的时候直接通过下标偏移就可以找到数据所在空间的地址，而无需遍历后才可以获取地址·所以顺序表在获取地址操作时的时间复杂度**：O(1)**

2.5 顺序表的实现和扩充

顺序表完整信息：数据区、信息区：元素存储区的容量和当前表中已有的元素个数

扩充：

• 每次扩充**增加固定数目的存储位置，**如每次扩充增加10个元素位置，这种策略可称为线性增长

  • 特点：节省空间，但是扩充操作频繁，操作次数多。

• 每次扩充容量加倍，如每次扩充增加一倍存储空间。

  • 特点：减少了扩充操作的执行次数，但可能会浪费空间资源，以空间换时间，推荐的方式

元素存储区的替换：

一体式存储的顺序表存储在连续的空间，则只能整体搬迁，即信息区和数据区都改变

分离式存储的顺序表可只整体更換数据区，信息区的链接更新即可

2.6 顺序表增加与删除元素

增加：

• 尾端加入元素，时间复杂度为O(1)

• 非保序的加入元素（不常见），时间复杂度为O(1)

• 保序的元素加入，时间复杂度为O(n)

删除元素：

• 删除表尾元素，时间复杂度为O(1)

• 非保序的元素删除（不常见），时间复杂度为O(1)

• 保序的元素删除，时间复杂度为O(n)

3、链表

3.1 链表

顺序表：查找修改快，增删慢

链表：增删快，查找慢

不需要连续的存储空间

存储:[10，20，30，40]

每个结点有2部分：元素域，下一个结点的内存地址（链接域）；最后一个结点链接域为None
链表结构：

1、单链表(单向链表)是链表的一种形式，每个结点包含两个域：元素域和链接域.

这个链接指向链表中的下一个结点，而最后一个结点的链接域则指向一个空值None

①表元素域item用来存放具体的数据
②链接域next用来存放下一个结点的位置
③变量head指向链表的头结点(首结点)的位置，从head出发能找到表中的任意结点

2、单向循环链表：
3、双向链表
4、双向循环链表

结点代码实现：

从面向对象的角度思考链表，应该有2个对象：结点对象SingleNode,链表对象SingLinkList

如果node是一个结点，获取结点元素：node.item,获取下一个结点：node.next

操作	链表	顺序表
访问元素	O(n)	O(1)
在头部插入/删除	O(1)	O(n)
在尾部插入/删除	O(n)	O(1)
在中间插入/删除	O(n)	O(n)

"""
案例：自定义代码模拟链表
概述：
它属于数据结构之 线性结构的一种，每个节点都只能有1个前驱 和1个后继节点，
作用：
用于优化顺序表的弊端（如果没有足够的连续的内存空间，会导致扩容失败）链表扩容时，有地儿就行，连不连续无所谓。
组成：
由节点组成，其中节点由元素域（数值域）和链接域(地址域)组成。分类:
根据节点类型不同，链表主要分为：单向链表：
单向循环链表
双向链表
双向循环链表

自定义代码模拟链表，思路分析：
1.自定义SingleNode类，表示结点类
    属性：
        item: 数值域（元素域）
        next:地址域（链接域）
2.自定义SingleLinkList类，表示链表
    属性：
        head 表示头结点
    行为:
    isEmpty(self)           判断链表是否为空
    length(self)            获取链表长度
    travel(self)            遍历链表
    add(self,item)          链表头部添加元素
    append(self,item)       链表尾部添加元素
    insert(self,pos,item)   链表指定位置添加元素
    remove(self,item)       删除节点
    research(self,item)     查找节点是否存在

"""
from hmac import new


# 结点 类
class SingleNode:
    def __init__(self,item):
        self.item = item
        self.next = None

# 链表类
class SingleLinkList:
    def __init__(self,node=None):
        self.head = node

    # 判断链表是否为空
    def isEmpty(self):
        # if self.head is None:
        #     return True
        # else:
        #     return False
        return self.head is None

    # 获取链表长度
    def length(self):
    #     创建游标（当前节点）默认从头结点开始
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    # 遍历链表
    def travel(self):
        # 定义当前游标
        cur = self.head
        while cur is not None:
            print(cur.item,end=' ')
            cur = cur.next

    # 链表头部添加元素
    def add(self,item):
        new_node = SingleNode(item)
        new_node.next = self.head
        self.head = new_node

    # 链表尾部添加元素
    def append(self, item):
        new_node = SingleNode(item)
        if self.isEmpty():
            self.head == new_node
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = new_node


    # 链表指定位置添加元素
    def insert(self,pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > self.length():
            self.append(item)
        else:
            cur = self.head
            count = 0

            while count < pos - 1:
                count += 1
                cur = cur.next
            new_node = SingleNode(item)
            new_node.next = cur.next
            cur.next = new_node

    # 删除节点
    def remove(self,item):
        cur_node = self.head # 游标
        pre_node = cur_node # 游标前一个节点
        while cur_node is not  None:
            if cur_node.item == item:
                if cur_node == self.head:
                    self.head = cur_node.next
                else:
                    pre_node.next = cur_node.next
                    cur_node.next = None
                    return
            # 如果没有找到要删除的元素
            else:
                pre_node = cur_node
                cur_node = cur_node.next

    # 查找节点是否存在
    def research(self,item):
        cur_node = self.head
        while cur_node is not None:
            if cur_node.item == item:
                return True
            else:
                cur_node = cur_node.next
        return False

if __name__ == '__main__':
    node1 = SingleNode(10)
    # print(f'元素域：{node1.item}')
    # print(f'地址域：{node1.next}')
    # print(f'node1的类型：{type(node1)}')
    # print(f'node1对象：{node1}')
    #
    # #链表
    # my_linkeList = SingleLinkList(node1)
    # print(f'头结点：{my_linkeList.head}')
    # print(f'头结点元素域:{my_linkeList.head.item}')
    # print(f'头结点地址域:{my_linkeList.head.next}')

    #完整测试
    node2 = SingleNode('1')
    my_linkedList = SingleLinkList(node2)
    print(f'头结点：{my_linkedList.head}')
    print(f'头结点元素域:{my_linkedList.head.item}')
    print(f'头结点地址域:{my_linkedList.head.next}')
    print('*'*30)

    print(f'链表是否为空：{my_linkedList.isEmpty()}')
    node3 = SingleNode('2')
    my_linkedList = SingleLinkList(node3)
    print('*'*30)
    print(f'链表长度：{my_linkedList.length()}')
    print('*'*30)
    my_linkedList.travel()
    print('******************头部添加add**************')
    my_linkedList.add('3')
    my_linkedList.add('4')
    my_linkedList.travel()

    print('******************尾部添加append**************')
    my_linkedList.travel()

    print('\n******************指定位置添加insert**************')
    my_linkedList.insert(2,'5')
    my_linkedList.travel()

    print('\n******************删除remove**************')
    print('删除前')
    my_linkedList.travel()
    print()
    my_linkedList.remove('4')
    print('删除后')
    my_linkedList.travel()

    print('\n******************查找research**************')
    print(f'查找元素是否存在：{my_linkedList.research("5")}')

4、算法的稳定性

算法稳定性：具有相同关键字的记录经过排序后，相对位置保持不变。“相同元素的相对位置是否发生改变”

不稳定算法：选择排序、快速排序、希尔排序、堆排序

稳定排序算法：冒泡排序、插入排序、归并排序、基数排序

4.1 冒泡排序

记忆:相邻两个元素比较，前面的元素比后面的元素大则交换，把最大的数找到，经过一轮一轮的比较最终把序列给排序。

要素：

1. 要比较的总轮数：列表长度 -1

2. 每轮比较的总次数：列表长度 - 1 - 轮数（索引，从0开始）

3. 谁和谁比较

注意: 交换：a,b = b,a (等价于c=a,a=b,b=c)

• 时间复杂度：

  • 最优：O(n)，

    • 优化，记录内每轮交换次数，若该轮交换次数为0，则不用进行后续比较

  • 最坏：O(n²)

• 冒泡：稳定排序

• 扩展：

  • 外循环的 -1 是什么意思：减少比较的轮数

  • 内循环的 -1 是什么意思：防止索引越界

  • 内循环的 -i 是什么意思：减少每轮比较的次数

def bubble_sort(myList):
    sum = 0
    for i in range(len(myList) - 1):
        count = 0 *# 记录是否交换了数据,如果第一轮没有交换数据，则后面将不再进行排序*
*        *for j in range(len(myList) - 1 - i):
            if myList[j] > myList[j + 1]:
                count += 1
                myList[j],myList[j + 1] = myList[j + 1],myList[j]
                print(f'第{i}-{j}轮排序，，myList:{myList}')
        print(f'第{i}轮排序结束，交换了{count}次')
        if count == 0:
            break
    print(f'总共交换了{sum}次')
if __name__ == '__main__':
    myList = [5,4,3,2,1]
    print('排序前',myList)
    bubble_sort(myList)
    print('排序后',myList)

4.2 选择排序

选择排序：待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置

• 要点：

  • 比较的总轮数：n-1

  • 每轮比较的总次数：range(i+1,n)

  • 谁和谁比较: i 和 min_index

• 时间复杂度：

  • 最优：O（n²）

  • 最坏：O（n²）

• 选择排序：不稳定排序

• 扩展：

  • 外循环的 -1 是什么意思：减少比较的轮数

def select_sort(myList):
    for i in range(len(myList)-1):
        min_index = i
        for j in range(i+1,len(myList)):
            if myList[min_index] > myList[j]:
                myList[min_index],myList[j] = myList[j],myList[min_index]
        if min_index != i:
            myList[i], myList[min_index] = myList[min_index], myList[i]
if __name__ == '__main__':
    myList = [5,4,3,2,1]
    select_sort(myList)
    print(myList)

4.3 插入排序

插入排序：将一个数据插入到已经排好序的有序数据中

• 原理：把列表分成两部分，假设第一个元素是有序的，剩下的元素都是无序的，每次都从无序列表中获取1个元素，和Ta前面的所有元素比较，决定它的位置，进行插入
  直至无序列表的元素操作完毕，剩下的列表就是有序的

• 要点：

  • 比较的总轮数：n-1 range(1,n)

  • 每轮比较的总次数：range(i，0，-1)

  • 谁和谁比较:j 和 j-1

• 时间复杂度：

  • 最优:O(n）

  • 最坏:O(n²）

• 插入排序：稳定排序，适用于少量数据的排序

def insert_sort(myList):
    n = len(myList)
    for i in range(1,n):
        count = 0
        for j in range(i,0,-1):
            if myList[j-1] > myList[j]:
                myList[j-1],myList[j] = myList[j],myList[j-1]
                count += 1
            else:
                 break
        print(f'第{i}轮排序，，myList:{myList},比较次数：{count},')

if __name__ == '__main__':
    myList = [5,4,3,2,1]
    print(myList)
    insert_sort(myList)
    print(myList)

4.4 快速排序

基本思想:基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

排序流程：

• 首先设定一个分界值，通过该分界值江数组分层左右两部分

• 就那个大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边，此时，左边部分中各元素都小于或等于分界值，右边部分中各元素都大于或等分界值

• 然后左边和有变动数据可以独立排序，对于左侧树数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值，右侧同上

• 重复后，可以看出这是一个递归定义。

要点：

• 层数带边排序的轮数：n-1

• 每一轮比较n-1次

• 最差时间复杂度:$O(n^2)$

• 最优时间复杂度：$O(nlogn)$

• 不稳定算法

"""
大白话解释：
第1轮：1个分界值，假设第1个元素为分界值，次数：比该值小的的都放左边，比该值大于或者等于放右边。小  分界 大
第2轮：2个分界值，上一轮分界值左边数据找个分界值。上一轮分界值右边数据 找个分界值
第3轮：4个分界值..．以此类推。
"""
def quickSort(myList,start,end):
    """
    快速排序实现对列表元素排序
    :param myList:要操作的列表
    :param start:起始索引
    :param end:结束索引
    :return:
    """
    mid = myList[start] # 分界值:列表的起始值
    left = start # 分界值左
    right = end # 分界值右
    # 具体查找过程：只要left比right小，就一直找
    while left < right:
        # 核心细节：出口：如果start >= end 结束排序
        if start >= end:
            return
        # 把分界值右边比分界值小的数据，放分界值左边
        #循环操作：只要分界值右边的数据比分界值大，right就-1，直至循环结束
        while myList[right] >= mid and left < right:
            right -= 1
        # 此步骤：说明myList[right]比分界值小，放左侧
        myList[left] = myList[right]
        # 把分界值左边比分界值大的数据，放分界值右边
        while myList[left] < mid and left < right:
            left += 1
        myList[right] = myList[left]

        # 循环结束，即：分界值的位置已经找到，赋值即可
        myList[left] = mid
        print(f'排序过程：start:{start},end:{end},myList:{myList}')

        # 递归方式，处理分界值左侧的数据
        quickSort(myList,start,left-1)
        quickSort(myList,right+1,end)

if __name__ == '__main__':
    myList = [1,5,2,6,3,8,4,9]
    print(f'排序前：{myList}')
    quickSort(myList,0,len(myList)-1)
    print(f'排序后：{myList}')

数据结构

5、查找

5.1 二分查找

二分查找又称折半查找，它是一种效率较高的查找方法。

**原理：**将数组分为三部分，依次是中值前，中值，中值后

将要查找的值与中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回

"""
案例：演示二分查找，递归版。
二分查找：
概述:
属于查找类算法，相对效率比较高，时间复杂度为：0(logn)
前提:
列表必须是有序的。原理：假设列表是升序的
1．比较要查找的元素和列表的中值，如果一样就返回True，程序结束。
2.如果要查找的元素比中值小，去前半段（中值前）查找。
3.如果要查找的元素比中值大，去后半段（中值后）查找。
"""
def binary_search_recursion(myList,target):
    """
    该函数是二分查找递归版，实现查找指定元素是否在列表中，
    :param myList:待查找的列表
    :param target:要查找的元素
    :return:True：在，False：不再
    """
    n = len(myList)
    mid = n // 2 # 中值索引 //是整数除法，默认为整数
    if n <= 0:
        return False
    if target == myList[mid]:
        return True
    elif target < myList[mid]:
        return binary_search_recursion(myList[:mid],target)
    else:
        return binary_search_recursion(myList[mid+1:],target)
    return False # 走到这里，说明列表都遍历完了，还没找到，返回False
if __name__ == '__main__':
    myList = [1,2,3,4,5,6,7,8,9,10]
    element = 110
    print(binary_search_recursion(myList,element))

"""
步骤：
1、设置初始化搜索空间，起始位置start和结束为止end
2、循环检索：
    2.1 获取中间值索引 mid = (start+end)//2
    2.2 item等于中间值，返回True
    2.3 item小于中间值，在前半部空间搜索，修改搜索空间end=mid-1
    2.4 item大于中间值 在后半部空间搜索，修改搜索空间start=mid+1
"""
def binart_search_nonrecursion(myList,target):
    """
    该函数是二分查找非递归版，实现查找指定元素是否在列表中，
    :param myList:待查找的列表
    :param target:要查找的元素
    :return:True：在，False：不再
    """
    n = len(myList)
    start = 0
    end = n-1
    mid = (start+end)//2
    while start <= end:
        if myList[mid] == target:
            return True
        elif myList[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
        mid = (start+end)//2
    return  False
if __name__ == '__main__':
    myList = [1,2,3,4,5,6,7,8,9,10]
    element = 101
    print(binart_search_nonrecursion(myList,element))

1.4 树🌲

1、树的概念

树：非线性结构

特点：

• 每个节点有0个或多个子节点

• 没有父节点的节点称为根节点

• 每一个非根节点有且只有一个父节点

• 除根节点外，每个子节点可以分为多个不相交的子树

• 没有子节点的节点称为叶子结点

2、树的种类及存储

种类：

• 无序树：数中任意节点的子节点之间没有顺序关系，“自由树”

• 有序树：树中任意节点的子节点之间有顺序关系

  • 霍夫曼树（用于信息编码）：带权路径最短的二叉树称哈夫曼树或最优二叉树

  • B树：一种归对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于的两个子树

• 二叉树：每个节点最多含有两个子树的树

• 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树

• 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树

  • 主要是为了防止树退化为链表

二叉树的种类：

• 排序二叉树（二叉查找树：Binary Search Tree）也称为二叉搜索树、有序二叉树

  • BST要求：

    • 若左子树不空，则左子树上所有节点的值均小于它的根节点的值

    • 若右子树不空，则右子树所有节点的值均大于它根节点的值

    • 左右子树也分别为二叉排序树（BST）

  • 一般称为二叉排序树，中序遍历二叉排序树，会得到一个有序的序列

• 二叉树种类中，各个树的作用：

  • 满二叉树：层次存储的时候，从左到右控制节点产生

  • 平衡二叉树：防止树变成链表

  • 排序二叉树：对数据排序，检索起来速度快

二叉树的存储：

• 顺序存储：将二叉树存储在固定的数组中，需要存储树节点数据和树节点关系，占空间

• 链式存储：由于对节点的个数无法掌握，常见树的存储表示都转换为二叉树进行处理，子节点个数最多为2。容易找到子节点、父节点关系。每个节点有两个指针域

• 二叉树：每个节点最多含有两个子树的树

3、树的应用场景_数据库索引
目录结构

4、二叉树的概念和性质

概念：每个节点最多有两个子树的树结构，左子树和右子树

性质：（k,i大于0）

• 在二叉树的第i层上至多有$2^i-1$个结点

• 深度为k的二叉树至多有$2^k-1$个节点

• 对于任意一棵二叉树，如果其叶子结点数为$N_0$,而度数为2的结点总数为$N_2$,则$N_0=N_2+1$

• 最多有n个结点的完全二叉树的深度必为$lo{g}_2(n+1)$

• 对于完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子，编号必为2i,其右孩子编号必为2i+1.其父节点编号必为$i//2$（i=1为根时除外）

5、二叉树的广度优先遍历-深度优先遍历（前中后序遍历）

深度优先可以先找到搜索路径-深度遍历

广度优先可以找到最短路径-层次遍历

"""
树结构解释：
概述:
它属于数据结构的一种，属于非线性结构(N个前驱，N个后继)特点：
1.有且只能有1个根节点。
2.每个节点都可以有1个父节点及任意个子节点，根节点除外(没有父节点）。
3.没有子节点的节点，称之为：叶子节点。
常用分类：
无序树：
有序树:
完全二叉树：最后一层不满，其它都是满的。满二叉树：都是满的。
非完全二叉树：中间有断的。
平衡二叉树：任意节点的两个子树的高度差不超过1
我们用的最多的就是：二叉树
存储：
顺序存储：既要存储数据，又要存储节点的关系。
链式存储：采用节点（item，Lchild，rchild）的方式，形成链表来存储
抽取方法的快捷键：CTRL+ALT+M
"""
# 1、结点类
class Node(object):
    def __init__(self,item):
        self.item = item
        self.lchild = None
        self.rchild = None

# 2、二叉树类
class BinaryTree(object):
    # 根节点
    def __init__(self,node = None):
        self.root = node

    # 二叉树广度-添加功能
    def add(self,item):
        """
        初始操作：初始化队列、将根节点入队、准备加入到二叉树的新节点
        重复执行：获得并弹出队头元素
            - 若当前节点的左右子节点不为空，则将其左右节点入队列
            - 若当前节点的左右节点为空，则将新节点挂到为空的左子节点、或者右子节点
        :param item: 添加节点的元素域
        :return:
        """
        # 封装节点
        newNode = Node(item)
        #判断根节点是否为空
        if self.root is None:
            self.root = newNode
            return
        #创建队，添加根节点到队列中
        queue = []
        queue.append(self.root)
        #通过while循环找到空缺的节点位置
        while True:
            #获取队列的第一个元素
            node = queue.pop(0)
            #如果左子树为空，则添加至该左子树，并结束
            if node.lchild is None:
                node.lchild = newNode
                return
            else:
                queue.append(node.lchild)
            #如果右子树为空，则添加至该右子树，并结束
            if node.rchild is None:
                node.rchild = newNode
                return
            else:
                queue.append(node.rchild)

    # 二叉树广度优先遍历
    def breadth_travel(self):
        #判断根节点是否为空
        if self.root is None:
            print('该二叉树为空！')
            return
        #创建队列，添加根节点
        queue = []
        queue.append(self.root)
        while len(queue) != 0:
            node = queue.pop(0)
            print(node.item,end=' ')
            # 判断左子树
            if node.lchild is not None:
                queue.append(node.lchild)
            #判断右子树
            if node.rchild is not None:
                queue.append(node.rchild)

    # 二叉树深度前序遍历
    def preTravel(self,root):
        if root is not None:
            print(root.item,end='\t')
            self.preTravel(root.lchild)
            self.preTravel(root.rchild)

    # 二叉树深度中序遍历
    def midTravel(self,root):
        if root is not None:
            self.midTravel(root.lchild)
            print(root.item, end='\t')
            self.midTravel(root.rchild)

    # 二叉树深度后序遍历
    def behindTravel(self,root):
        if root is not None:
            self.behindTravel(root.lchild)
            self.behindTravel(root.rchild)
            print(root.item, end='\t')

# 3、测试函数
def testNode():
    node1 = Node('A') # 结点
    print(node1.item)
    print(node1.lchild)
    print(node1.rchild)

    bt = BinaryTree(node1)# 二叉树
    print(f'bt:{bt},\troot:{bt.root},\troot元素域：{bt.root.item}')

# 测试：队列
def testQueue():
    global queue
    # 创建队列：先进先出
    queue = []
    queue.append('A')
    queue.append('B')
    queue.append('C')
    # print(queue.remove('A')) # 根据元素删除
    print(queue.pop(0))# pop根据索引删除，并返回该元素，即模拟队列中获取元素
    print(queue.pop(0))
    print(queue)

#测试：广度优先 
def testBreeth():
    # 1、创建二叉树
    bt = BinaryTree()
    # 2、添加元素
    bt.add('A')
    bt.add('B')
    bt.add('I')
    bt.add('D')
    bt.add('E')
    bt.add('F')
    # 3、广度优先遍历
    print('广度优先遍历：')
    bt.breadth_travel()
    print('深度优先遍历：前序')
    bt.preTravel()

# 测试：深度优先遍历
def testDeep():
    bt = BinaryTree()
    bt.add(0)
    bt.add(1)
    bt.add(2)
    bt.add(3)
    bt.add(4)
    bt.add(5)
    bt.add(6)
    bt.add(7)
    bt.add(8)
    bt.add(9)
    print('广度遍历：', end=' ')
    bt.breadth_travel()
    print()
    print('先序：', end=' ')
    bt.preTravel(bt.root)
    print()
    print('中序：', end=' ')
    bt.midTravel(bt.root)
    print()
    print('后序:', end='  ')
    bt.behindTravel(bt.root)

# 4、主函数
if __name__ == '__main__':
    # testNode()

    # testQueue()

    # testBreeth()

    testDeep()

6、二叉树由遍历结果反推二叉树的结构

反推：必须有中序，+先序/后续