树
树的引入
树的本质优势：分层次组织
查找
静态查找
顺序查找
哨兵
的意思是在边界放一个值，便利的时候不需要写i>0这个条件，而是写不等于K，K就是传进来的那个查找目标值，这样就不用单独加一个循环条件了（如果K存在的话也是要跳出，到了边界也是要跳出）
二分查找
要求：n个数据元素的关键字满足有序（e.g.从小到大），且连续存储（数组）。
ASL：平均成功查找次数
二分查找时，因为我们事先对其中元素进行了
有序化的组织
，使得查找过程是按照
固定的顺序或者事先定义好的顺序
进行的。按照类似这样的结构化的形式存储数据，不局限于数组，就形成了树。
动态查找
树这样的数据结构可以实现动态查找。
树
· 定义
n个结点构成的有限集合。
根结点；互不相交；子树；子树是不相交的；除了根结点以外，每个节点有且仅有一个父节点；一棵N个结点的树有N-1条边。
· 树的基本术语
结点的度
：连接到下面的边的数目，即结点的
子树个数
树的度
：树的所有结点中最大的度数
叶结点(leaf)
：度为0的结点
父节点
，
子结点
兄弟结点
：具有同一父结点的各结点彼此是兄弟结点
路径和路径长度
：结点序列（从ni到nk），路径所包含边的个数为路径的长度
祖先结点
：从树根到某一结点路径上所有结点都是其祖先结点
子孙结点
结点的层次
：规定根结点在1层，其他任一结点的层数是其父结点的层数+1
树的深度
：树中所有节点中的最大层次是这棵树的深度
空树的depth=-1
一个节点的depth=0
“两层”节点，depth=1
· 树的表示方法
数组❌ 普通的链表❌（并不是二叉树，一个结点可能有多个子结点）
-> 儿子-兄弟表示法。两个指针域，且空间浪费不大。
便于进行**
层序遍历
**
二叉树
· 介绍
度为2的树。每个结点的指针最多是两个。一般的树都可以用上面的“儿子-兄弟”表示方法来变成二叉树。
【二叉树是最重要也是最主要的内容】
二叉树的子树有左右顺序之分
加图
· 特点
一个二叉树第i层的最大结点数为：
2
(
i
−
1
)
2^{(i-1)}
2
(
i
−
1
)
, i>=1
深度为k的二叉树的最大结点总数为：
2
k
−
1
2^k-1
2
k
−
1
, k>=1
(
1
+
2
1
+
2
2
+
2
3
+
.
.
.
+
2
(
k
−
1
)
=
2
k
−
1
1+2^1+2^2+2^3+…+2^{(k-1)} = 2^k-1
1
+
2
1
+
2
2
+
2
3
+
.
.
.
+
2
(
k
−
1
)
=
2
k
−
1
)
对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者的关系n0 = n2 + 1.
（由边可以证明，n个节点的树有n-1条边，
n
0
+
n
1
+
n
2
−
1
=
0
∗
n
0
+
1
∗
n
1
+
2
∗
n
2
n0+n1+n2-1 = 0*n0 + 1*n1+ 2*n2
n
0
+
n
1
+
n
2
−
1
=
0
∗
n
0
+
1
∗
n
1
+
2
∗
n
2
，得n0 = n2 + 1)
· 定义
类型名称：二叉树
数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。
操作集：
判断BT是否为空
；
遍历，按某顺序访问每个结点
；
创建一个二叉树
二叉树的遍历是树里最主要的操作方法。
####· 二叉树的存储结构
1、顺序存储（数组）
完全二叉树可以用数组来存（没有空间浪费）
2、链表存储
适用于一般的二叉树。分三个域，left, data, right
· 二叉树的遍历
1. 先序遍历（Preorder Traversal）
遍历过程为：
访问根结点 -> 先序遍历其左子树 -> 先序遍历其右子树
【
递归
实现】
if（BT）的意思是，判断BT是否为空！
2. 中序遍历（Inorder Traversal）
遍历过程为：
中序遍历左子树 -> 访问根结点 ->中序遍历右子树
3. 后序遍历（Postorder Traversal）
遍历过程为：
后续遍历左子树 -> 后续遍历右子树 -> 访问根结点
【图略】
注意：先序、中序、后序遍历时，经过结点的路线是一样的，只是
访问各结点的时机
不同。
以上三种方法都是用
递归
（堆栈）实现的。
非递归实现：
4. 层序遍历
二叉树是一个二维结构，
而遍历过程实质是
产生一个访问序列
（一维，线性结构）
，所以遍历二叉树的本质就是
如何把一个二维结构变成一维的线性序列的过程
。
层序遍历通过
队列
实现
：遍历
从根结点开始
，首先将
根结点入队
，然后开始执行循环：
结点出队、访问该结点、其左右儿子入队
。
如果是使用
数组
存储这颗树的节点的话，那么直接输出即可，非常方便。
· 二叉树遍历的应用
由两种遍历序列确定二叉树
必须含有
中序遍历
！否则无法分辨左右根。
如果变成后序和中序，则倒着看即可，即后序的最后一个节点是根结点，由此在中序序列中分割为左右子树。在中序中圈出左右子树，在后序中找到对应的序列，最后一个字母为根结点。继续递归下去即可。
表达式树
加图
二叉查找树
对于树中每个节点X，它的左子树中**
所有
关键字值，
小于
X的关键字值，而它的右子树中
所有
关键字值
大于
**X的关键字值。在删除一个结点的时候，分三种情况：1.该节点为叶子节点，则直接删除即可；2.该节点有一个子节点，则把该节点的父结点指向它的指针指向其子节点即可；3.
该节点有两个节点
【重点】
：将该节点的左子树中右下角的元素，和该节点元素交换。