树：事物的层次关系。硬盘文件管理，社会组织。

树的意义，使得查找效率更高。

查找：给定关键词，返回结果。静态查找，要查找的集合的元素时不变的，没有删除和插入，只有查找，例如查字典。动态查找：除了查找，还有插入和删除。

静态查找：方法一，顺序查找。普通循环。方法二，二分查找。排查电线杆。前提是顺序存放。

树：n个结点构成的有限集合。当n=0时，为空树。任何一个非空树，需要具备以下性质，有一个特殊节点root，其余结点可以分为互不相交的有限集，其中每个集合是一个树，称为原来树的子树。除了根结点，每个结点有且仅有一个父节点，所以n个结点的树有n-1条边。树是保证结点联通的最小的联通方式。去掉任何一条边都不连通。

树的基本术语：

结点的度：结点的子树个数

树的度：树的所有结点中最大的度数

叶节点：度为0的节点

父节点：有子树的结点是其子树的根结点的父节点。

子节点

父节点：具有同一个父节点

路径长度：路径上边的个数

祖先结点：沿着树根到某一结点路径上的所有结点都是这个结点的祖先结点。

子孙节点：某一结点的子树中的所有结点是这个结点的子孙。

结点的层次：根结点在1层

树的深度：树中所有结点中的最大层次是这棵树的深度。

树的表示：1.数组实现。不方便。2.链表实现。每个结点的结构形式不同，也不方便。3.儿子兄弟表示法：每个结点有两个指针，第一指针指向第一个儿子，第二个指针指向下一个兄弟。没有就为None。顺时针旋转45度，从上向下看，是一个二叉树。二叉树是度为2的树。

二叉树的定义：一个有穷的节点的集合。这个集合可以为空。若不为空，则它是由根结点和左右两个不相交的二叉树组成。二叉树度为二，左右有区别。结点可以没有子节点，可以只有左结点，也可以只有右结点，也可以左右结点都有。

特殊的二叉树：1.斜二叉树，都只有左结点2.满二叉树：每个结点都有左结点和右结点。3.完全二叉树：除了末尾几个没有结点了，按照满二叉树的顺序排。结点从上往下，从左往右。编号与满二叉树的编号相同。也就是从满二叉树的最后几个允许没有。

二叉树的几个性质：1.二叉树的第i层的最大结点数为2^(i-1)。2.深度为k的二叉树的最大节点数为2^k-1。3.对于任何二叉树，度为2的节点的个数加一等于叶子节点的个数。

二叉树的抽象数据类型：1.数据对象集合：一个有穷节点集合。2.操作集：判断是不是空，遍历，创建。遍历是最主要的操作：先序遍历--根、左树、右树；中序遍历--左树、根、右树；后序遍历--左树、右树、根；层次遍历--从上到下，从左到右。

二叉树的存储结构：1.顺序存储：数组可不可以，完全二叉树用数组可以，从上往下从左往右编号。非根结点，父节点的序号是它的二分之一取整；左儿子是它的二倍，右儿子是二倍加一。2.链表存储：每个节点有数据和左儿子指针和右儿子指针。

二叉树的遍历：

遍历的本质是拉成一个一维结构。

1.递归的遍历。先序遍历：先根结点，访问左子树，然后右子树。中序遍历：先左子树，根结点，然后访问右子树。后序遍历：左边递归，右边递归，然后根结点。三种遍历方法的路径都是一样的，区别只是在什么时候被打印，每个节点有三种可以被打印的机会。

2.非遍历的递归。例如中序遍历的非递归遍历算法。遇到一个结点，就把它压栈，并去遍历左子树，左子树遍历完成后，从栈顶弹出这个结点并访问他，然后再去中序遍历该节点的右子树。

3.层序遍历：遍历从根结点开始，首先将根结点入队，然后循环，结点数对，访问该节点，其左右儿子入队。

求二叉树的高度，左右子树的高度的最大值，然后加一。

表达式树，中序遍历得到中缀表达式，前序遍历得到前缀表达式，后序遍历得到后缀表达式。中缀表达式可能是不对的，左子树开始时加左括号，左子树结束时加右括号。

有一个中序遍历序列和一个前序遍历序列或者一个中序遍历序列和一个后序遍历序列，都可以唯一确定一个二叉树。先序序列是，根、左、右；中序是，左、根、右。就能找到。先序序列的第一个元素是根，在中序序列中找这个元素，这个元素前面的就是左子树。

树的同构：判断两个数是不是同构。如果一棵树能通过若干次左右儿子的交换后变成另一个数，就称两棵树是同构的。

静态链表：链表的思想，但是是数组的实现方式。存的不是指针，而是左右结点的下标。

二叉树的搜索：静态查找，动态查找。针对动态查找，数据如何组织？受到二分查找的启发，二分查找之所以比顺序查找效率高，是因为二分查找的数据有序的组织。所以也想把树的数据进行有效的组织。二叉搜索树就是这样的一种树。

二叉搜索树：一棵二叉树，可以为空，如果不为空，需要满足，非空左子树的所有键值小于其根结点的键值。非空右子树的所有键值大于根结点的键值。左右子树都是二叉搜索树。

二叉树要实现，1.给定要查找的元素，返回位置。与根结点比较，再决定是去左子树中找、根结点就是、还是右子树中找。二叉树越平衡，效率越高。2.查找最大元素。最大元素一定在最右分支的叶子节点上。最小元素一定是最左边节点的叶子结点上。3.二叉搜索树插入节点。关键要找到应该插入的位置。如果希望找的位置没有东西，就插在那里。4.删除。删除叶子结点。

平衡二叉树：搜索树结点的插入顺序不同，导致不同的深度也影响查找效率（平均查找长度）。发现越平衡的二叉树的查找效率越高。衡量平衡程度可以用左右两个子树的高度差不多。给定节点数为n的平衡二叉树，最大高度是O(log2 n)

平衡二叉树的调整：因为插入删除的时候，会导致不平衡。可以右旋。但是不管怎么调整，要保证左子树小，右子树大。要发现谁的插入导致哪个结点不平衡了。麻烦节点在发现结点的右子树的右子树上，有旋转解决。判断哪个结点不平衡，要看结点的左右子树的高度差，高度差大于或等于2就是不平衡了。破坏者在被破坏者的左左子树，则左旋转。被破坏的节点在低的地方的节点需要先解决。还有左子树的右子树上面，把插入节点到根结点之间的几个节点的从下往上的三个，让他们平衡。还有在右子树的左子树上。一共就这四种情况。

堆（heap）：不是堆栈。

优先队列：是一种特殊的队列。被服务的元素的顺序是按照元素的优先权的大小，而不是元素进入队列的先后顺序。

有些时候，我们要插入一个元素，并找到其中的额一个最小值或者最大值。删除其中的最大值是比较麻烦的。堆可以容易找到最值。

堆：用数组表示完全二叉树。任意一个节点是其子树的所有结点的最大值。分为最大堆和最小堆。

堆的操作集：1.创建堆。开辟一个数组。2.插入一个元素。在数组的末尾插入。检查他的父节点，如果让他的父节点不满足堆，则与父节点交换位置，一直与父节点相比。3.最大堆得删除。把最后一个节点替换根结点，然后不满足堆，再不断调换。

最大堆得建立：把所有的元素按照输入顺序存入一个完全二叉树。调整各个节点的位置，使得它满足最大堆。从下往上看，使得下面的子树依次是堆。