树与二叉树
树
- 有且只有一个称为根的节点（头结点）
- 每个节点可以有多个直接后继（孩子结点）
- 根节点外，每个结点有且只有一个直接前驱结点（双亲结点）
- 属于非线性结构，空树也是树型结构，也属于非线性结构
树中的概念
| 主称 | 别称 |
|---|---|
| 结点 | 元素 |
| 叶子结点 | 尾结点 |
| 孩子结点 | 直接后续结点 |
| 双亲结点 | 直接前驱结点 |
| 兄弟结点 | 双亲相同的结点 |
度指结点的直接后继的个数（也就是多少个子结点）
- 叶子结点的度为0
- 树的度：所有结点度的最大值
- 层次指结点：所在的层数，根是一层
- 树的深度：所有结点层数的最大值
- 森林就是树的集合（森林可以是空集）
树元素之间的关系
- 兄弟节点：双亲相同的节点
- E内有兄弟，G的兄弟是H,H的兄弟是G
- 度指节点的直接后继个数
- A的度为3
- F的度为0
二叉树
- 二叉树不是树的特例
- 树和二叉树是两个不同的数据结构
二叉树属于树形结构
- 每个节点的度≤2
- 每个节点最多2个孩子
- 可以有1个孩子，也可以没有孩子（叶子节点）
- 孩子节点非为左孩子和右孩子
性质
- 二叉树第i层上的节点树目最多为$2^{i-1}$ {i≥1}
- 深度为k的二叉树至多有$2^k-1$个节点{k≥1}
- 包含n个点，的二叉树高度至少为$\log_2(n+1)$
- 在任意一颗二叉树中，若终端节点的个数为$n_0$，度为2的节点树为$n_2$，则$n_0=n_2+1$
- 叶子节点比度为2的节点多1个
叶子节点：度为0
二叉树的总结点为：度为0的个数+度为1的个数+度为2的个数
（其中，度为0（叶子节点）的个数比度为2的个数多1个）
满二叉树
完全二叉树
满二叉树的基础上可以少节点
- 最底层的可以减少
- 从右往左减少（右有结点则左边一定有结点）
- 按层编号：1 - N （由上向下，从左到右）
- 双亲编号为：i/2
- 如果有左孩子，则编号为：2i
- 如果有右孩子，则编号为：2i + 1
- 度为1的结点可能是0个或者1个
- 具有N个节点完全二叉树的深度为$[\log_2N]+1$
题1：叶子有4个，度为1的有5个，该二叉树共有（）个节点
- 叶子节点比度为2的节点多一个，所以度为2的节点为3个
- 所以：该二叉树共有12个节点：5+4+3
题2：有28个节点的完全二叉树深度为（）
- 根据完全二叉树深度公式$[\log_2N]+1$：
- $2^5 $ < 28, $2^5$<5，取4，所以4+1 = 5
- 28个节点完全二叉树深度为5
二叉树遍历
访问二叉树中每个结点1次，且每个结点制备访问1次，有以下遍历方法：
- 先序遍历
- 中序遍历
- 后序遍历
先序遍历
（分成三部分）根、左子树、右子树
- 左子树：以左孩子为根的树称为左子树
- 右子树: 以右孩子为根的树称为右子树
遍历顺服：访问根结点->访问左子树->访问右子树（先左后右是正确的）
循环结果： ①②④⑤③⑥⑦⑧
中序遍历
（分成三部分）根、左子树、右子树
- 左子树：以左孩子为根的树称为左子树
- 右子树: 以右孩子为根的树称为右子树
步骤：访问左子树->访问根结点->访问右子树
给个解释：（每个节点都把自己当成根，然后按照步骤输出）
第一次遍历（A的左侧）：A作根，找到左子树B
第二次遍历（A的左侧）：B下有C，C作根，找到左子树D
第三次遍历（A的左侧）：C为 D 的根节点，找到根节点D
第四次遍历（A自己）：A作根，找到根节点A
第五次遍历（A的右侧）：A下有E，E作为根，因无左子树，输出右子树F
第六次遍历（A的右侧）：F作为根节点，但只有一个元素G，所以找到G
第七次遍历（A的右侧）：此时E“已经访问完自己左子树”，接着是自己，所以找到E
第八次遍历（A的右侧）：此时仅剩一个元素H
先序遍历结果：ABCDEFGH
中序遍历结果：BDCAFGEH
后续遍历
（分成三部分）根、左子树、右子树
- 左子树：以左孩子为根的树称为左子树
- 右子树: 以右孩子为根的树称为右子树
步骤：访问左子树->访问右子树->访问根结点
==key12345==
- A的最极限左子树为B
- A的最极限右子树为H
- E的最极限左子树为F
以此类推 但不要搞混了
后序遍历顺序：CDB GFHE A
同理，可以根据顺序来推出二叉树的图
程序设计理论
- 程序：为了解决某一个具体问题而编写的指令序列，主要是靠人来编写的
- 程序设计：是编写程序的过程，要通过具体的编程工具才能够写程序
- 程序设计风格：不影响程序正确和效率的前提下，对程序进行有效的编排和组织的基本原则
- 是是外在的格式，与程序的功能没有关系
- 从风格的角度：“清晰第一、效率第二”
结构化设计原则
- 自顶向下
- 模块划分
- 逐步求精
- 结构化编码
强调程序风格的意义：
- 程序的可读性好
- 易于测试，易于维护
- 减少读程序时间、提高软件开发的效率
面向对象
面向对象的基本思想（OOP）：将面向对象的思想引入软件开发的过程中
面向对象的优点
- 符合人们认识客观世界的规律
- 稳定性好
- 可重用性好
- 易于维护
对象
对象的概念：现实世界中，每个实体都是对象，可以是有形的也可以是无形的，对象是属性和方法的封装体
对象的特征
标识唯一性
分类性
封装性
多态性 （多态性是允许你将父对象设置成为一个或更多的他的子对象相等的技术)
模块独立性
模块化设计是指将软件分解为多个独立模块，不同的模块具有不同的功能和职责。每个模块可以独立的进行开发、测试，最后组装成完整的软件。
属性：是对象所包含的信息
方法：是对象的动态属性（操作、服务、行为）
操作：是对象的动态性属性
类
- 类是对象的集合
- 是属性和方法 相似的对象的集合
- 类中的对象称为：实例
- 类是对象的集合、对象是类的实例
继承（派生）
- 是基于类的概念，不是对象的概念
- 一个类可以继承另一个类的基本特征，还可以有自己的新特征
消息
- 是基于对象的概念
- 是对象之间通信的手段
多态性
- 基于方法的概念
- 同一个操作作用于不同的对象上可以有不同的结果
信息隐蔽、模块独立、和封装是实现信息隐蔽的手段，封装了才有独立性可言
