0x01 线性数据结构
线性数据结构是计算机组织数据的一种方式
- 线性结构是一个数据元素集合
- 有一个唯一的首元素
- 有一个唯一的尾元素
- 除了首元素和尾元素，所有的元素都有一个唯一的先驱
- 除了首元素和尾元素，所有的元素都有一个唯一的后继
常见的线性数据结构有：数组、栈、队列、链表等
数组
Python语言没有提供数组数据类型，通常使用列表作为数组。
栈
- 栈(
Stack)是一种特殊的列表- 栈内元素只能通过列表的一端访问
- 栈是后进先出的数据结构
- 栈的核心操作
- 入栈(
push) - 出栈(
pop)
- 入栈(
- 栈的实现
Python列表从最后的位置添加和移除元素都非常高效，可天然地实现栈的操作
- 列表的
append()方法对应入栈操作(push) - 列表的
pop()方法对应出栈操作(pop)
list = [] list.append(1) list.append(2) print(list) # [1,2] list.pop print(list) # [1] - 列表的
队列
- 队列(
Quene)也是一种特殊的列表- 队列插入元素只能从队尾进行
- 队列删除元素只能在队首进行
- 队列是先进先出的数据结构
- 队列的核心操作
- 尾部添加
- 首部删除
- 队列的实现
队列用列表实现并不适合(在首部添加数据只能用
insert方法需要移动其他数据)，collections.deque是Python提供的双端队列，支持从任一端添加删除数据，速度快
#deque支持的方法
append(x) # 尾部添加元素
appendleft(x) # 首部添加元素
pop() # 尾部弹出元素
popleft() # 首部弹出元素
clear() # 清空队列
reverse() # 反转队列
# 实现
from collections import deque
dq = deque()
dq.append(1)
dq.append(2)
print(dq)
# deque([1,2])
dq.popleft()
# deque([2])
dq.popleft()
# deque([])0x02 树的概念
树不是一种线性结构，是非线性的，树在计算机科学里应用广泛，包括操作系统、图形学、数据库和计算机网络等。
树的术语
- 节点(Node) 树中每一个数据元素称为一个节点，节点是树的基本构成部分。
- 边(Edge)
边也是树的基本构成部分。边有方向，链接两个节点，并表示两个之间的联系。
除了根节点外每个节点都有且只有一条与其他节点相连的
入边(指向该节点的边)，每个节点可能有许多条出边(从该节点指向其他节点的边) - 根节点(Root) 根节点是树中唯一一个没有入边的节点
- 路径(Path) 路径是由边连接起来的节点的有序排列。
- 子节点集(Children) 当一个节点的入边来自另一个节点时，称前者是后者的子节点，同一个节点的所有子节点构成子节点集。
- 父节点(Parent) 一个节点是它出边所连接所有节点的父节点
- 兄弟节点(Sibling) 同一个节点的所有子节点互为兄弟节点
- 子树(Subtree) 子树是一个父节点的某个子节点的所有边和后代节点所构成的集合
- 叶节点(Leaf Node) 没有子节点的节点称为叶节点
- 层数(Level) 一个节点的层数是指从根节点到该节点的路径中的边的数目
- 高度(Height) 树的高度等于所有节点的层数的最大值
树的定义
树是节点和连接节点的边的集合，它有以下特征：
- 有一个节点被设计为根节点
- 除了根节点，每个节点都通过一条边与它唯一的父节点相连接
- 可以沿着唯一的路径从根节点到每个节点
- 如果这个树的每个节点都至多有两个子节点，称为
二叉树
0x03 二叉树
二叉树的定义
- 二叉树是由n(n≥0)个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是一个根和称为左、右子树的两个不相交的二叉树组成。
- 结点的度和树的度 每个结点具有的子树个数称为结点的度，树中所有结点的度的最大值称为树的度
- 二叉树的度为2
二叉树的特点
- 二叉树是有序树，即使只有一个子树，也必须区分左、右子树；
- 二叉树每个结点的度不能大于2，只能取0、1、2三者之一
- 二叉树所有结点的形态有五种:空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点
二叉树的性质
- 二叉树的第i层至多拥有2^i-1个结点
- 对任何一棵二叉树T，如果其叶结点数为N0,度为2的结点数为N2，则N0=N2-1
- 满二叉树：当树中每一层都满时，则称此树为满二叉树。
- 完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是右边缺少连续的若干个结点，则称此树为完全二叉树
- 满二叉树是完全二叉树的特例
- 深度为h的满二叉树的结点数为2^h-1
二叉树的遍历
按照一定次序访问树中的所有结点，并且每个结点的值仅被访问一次的过程
- 可能的三种遍历次序
- 先序遍历：首先访问根结点然后遍历左子树，最后遍历右子树
- 中序遍历：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
- 后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点
